Chapter 7 圖形與網路 資料結構導論 - C語言實作

7.1 前言 圖形(Graph)結構具有以下重要特徵： 圖形結構基本上是由頂點(Vertices)與邊(Edges)兩個部分所構成 。 圖形結構是否具有方向性來將圖形結構分成兩大類：無向圖(Undirected Graph)與有向圖(Directed Graph)。 圖形的另一特點是資料也可以儲存在圖形的個別邊上。邊上的資料可用以表示從這個邊的一個頂點至另一個頂點的花費(或成本)。 這種成本存在邊上的圖形稱為「網路」 。 資料結構導論 - C語言實作

7.2 圖形的基本術語 圖形(Graph)可利用頂點(Vertices，或稱Nodes)與邊(Edges)來加以描述，也就是說圖形可以視為由頂點和邊所組成的集合 。 圖形結構會根據邊是否有方向性來區分為有向圖(Directed Graph)和無向圖(Undirected Graph)兩類。 資料結構導論 - C語言實作

7.2.1 無向圖的基本概念 一個無向圖G = (V，E) 無向圖的邊可以利用(V1 ,V2)或(V2 ,V1)來表示，其中 V1 ,V2 V │V│來表示此無向圖的頂點的個數 │E│代表此無向圖邊的個數 資料結構導論 - C語言實作

無向完全圖 無向完全圖(Undirected Complete Graph) 一個無向圖G = (V，E)其圖形中每一個節點均與其他的節點直接相連 也就是任意一個節點會與透過|V|-1條邊與其他的節點相連接 一個包含N個頂點的無向完全圖總共會有 N(N-1)/2 個邊。 圖7.1 無向完全圖 資料結構導論 - C語言實作

分支度, 路徑, 長度 無向圖中頂點的分支度(Degree) 無向圖中共邊的兩點(V1 ,V2)而言 VX 到VY 的路徑(Path) 紀錄了連接該頂點的邊之數目 無向圖中共邊的兩點(V1 ,V2)而言 稱V1和V2 兩頂點相鄰(Adjacent) VX 到VY 的路徑(Path) 從頂點 VX 到頂點 VY 所經過的頂點串列 路徑所經過之邊的總數為該路徑之長度(Path Length) 資料結構導論 - C語言實作

簡單路徑, 迴路 在無向圖中的任一條路徑其起點和終點可以相同 簡單路徑(Simple Path) 迴路(Cycle) 若是某一給定的路徑除了起點和終點外，其餘的頂點均只經過一次的路徑 迴路(Cycle) 若是一個簡單路徑的起點與終點是相同的我們將它稱為一個迴路 資料結構導論 - C語言實作

7.2.1 無向圖的基本概念 一個無向圖中如果任意兩個頂點VX 與 VY 間有路徑相通，則稱 頂點VX 和 VY 是相連的(Connected)。 如果一個無向圖中任意兩個頂點皆是相連，則我們稱這個無向圖是相連的無向圖(Connected Graph) 。 資料結構導論 - C語言實作

7.2.1 無向圖的基本概念 一個無向圖不是相連的，此無向圖會由兩個或兩個以上的不交集的相連子圖所組成。 個別相連子圖(Connected Subgraph)也可稱為相連單元(Connected Component)。 資料結構導論 - C語言實作

7.2.2 有向圖的基本概念 一個有向圖G = (V，E) 有向圖的邊是利用<V1 ,V2>來描述，表從 V1 到 V2 有路可通 <V1 ,V2>與<V2 ,V1>是不同的，因為有向圖的邊是具有方向性的 │V│來表示此有向圖的頂點的個數 │E│代表此有向圖邊的個數 資料結構導論 - C語言實作

7.2.2 有向圖的基本概念 有向圖中邊是具有方向性的 有向圖的表示法中路徑(Path)也是具有方向性 在有向圖中從頂點 VX 到頂點 VY 所經過的頂點串列稱之為 VX 到VY 的路徑(Path) 。 而路徑所經過之邊的總數為該路徑之長度(Path Length)。 圖7.2 有向圖 資料結構導論 - C語言實作

