資料結構 第7章　圖形結構

7-1　認識圖形 Koenigsberg Bridge問題

7-1-1　圖形的定義 圖形G是由V(G) 和E(G) 所組成，其中V(G) 是一個有限且非空的集合，代表頂點，E(G) 是一個有限的集合，代表邊 ，寫成G = (V, E)。

7-1-2 圖形的相關名詞 相關名詞： 相鄰 分支度 長度 簡單路徑 連通 、強連通 、弱連通 循環 加權圖形 7-1-2　圖形的相關名詞 相關名詞： 相鄰 分支度 長度 簡單路徑 連通 、強連通 、弱連通 循環 加權圖形 自身迴圈 、多重圖形 、簡單圖形 子圖形 連通單元、強連通單元 完整圖形

7-2　圖形的表示方式 7-2-1　相鄰矩陣 範例7.1：以相鄰矩陣存放無向圖形G1。

範例7.2：以相鄰矩陣存放有向圖形G2。

7-2-2　相鄰串列 範例7.3：以相鄰串列存放無向圖形G1。

範例7.4：以相鄰串列存放有向圖形G2。

7-2-3　加權圖形的表示方式 範例7.5：以相鄰矩陣存放加權圖形G6。

範例7.6：以相鄰串列存放加權圖形G6。

7-3　圖形的基本運算 7-3-1　深度優先搜尋 (DFS)

範例7.7：[DFS] 假設下列圖形的起始頂點為A，試寫出其深度優先搜尋結果。

解答：

7-3-2　廣度優先搜尋 (BFS)

範例7.9：[BFS] 假設下列圖形的起始頂點為A，試寫出其廣度優先搜尋結果。

解答：

7-3-3　連通單元 只要呼叫dfs(0) 或bfs(0) 函數，令它從第一個頂點開始走訪，一旦在走訪完畢後還有其它尚未拜訪過的頂點，就表示該圖形不是一個連通圖形 ，下圖即為一例。 show_connected() { int v; for(v = 0; v < n; v++) if (visited[v] == FALSE){ dfs(v); printf("\n"); }

7-3-4　擴張樹 圖形的擴張樹 (spanning tree) 指的是以圖形內最少的邊數連接所有頂點所形成的樹，而樹 (tree) 則是連通且沒有循環的圖形 。

圖形G14幾種可能的擴張樹 ：

G15的DFS樹 G15的BFS樹

7-4　最小擴張樹 Kruskal演算法

Prim演算法

Sollin演算法

7-5 最短路徑 最短路徑 (shortest path) 又分成「某個頂點到其它頂點的最短路徑」和「任意兩個頂點的最短距離」兩種情況。 7-5　最短路徑 最短路徑 (shortest path) 又分成「某個頂點到其它頂點的最短路徑」和「任意兩個頂點的最短距離」兩種情況。 以加權圖形表示城市之間的交通路線

7-5-1 某個頂點到其它頂點的最短路徑 起點 終點 最短距離 最短路徑 V0 V1 7 V0→V1 V2 3 V0→V2 V3 12 7-5-1　某個頂點到其它頂點的最短路徑 起點 終點 最短距離 最短路徑 V0 V1 7 V0→V1 V2 3 V0→V2 V3 12 V0→V2→V3 V4 20 V0→V2→V4 V5 13 V0→V2→V5 V6 14 V0→V2→V5→V6 V7 24 V0→V2→V5→V7

使用Dijkstra演算法求取某個頂點到其它頂點的最短路徑：每次都要從尚未選擇的頂點中選擇距離最短者Vx ，然後檢查有沒有其它尚未選擇的頂點Vi因為行經Vx而使距離變短，如此重複V - 1次，直到找出第V - 1個頂點的最短路徑，整個演算法才宣告結束。

7-5-2 任意兩個頂點的最短距離 方法一：分別以加權圖形的每個頂點做為起始頂點執行Dijkstra演算法。 7-5-2　任意兩個頂點的最短距離 方法一：分別以加權圖形的每個頂點做為起始頂點執行Dijkstra演算法。 方法二：使用Floyd演算法，其步驟如下 ： 使用admatrix[V][V] 陣列存放加權圖形的相鄰矩陣。 定義Ak[i][j] 為Vi到Vj的最短距離，而且中間只能經過 索引小於等於k的頂點。 定義A0[i][j] 為admatrix[i][j] 。 根據下式依序求取A0、A1、…、AV，AV即為最後的結果。 Ak[i][j] = min{ Ak-1[i][j], Ak-1[i][k] + Ak-1[k][j]}, k ≥ 1且A0[i][j] = 邊 (Vi, Vj) 的距離

範例7.18：[Floyd演算法] 針對加權圖形G17找出任意兩個頂點的最短距離。

解答： 1. 3. 2. 4.

7-6 拓樸排序 頂點工作網路 (AOV網路，activity on vertex network) 7-6　拓樸排序 頂點工作網路 (AOV網路，activity on vertex network) 前行者 (predecessor)、後繼者 (successor) 立即前行者 (immediate predecessor) 、立即後繼者 (immediate successor) 拓樸排序 (topology sort)，例如V0→V1→V2→V3→V4→V5→V6→V7和V0→V1→V2→V3→V4→ V6→V5→V7

範例7.20：[拓樸排序] 針對有向圖形G18找出其拓樸排序。 1. 2.

3. 4. 5. 6.

7. 8. 9.輸出V7，所有頂點均輸出完畢，得到拓樸排序為V0→V1→V2→V3→V4→V5→V6→V7。