Chapter 12 圖型結構 - Ian-Liu-1990/Data-Structure GitHub Wiki

Ｉ. 圖形[計算邊數和觀念]

  1. 頂點Vertex

  2. 邊Edge

    1. 路徑: 由一個邊或一個邊以上所組成
    2. 路徑長度: 所有經過的邊總和
    3. 簡單路徑: 除了起點和終點可以是相同(亦可以不同)，其餘頂點皆不可以重複
    4. 迴路: 1. 起點和終點必須是相同，2. 是一條簡單路徑，程式實作 - 使用DFS或BFS若pop出已看過，代表有迴路
    5. 附著: 指邊附著在點上
    6. 連通: 兩點間存在一條路徑

  3. 圖形

    1. 有向連通圖形:
    • 強連通頂點: 兩相異頂點V1，V2互相有路徑可到達對方
    • 強連通圖形: 任意相異點Vi和Vj皆互相有路徑可到達對方
    • 強連通單元: 最大的有向連通子圖
    1. 無向連通圖形:
    • 連通圖形: 任意相異點Vi和Vj皆互相有路徑可到達對方
    • 連通單元: 最大的有向連通子圖
    1. 完全圖形:
    2. 完全子圖: 若G完全圖形的部份G'也為完全圖形，則G'為完全子圖
    3. 多重圖形: 若一個圖形，同一個邊重複多次

ＩＩ. 尤拉循環

ＩＩＩ. 圖形追蹤[申論考點 - 哪一個方法優秀或時間空間複雜度]

鄰接串列時間複雜度 鄰接矩陣時間複雜度
DFS O(n+e) : 由串列一個一個接尋找 O(n^2) : 陣列必須將每一行每一列都檢查
BFS O(n+e) O(n^2)

ＩＶ. 展開樹Ｔ

  1. 定義 :

    1. Ｔ是Ｇ的子圖
    2. Ｔ包含Ｇ所有節點
    3. Ｔ是一棵樹(一種圖型，連通圖且沒有循環)

  2. 以BFS或DFS找出此同型的連通單元

Ｖ. 最小成本展開樹Ｔ

  1. 定義 : 以最少的邊連通圖形中所有的頂點，且邊所花費的成本為最少 ->即找出最小成本伸展樹(Spanning Tree)

  2. 求最小伸展樹演算法

    1. Kruskal's : 先將所有成本邊排序，每次找成本最小的邊加入子圖中，加入最小邊且不能造成迴圈
      1. 程式實作 - 找最小權重邊 : 以最佳排序或最小堆積樹Ｏ(ElogE)
      2. 程式實作 - 加入的邊是否形成迴圈 : 將邊的點加入鄰接串列，再用BFS或DFS是否搜尋中會中斷(表示形成迴圈)
    2. Prims : 先初設1頂點加入集合U，每次從U找集合V-U中找所有相臨未拜訪點使"相鄰的邊成本最小Min"
  • 不管用1還是2，所求得的Spanning tree為同一個

ＶＩ. 求最短路徑或最少成本 - 網路圖型 : 兩頂點在最小成本路徑上，不代表為原圖Ｇ的最短路徑

１. 連結狀態導向-Djkstra : OSPF網路協定，限制 - Single Source(起點到其他點)路徑權重不可為負

２. 向量導向-Bellman fold : RIP網路協定，限制 - Single Source(起點到其他點)的圖型，邊可以為負，但不可以有負的迴路

３. Ｆｌｏｄｙ－Ｗａｒｓｈａｌｌ : 限制 - "任意兩點"i和j的最短路徑，邊可以負，但不可以有負的迴路

４. Ｊｏｈｎｓｏｎ’ｓ演算法 : 限制 - "任意兩點"i和j的最短路徑，邊可以負，但不可以有負的迴路

ＶＩＩ. AOV網路拓樸 - 有向非循環圖，<= 求工作先後順序

  1. 定義 : 將有向圖節點排列成一組線性順序，且若其中u為v前行節點，則u必須排在v之前
  2. 應用 : 以頂點表示工作或活動，以邊表示工作之間的先後順序．不會直接給圖，小心工作表格

ＶＩＩＩ. AOE邊工作網路拓樸-一個計劃開始到結束至少需要多少時間完成，找到緊要工作並縮短它，可縮短整個計畫完成時間

  1. 最早MAX可能開始時間 - 演算法 : a[j], a[i]皆表示自己工作最早開始時間，d(i, j)表示i完成所需時間

  2. 最晚MIN可能開始時間 - 演算法 :

  3. 臨界路徑CPM : 由緊要工作所組成的最長路徑工作時間

  4. 緊要工作 : 第i"邊"最早工作時間(看起始節點的最早開始時間) = 第"i"邊"最晚工作時間的工作(最晚時間 - 前邊花費時間)

  5. 可縮短時間的點減少整個專案時間 : 連通臨界路徑i的"邊集合" 交集 連通臨界路徑j的"邊集合"

ＶＩＩＩＩ. 最大流量與最小切割 - 須小心優化回流，當作無向圖處理