7.2.2 有向圖的基本概念 有向圖中的任一條路徑其起點和終點可以相同 若是某一給定的路徑除了起點和終點外，其餘的頂點均只經過一次的路徑稱之為簡單路徑(Simple Path) 若是一個簡單路徑的起點與終點是相同的我們將它稱為一個迴路(Cycle) 資料結構導論 - C語言實作

7.2.2 有向圖的基本概念 一個有向圖G = (V，E)其圖形中每一個節點均與其他的節點直接相連 這樣的有向圖我們將之稱為有向完全圖(Directed Complete Graph) 我們發現一個包含N個頂點的有向完全圖總共會有 N(N-1) 個邊 圖7.3 有向完全圖 (Directed Complete Graph) 資料結構導論 - C語言實作

7.2.2 有向圖的基本概念 在無向圖和有向圖表示中，針對頂點分支度(Degree)的定義是不同的 無向圖因為一個邊表示兩個頂點互相連通 所以只有定義個別頂點的分支度 在有向圖中的頂點分支度分成 出分支度(Out Degree)和 入分支度(In Degree)兩部分 資料結構導論 - C語言實作

7.2.2 有向圖的基本概念 有向圖的任意兩個頂點 VX 和 VY，VX 到 VY 存在一條路徑可以連通這兩個節點，且 VY 到 VX 也有路徑可以連通，稱此有向圖為緊密相連(Strongly Connected)。 一個非緊密相連的有向圖中，其中具有緊密相連關係的最大子圖稱緊密相連單元(Strongly Connected Component)。 圖7.2的緊密相連單元 (Connected Component) 資料結構導論 - C語言實作

7.3 圖形的表示法 7.3.1 相鄰矩陣表示法(Adjacent Matrix) 7.3.2 相鄰串列表示法 7.3.3 相鄰複串列表示法 7.3 圖形的表示法 7.3.1 相鄰矩陣表示法(Adjacent Matrix) 7.3.2 相鄰串列表示法 7.3.3 相鄰複串列表示法 資料結構導論 - C語言實作

7.3.1 相鄰矩陣表示法(Adjacent Matrix) 利用一個大小是NN的二維陣列DATA來表示一個包含N個頂點的圖形 若在給定的圖形中頂點 i 到頂點 j 是相連的(存在一個邊連接這兩個頂點), 陣列對應元素DATA[i][j]會被設定為1 否則DATA[i][j]會被設定為0 資料結構導論 - C語言實作

7.3.2 相鄰串列表示法 圖7.5(a)中無向圖G1之相鄰矩陣表示結果 圖7.5 (a) 無向圖G1 (b) 有向圖G2 資料結構導論 - C語言實作

7.3.2 相鄰串列表示法 相鄰串列表示法(Adjacent List) 是利用串列結構來紀錄給定的圖形中頂點的相鄰關係 相鄰矩陣中矩陣元素DATA[i][j]值為1表示對應的頂點i與頂點j是相連的 無向圖的相鄰串列表示法 有向圖的相鄰串列表示法 資料結構導論 - C語言實作

7.3.3 相鄰複串列表示法 相鄰複串列的結構中個別節點是用以表示給定圖形的一個邊的資料，因此相鄰複串列的節點又被稱為邊節點 它包含了標記欄，邊的頂點欄VX，邊的頂點欄VY，VX鏈結欄和VY鏈結欄等五個欄位 圖7.10 相鄰複串列的邊節點結構 資料結構導論 - C語言實作

7.3.3 相鄰複串列表示法 (a) 無向圖 (b) 圖7.11(a)的相鄰複串列表示法 圖7.11 相鄰複串列 圖7.11 相鄰複串列 資料結構導論 - C語言實作

7.3.3 相鄰複串列表示法 圖7.12 相鄰複串列 資料結構導論 - C語言實作

7.4 圖形追蹤 (Graph Traversal) 從圖形之某一個頂點VX出發，找尋所有可以從VX到達的頂點，這樣的動作我們稱它為圖形的追蹤(Graph Traversal) 常見圖形追蹤方法有兩種： 深度優先搜尋法(Depth First Search, DFS) 廣度優先搜尋法(Breadth First Search,BFS) 資料結構導論 - C語言實作

7.4.1 深度優先搜尋法 假設VX是起始搜尋頂點，設定此頂點已被拜訪過。 從與起始搜尋頂點VX連接且未被拜訪過的頂點中選出一個頂點。假設該頂點為VY，設定此頂點已被拜訪過。並記錄其前一個搜尋頂點是VX，以VY為新的搜尋頂點進行深度優先搜尋。 如果與頂點VX連接的頂點皆已被拜訪過，則回到頂點VX的前一個被搜尋頂點。假設此頂點是Vz，則以Vz為新的起點搜尋頂點進行深度優先搜尋。 資料結構導論 - C語言實作

7.4.1 深度優先搜尋法 我們發現深度優先搜尋法可以利用堆疊(Stack)來記錄深度優先搜尋過程中的資訊，並以遞迴(Recursive)的方式進行圖形追蹤的處理 。 透過深度優先搜尋法的追蹤可將給定的圖形分割成為一棵樹或是一片樹林，我們將這兩種狀況分別稱為深度優先擴張樹(Depth First Spanning Tree)以及深度優先擴張樹林(Depth First Spanning Forest)。 資料結構導論 - C語言實作

7.4.1 深度優先搜尋法 深度優先追蹤過程 A，B，D，G，E，C，F，H，I是本例找到的一組解 資料結構導論 - C語言實作

7.4.2 廣度優先搜尋法 選擇一個起始頂點VX，並設定此頂點已經被拜訪過。 將與VX相連的所有頂點放入佇列。 若佇列不是空的則從佇列取出一個頂點VY，並設定此頂點已被拜訪過。並將與VY相連且未拜訪過的頂點放入佇列中。 重複步驟3直到佇列是空的。 資料結構導論 - C語言實作

7.4.2 廣度優先搜尋法 廣度優先搜尋法BFS可以使用佇列(Queue)的概念來搜尋相連的頂點，上一節所介紹的深度優先搜尋法DFS則是使用堆疊的概念來搜尋相鄰的頂點。 廣度優先搜尋法的追蹤可以將圖形分割成為一棵樹或是一片樹林，我們將這兩種狀況分別稱為廣度優先擴張樹(Breadth First Spanning Tree)以及廣度優先擴張樹林(Breadth First Spanning Forest)。 資料結構導論 - C語言實作

7.4.2 廣度優先搜尋法 A，B，C，D，E，F，G，H，I是本例找到的一組解 廣度優先追蹤過程 資料結構導論 - C語言實作

7.5 擴張樹和花費最少擴張樹 一個無向相連圖(Undirected Connected Graph)G = (V,E) 7.5 擴張樹和花費最少擴張樹 一個無向相連圖(Undirected Connected Graph)G = (V,E) 其中|V|=N而且|E| N-1 我們可以利用圖形中的N-1 個邊建立一棵可以連接所有頂點的樹，我們將這樣的一棵樹稱為擴張樹(Spanning Tree) 資料結構導論 - C語言實作

7.5 擴張樹和花費最少擴張樹 擴張樹具有下列基本的特性： 若要加入圖形中其餘的邊到擴張樹中必會形成迴路(Cycle) 7.5 擴張樹和花費最少擴張樹 擴張樹具有下列基本的特性： 若要加入圖形中其餘的邊到擴張樹中必會形成迴路(Cycle) 擴張樹中的任兩個頂點間都是相連的 也就是存在一條路徑可通，但此一路徑不一定是原圖形中該兩頂點之最短路徑 (a) DFS 擴張樹 (b) BFS 擴張樹 資料結構導論 - C語言實作

圖形與樹的差異 樹的子樹間除了透過共同的樹根外，沒有其他方法可以讓個別子樹相連 如果將兩個子樹的節點直接相連，就變成圖形，不再是樹 樹狀結構中是不允許迴路存在的 (a) DFS 擴張樹 (b) BFS 擴張樹 資料結構導論 - C語言實作

產生擴張樹的方法 DFS與BFS擴張樹 依照DFS與BFS搜尋方法所找出的頂點順序，循序地挑選對應的邊，即可產生 (a) DFS 擴張樹 (b) BFS 擴張樹 資料結構導論 - C語言實作

7.5 擴張樹和花費最少擴張樹 |E|= |V| -1 擴張樹 資料結構導論 - C語言實作

7.5 擴張樹和花費最少擴張樹 一個給定的網路所建立的花費最少擴張樹(Minimum Cost Spanning Tree) 7.5 擴張樹和花費最少擴張樹 一個給定的網路所建立的花費最少擴張樹(Minimum Cost Spanning Tree) 指的是在所有可能的擴張樹中其個別邊的加權值總和(即總成本)最少的 花費最少擴張樹的所有邊的加權值之總和會是所有可能的擴張樹中最少的 但是不表示在最少成本擴張樹中連接任意兩頂點的成本一定會最少 資料結構導論 - C語言實作

7.5.1 Prim's Method 給定一個網路G=(V, E)，其中V是頂點的集合而E是邊的集合。每個邊都有其對應的成本 令 A=V，B=，T=，其中為空集合 從A中任選一個頂點VX，將之從A搬移到B，並將此頂點加入花費最少擴張樹T 找出一條連接A和B的最少花費邊 (VY,Vz)，其中VY A，Vz B，且邊(VY,Vz)加到T不會造成迴路 資料結構導論 - C語言實作

7.5.1 Prim's Method 最少成本擴張樹中並非連接任意兩頂點的成本一定會最少 將頂點VY自A搬移到B，並將頂點VY與邊(VY,Vz)加入T。 重複步驟(3)-(4)直到 A=。 (a) G (b) G的花費最少擴張樹T 最少成本擴張樹中並非連接任意兩頂點的成本一定會最少 資料結構導論 - C語言實作

7.5.2 Kruskal’s Method 從網路 G=(V,E) 中挑選出前N-1個花費較少並且不會產生迴路(Cycle)的邊，循序地將這些邊以及相關頂點加入擴張樹T中即可建立出花費最少的擴張樹 令花費最少擴張樹 T=。 從網路的邊集合E中選取其中花費最少的邊(VX ,VY)。 測試如果將這個邊(VX,VY)加入到擴張樹T中會不會產生迴路。若不會產生迴路則將這個邊與相關頂點加入到T中，否則從網路的邊集合E中刪除(VX,VY)。 重複步驟(2)-(3)，直到擴張樹T的邊數等於 N-1 為止。 資料結構導論 - C語言實作

7.5.2 Kruskal’s Method (a) (b) (c) (d) 資料結構導論 - C語言實作 9 8 4 2 5 7 3 6

7.6 最短路徑問題 在圖形網路的應用中我們有時需要找出 7.6 最短路徑問題 在圖形網路的應用中我們有時需要找出 任意兩個頂點間的最短距離 從某一個特定的頂點到其他所有頂點的距離 為了找出圖形網路中單一節點與其他所有頂點的最短距離以及圖形網路中任兩個頂點的最短距離，我們將在下面的段落詳細地介紹這兩個問題的解決方法 資料結構導論 - C語言實作

7.6.1 單一頂點到其他頂點之最短距離 一個有向網路G = (V,E) 為了找出這個網路中的某個特定頂點到其他所有頂點之最短距離 用一個二維的成本相鄰矩陣COST[N][N]來儲存 N=|V| 針對網路中所有的有向邊(i,j)將這個邊的成本存入COST[i][j] 否則COST[i][j] = ∞ 資料結構導論 - C語言實作

7.6.1 單一頂點到其他頂點之最短距離 利用一維陣列FLAG[N]來紀錄個別頂點的狀態 若起點到第i個頂點的最短距離已經被找出來則FLAG[i]=1 否則FLAG[i]=0 利用一個一維陣列DIST[N]來存放從起始頂點到達頂點i之最短路徑 資料結構導論 - C語言實作

7.6.1 單一頂點到其他頂點之最短距離 設定成本矩陣COST之起始值，即對於每一個邊，令 COST[i][j]=邊<i,j>之距離，若<i,j>E COST[i][j]=∞ ，若<i,j>E 設定FLAG和DIST兩矩陣之初值，即對每一頂點i FLAG[i]=0 DIST[i]=COST[s][i]，其中s是起始頂點 資料結構導論 - C語言實作

7.6.1 單一頂點到其他頂點之最短距離 處理起始頂點s，設定 選取一個頂點 x，使得 x 是所有未被選取之頂點中DIST[x]是最少者 cnt = 1 FLAG[s]=1 DIST[s]=0 選取一個頂點 x，使得 x 是所有未被選取之頂點中DIST[x]是最少者 DIST[x] = min {DIST[y]} 其中FLAG[y] = 0 資料結構導論 - C語言實作

7.6.1 單一頂點到其他頂點之最短距離 處理挑選出的頂點x，設定 更新尚未被選取的頂點(FLAG[y]=0)之距離矩陣值，即令 FLAG[x]=1 cnt = cnt + 1 更新尚未被選取的頂點(FLAG[y]=0)之距離矩陣值，即令 DIST[y]=min｛DIST[y]，DIST[x]+COST[x][y]｝ 當cnt < N 時重複步驟(4)-(6) 資料結構導論 - C語言實作

7.6.1 單一頂點到其他頂點之最短距離 網路圖 G G 的成本相鄰矩陣 資料結構導論 - C語言實作

7.6.1 單一頂點到其他頂點之最短距離 資料結構導論 - C語言實作

7.6.1 單一頂點到其他頂點之最短距離 資料結構導論 - C語言實作

7.6.2 任意兩頂點之最短距離 有向網路圖形中，要找出任意兩個頂點的最短距離可以利用單一頂點到其他任何頂點的最短距離的做法 依序分別以每一個頂點當做起始頂點，便可找出任兩頂點的最短路徑和距離 資料結構導論 - C語言實作

7.6.2 任意兩頂點之最短距離 首先，我們會將給定有向網路G = (V,E)的所有頂點加以編號 假設有N個頂點，其編號依序為0, 1, 2, …, N-1 另外，我們利用一個二維的成本相鄰矩陣COST[N][N]來紀錄頂點間的距離 如果存在一個邊<i,j>E則將<i,j>之距離存入COST[i][j] 否則COST[i][j]=∞ 資料結構導論 - C語言實作

7.6.2 任意兩頂點之最短距離 為了找任兩個頂點i和j經過不同編號節點的最短距離，我們定義陣列AK[N][N] 其中個別元素AK[i][j]是頂點 i 到 j 的最短距離 其經過的頂點編號不超過K 定義A-1[i][j]=COST[i][j] 上述的二維陣列的它們具有一個重要的特性 AK[i][j]= min｛AK-1[i][j] , (AK-1[i][K] + AK-1[K][j])｝ , 0≦ k≦ N-1 資料結構導論 - C語言實作

7.6.2 任意兩頂點之最短距離 任兩頂點之最短距離 資料結構導論 - C語言實作

7.7 工作網路和拓樸排序 頂點工作網路(Activity On Vertex Network)，簡稱AOV網路 7.7 工作網路和拓樸排序 頂點工作網路(Activity On Vertex Network)，簡稱AOV網路 AOV 網路以及其對應相鄰矩陣表示法 資料結構導論 - C語言實作

7.7 工作網路和拓樸排序 立即先行者(Immediate Predecessor) 立即後繼者(Immediate Successor) 7.7 工作網路和拓樸排序 立即先行者(Immediate Predecessor) 立即後繼者(Immediate Successor) 拓樸排序的處理步驟 任選一個沒有先行者之頂點，將之輸出，並自AOV網路中刪除該頂點以及與該頂點相連接的邊 重複步驟(1)直到 AOV 網路的N個頂點皆已經被處理為止 資料結構導論 - C語言實作

7.7 工作網路和拓樸排序 拓樸排序 資料結構導論 - C語言實作