第 九 章 圖形結構 課程名稱：資料結構 授課老師：________ 2019/2/22.

Presentation on theme: "第 九 章 圖形結構 課程名稱：資料結構 授課老師：________ 2019/2/22."— Presentation transcript:

1 第 九 章 圖形結構 課程名稱：資料結構 授課老師：________ 2019/2/22

2 本章學習目標 1.讓讀者了解圖形結構的相關專有名詞。 2.讓讀者了解圖形的表示方式及追蹤方法。 2019/2/22

3 本章內容 9-1 圖形理論的起源 9-2 圖形 ( Graph ) 9-3 圖形的表示法 9-4 加權圖形 9-5 圖形的走訪方式
9-6 擴張樹 ( Spanning Tree ) 9-7 最小成本擴展樹 ( Minimum Cost Spanning Tree ) 9-8 最短路徑 ( shortest path ) 9-8 拓樸排序 ( Topological Sort ) 2019/2/22

4 9-1 圖形理論的起源 圖形的理論是起源於西元十八世紀，有一位數學家尤拉（Eular）為了解決「肯尼茲堡橋樑」問題，而想出的一種資料結構理論。而所謂的「肯尼茲堡橋樑」問題是：某一個人由某地點出發，最後再回到原出發點，必須要經過每一座橋，並且只能經過一次。如圖9-1所示： 2019/2/22

5 數學家尤拉（Eular）當時所使用的方法就是，利用頂點（Vertices）來表示每塊土地，邊（Edge）代表每一座橋樑，如圖9-2所示：
2019/2/22

6 在圖9-2中，尤拉所找出的規則就是「如果每個頂點的分支度皆為偶數時，才能從某一個頂點出發，經過每一個邊後，再回到出發的頂點。」而肯尼茲堡的情況為，四個頂點的分支度都是奇數（A的分支度為5，B的分支度為3，C的分支度為3，D的分支度為3），所以最後的結論：就是肯尼茲堡的人不可能走過所有的橋樑，到過每個地方，而後又回到肯尼茲堡。 2019/2/22

7 9-2 圖形 ( Graph ) 【定義】 圖形(Graph)是由頂點(Vertices)和邊(Edges)所組成，以G=(V,E)來表示；其中V為所有頂點的集合，E為所有邊的集合。說明如下： V: Vertex（點、節點、頂點），V(G)={V1,V2,V3,…,Vm}，其中 m>0 E: Edge（邊、連線），E(G)={E1,E2,E3,…,En}，其中n>0 2019/2/22

8 一般而言，我們可以將圖形結構分為無向圖形(Undirected Graph)與 有向圖形(Directed Graph)兩種，其說明如下：
(1) 邊(Edges)是沒有方向性的。 (2) 邊(V1,V2)與邊(V2,V1)是相同的。 2. 有向圖形(Directed Graph) (1) 邊(Edges)是有方向性的。 (2) 邊<V1,V2>與邊<V2,V1>是不相同的。 (3) <V1,V2>，其中V1為頭(head)，V2為尾(tail)，方向為：從V1指向V2 2019/2/22

9 【舉例】在下圖(A) 無向圖形中，其頂點(Vertices)和邊(Edges)的表示方式如下： V(G)={A,B,C,D,E}
E(G)={(A,B),(A,C),(B,A),(B,D),(C,A),(C,E),(D,B) ,(D,E) ,(E,C) ,(E,D)} 上圖(A)稱為「無向圖形」，因為它的邊是沒有方向性的， 沒有方向性的邊以( )表示； 2019/2/22

10 而圖(B)稱為「有向圖形」則是每邊都是有方向性， 以<>來表示。 表示方式為： V(G)={A,B,C,D,E}
E(G)={<A,B>,<A,C>,<B,D>,<C,E>,<D,E>} 2019/2/22

11 關於自身迴路(Self Loop)與重邊(Multi Edges)的情形，都屬於非圖形結構， 在本章節中不加以討論。
2019/2/22

12 以下是介紹圖形結構中常用到的專有名詞： 1. 完整圖形 ( complete graph )
(1)在「無向圖形」中，若有n個頂點，並且恰好有n(n-1)/2個邊， 則稱為「完整圖形」。 (2)在「有向圖形」中，若有n個頂點，並且恰好有n(n-1)個邊，則 稱為「完整圖形」。 2019/2/22

13 2. 路徑 ( path ) 在圖形 G 中，相異兩點間所經過的邊稱為路徑，如圖9-5之圖(A)中，A到E的路徑有{(A,B), (B,E)}、{(A,C), (C,E)}及{(A,B),(B,D),(D,E)}等路徑，它不只有一條路徑。 2019/2/22

14 3. 簡單路徑 ( simple path ) 指除了起點(第一個節點)與終點(最後一個節點)外的所有節點都不相同的路徑。亦即路徑不會有循環現象。如果起點及終點為同一個點的簡單路徑稱為循環。如圖9-5之圖(A)中，{(A,B),(B,D),(D,E),(E,C),(C,A)}起點及終點都是A，所以是一個循環路徑。 上圖的頂點 A 為簡單路徑，路徑 C , E , B 為簡單路徑， 路徑 B , D , E  ,  B 就不是簡單路徑。 2019/2/22

15 4. 循環路徑 ( cycle )又稱：迴圈 指最先和最後頂點相同的路徑。例如下圖的B , D , E  ,  B 。 2019/2/22

16 5. 子圖（Sub-graph） 若 G’=(V’,E’) 是 G=(V,E) 的子圖，則V’V與E’E 2019/2/22

17 7. 連通圖形（Connected Graph）
在無向圖形中，若頂點Vi到頂點Vj間存在路徑，則Vi和Vj是相連的。 7. 連通圖形（Connected Graph） 如果圖形G中，任兩個頂點均為相連，則此圖形稱為相連圖形，否則稱為非相連圖形。 2019/2/22

18 8. 連通單元（Connected Component）
圖中最大的連通子圖（Maximal Connected Subgraph），下圖可以視為2個連通單元。 2019/2/22

19 9. 緊密連通（Strongly Connected）
有相向圖形（Directed Graph）之中，任一個頂點<Vi,Vj> 之間都有一條從 Vi 到 Vj 的路徑並且也有一條從Vj到 Vi的路徑（Directed Graph） 2019/2/22

20 10. 相鄰（Adjacent） (1)無向圖G=(V,E) u,vV，(u,v)E，其中u,v代表相異兩個頂點
稱 u 相鄰至（Adjacent To）v 稱 v 相鄰自（Adjacent From）u 2019/2/22

21 11. 路徑長度（Path Length） 路徑長度 k 代表路徑上的邊（Edge）的數量。 2019/2/22

22 12.分支度（Degree） (1)無向圖G=(V,E) 頂點 u 的分支度=附著於 u 的邊的總數，如圖9-3之圖(A)中A頂點
的分支度為2。 (2)有向圖G=(V,E) 入分支度 ( in - degree )：指某一個頂點v擁有「箭頭」的邊數。如 圖9-3之圖(B)中，A 頂點的入分支度為0，而E頂點的入分支度為 2。（亦即箭頭指向 v） 出分支度 ( out - degree )：剛好和入分支度相反，指的是某一頂點 v擁有「尾」的邊數。如圖9-3之圖(B)中，A頂點的出分支度為2， 而E頂點的出分支度為0。（亦即箭頭從 v 指出去） 2019/2/22

23 【牛刀小試】請問下列圖形為何種結構？ 【解答】 (1)樹狀結構 (2)圖形結構 (3)非連通圖的圖形結構 (4)不是圖形結構
(5)不是圖形結構 2019/2/22

24 9-3 圖形的表示法 基本上，圖形的表示法有四種常見的方式，分別為：相鄰矩陣(Adjacency Matrix)、相鄰串列(Adjacency Lists)、相鄰多元串列(Adjacency Multi lists)及索引表格(Indexed Table)。 2019/2/22

25 9-3.1 相鄰矩陣 ( Adjacency Matrix )
【定義】 若圖形G = ( V , E ) 是具有 n 個頂點的圖形，並且n >= 1時，則要表示圖形G 的相鄰矩陣，我們可以利用一個 n × n 的二維陣列來表示，稱其為相鄰矩陣 ( adjacency matrix ) 。 【特性】 1. 矩陣A[i][j] = 0 表示邊E(i,j)不存在 2. 矩陣A[i][j] = 1 表示邊E(i,j)存在 3. 無向圖的相鄰矩陣以對角線對稱，A[i][j]=A[i][j] 2019/2/22

26 2019/2/22

27 對無向圖形而言，任一頂點i的分支度是各列或各行之和。 例如：在上圖(A)無向圖形的相鄰矩陣中，頂點1的支度為4。
在上圖(A)無向圖形的相鄰矩陣中，若A[i][j]=1時，則代表圖形G中有一條邊(Vi,Vj)存在。反之，若A[i][j]=0時，則代表圖形G中沒有一條邊(i,Vj)存在。 對無向圖形而言，任一頂點i的分支度是各列或各行之和。 例如：在上圖(A)無向圖形的相鄰矩陣中，頂點1的支度為4。 2019/2/22

28 在上圖(B)有向圖形的相鄰矩陣中，若A[i][j]=1時，則代表圖形G中有一條邊<Vi,Vj>存在。反之，若A  [i][j]=0時，則代表圖形G中沒有一條邊<Vi,Vj>存在。
2019/2/22

29 特別注意一點就是，在無向圖形中的相鄰矩陣就是一種「對稱矩陣」，因此，為了節省記憶體空間，我們可以只儲存上三角或下三角即可。但是，有向圖形的相鄰矩陣，則不一定會是「對稱矩陣」。
2019/2/22

30 【老師上課動態展示】檔案在附書光碟中。 2019/2/22

31 9-3.2 相鄰串列 (Adjacency Lists)
【定義】 假設圖形G=(V,E)包含n個頂點(n≧1)時，則我們可以使用n個鏈結串列來存放該圖形，每個鏈結串列分別代表一個頂點及其相鄰的頂點。而以串列結構來表示圖形，它有點類似相鄰矩陣，不過忽略掉矩陣中0的部份，直接把1的部份放入節點裡。 2019/2/22

32 2.在無向圖中，n個頂點e條邊共需n個串列首節點及2*e個節點； 有向圖則需n個串列首節點及e個節點。在相鄰串列中，計算所有
【特性】 1.每一個頂點使用一個串列。 2.在無向圖中，n個頂點e條邊共需n個串列首節點及2*e個節點； 有向圖則需n個串列首節點及e個節點。在相鄰串列中，計算所有 頂點分支度所需的時間複雜度Ｏ(n+e)。 2019/2/22

33 【節點結構】 在相鄰串列中所使用的節點結構是由2個欄位所組成，分別為頂點 欄位及指標欄位。如下圖所示： 頂點欄位 指標欄位
頂點欄位 指標欄位 2019/2/22

34 【實例1】請將下面的無向圖形( undirected graph )轉成相鄰串列。
說明：在無向圖中，5個頂點7條邊共需5個串列首節點及14個節點， 因此，在無向圖形中，節點數目為邊數的2倍。 【解答】 2019/2/22

35 【實例2】請將下面的有向圖形( directed graph )轉成相鄰串列。
說明：在有向圖中， 5個頂點7條邊共需5個串列首節點及7個節點， 因此，在有向圖形中，節點數目恰等於邊數。 2019/2/22

36 9-4 加權圖形 在上面的例子中，圖形上的每一個邊都沒有任何的權重，亦即任一頂點到其他頂點之間的關係強度都是相同的。但是，當我們要表示的資料與資料之間的關係強度是有不同時，那就必須要利用到加權圖形來呈現。何謂加權圖形呢？它是在圖形上的每一個邊上都給予一個權重值(weight)，此權重值可以用來表示距離、成本、時間或關係強度等等，如圖9-6中頂點1與頂點2之間邊的加權值為6。 2019/2/22

37 9-4.1 加權圖形的相鄰矩陣之表示法 假設以加權圖形表示法來表示相鄰矩陣 ，這與前面介紹的相鄰矩陣略有一些些不同，前面所介紹的圖形表示法是以兩個頂點之間若有相連，則以”1”來表示，若無，則以”0”。而在加權圖形中相異兩個頂點若有相連，則以加權值來表示之，若無，則以” ”來表示。以圖9-6的加權圖形為例，將它轉換成加權圖形的相鄰矩陣之表示法： 2019/2/22

38 9-4.2 加權圖形的相鄰串列之表示法 在利用相鄰串列來表示加權圖時，其相鄰串列的結構必須要再加上一個「權重欄位」來存放加權值。如下圖所示：
以圖9-6的加權圖形為例，將它轉換成加權圖的相鄰串列之表示法： 2019/2/22

39 9-5 圖形的走訪方式 樹有前序法、中序法和後序法三種走訪(追蹤)方式，圖形的走訪和樹的走訪概念相同，都是要能夠走訪到所有頂點。圖形的走訪方法有深度優先搜尋法（Depth-First-Search，DFS）和廣度優先搜尋法（Breadth-First-Search，BFS）。 2019/2/22

40 9-5.1 深度優先搜尋法 ( Depth-First Search ; DFS )
【定義】 1.深度優先搜尋法是利用「堆疊(Stack)」來處理。 2.先深後廣的方式是從圖形的某一頂點開始走訪，被拜訪過的頂點 就會被標示已拜訪的記號。接著走訪此一頂點的所有相鄰並且未 拜訪過的頂點中的任意一個頂點，並標示已拜訪的記號，再以該 點為新的起點繼續進行先深後廣的搜尋。 2019/2/22

41 【作法】 (1)先拜訪起始頂點 V。 (2)接著再選擇與頂點V 相鄰而且尚未被拜訪過的頂點 W ，以 W 為 起始點來做深入搜尋。
(3) 若有一頂點其相鄰的頂點皆被拜訪過時，就退回到最近曾拜訪 過之頂點，繼續執行深入搜尋。 (4) 若從任何已走過的頂點，皆無法再找到未被走過的相鄰頂點 時，此搜尋就結束了。 2019/2/22

42 【以堆疊 ( Stack ) 來實作】 假設現在有一個圖形，如下所示：
上圖經深度優先搜尋法處理後，其輸出為： 1 , 2 , 4 , 8 , 5 , 6 , 3 , 7 以堆疊的處理情形如下所示： 2019/2/22

43 2019/2/22

44 2019/2/22

45 2019/2/22

46 2019/2/22

47 9-5.2 廣度優先搜尋法 ( Bradth First Search ; BFS )
【定義】 1. 先廣後深搜尋法則是以「佇列(Queue)」及「遞迴」技巧來走訪。 2. 先廣後深的方式是從圖形的某一頂點開始走訪，被拜訪過的頂點就 會被標示已拜訪的記號。接著走訪此一頂點的所有相鄰並且尚未拜 訪過的頂點中的任意一個頂點，並標示已拜訪的記號，再以該點為 新的起點繼續進行先廣後深的搜尋。 2019/2/22

48 【作法】 1. 首先準備一個佇列為Qu 2. 再將起始頂點 v 加入到 Qu 之中（亦即進行Enqueue動作）
3.1 從 Qu中取出一頂點 w（亦即進行Dequeue動作） 3.2 並將 w 標示為『已拜訪過』 3.3 將所有與 w 相鄰且尚未標示『已拜訪過』的頂點加入到 Qu 之中 （亦即進行Enqueue動作） 3.4 回到步驟 3 4. 結束 2019/2/22

49 【以佇列(Queue)實作】 假設現在有一個圖形，如下圖所示： 以佇列的處理情形如下所示： 2019/2/22

50 2019/2/22

51 2019/2/22

52 2019/2/22

53 9-5.3 DFS與BFS比較 1.深度優先搜尋法（DFS）以深度（路徑長度）優先，可以用「遞迴 」和「堆疊」控制要走訪的頂點。
2019/2/22

54 9-5.4 DFS與BFS應用 圖形的走訪可應用於下列幾項： 1.找出一個無向圖形的擴張樹（spanning tree）
2.判斷無向圖形是否為一個相連圖形（connected graph） 3.找出一個無向圖的相連子圖 2019/2/22

55 9-6 擴張樹 ( Spanning Tree ) 由前一節介紹的深度優先法和廣度優先法得知，如果是一個有n個頂點的相連圖形，經由這兩種演算法走訪的結果，會得到用最少的邊來連結所有的頂點，且不會形成迴路，這樣的子圖是一種樹狀結構，也就是任何兩頂點之間的路徑唯一，這種可連結所有頂點且路徑唯一的樹狀結構稱為擴張樹（spanning tree）或稱生成樹、擴展樹，它可應用在許多方面，例如頂點代表鄉鎮，邊代表道路，原先的圖形是計畫中要興建的道路，但現在希望興建最少的道路，但還是可以讓所有的鄉鎮可通的情況下，則需要用到擴張樹。 2019/2/22

56 【定義】 假設G = (V,E)是一個圖形，而 S = ( V,T ) 是 G 的擴張樹。其中 T 是追蹤時所拜訪過的邊，而以K 表示追蹤後所未被拜訪過的邊，此時擴張樹具有下列幾點特性： 1. E = T + K。如圖9-7所示： 2. V 中的任何兩頂點 V1 及 V2 ，在 S 中有唯一的邊。 3. 加入 K 中任何一個邊於 S 中，會造成循環。如圖9-8所示： 2019/2/22

57 9-7 最小成本擴張樹 ( Minimum Cost Spanning Tree )
擴張樹在實際的應用上不止是找出頂點和邊而已，如果一個相連圖形的邊加上權重值（weight），來代表邊的成本、距離或關係強度時，則我們希望所產生的擴張樹之所有邊的權重值加總為最小，具有這樣性質的擴張樹稱為最小成本擴張樹（minimum-cost spanning tree）。 2019/2/22

58 2019/2/22

59 在上面的例子中，圖9-10之圖(1)深度優先度與圖(2)廣度優先度所找出的擴張樹，並不是最小擴張樹，因此，我們不能使用深度優先法或廣度優先法求最小成本擴張樹，接著介紹兩種著名的演算法-Kruskal演算法和Prime演算法(分別稱為K氏、P氏演算法）來求最小擴張樹，這兩種演算法都是使用「貪心策略」（greedy strategy）。 2019/2/22

60 Kruskal 演算法 【定義】 Kruskal 演算法每次挑選一個 Weight 最小的邊，加入到T中，並以形成最小成本 Spanning tree，但不可形成迴圈，直到數量達 n-1 個邊為止。這種演算法根據各邊的加權值大小，再由小到大排序後，再選取要加入 T 的邊。一個邊若與 T 原來已有的邊不會形成環路，即可加入 T 中，因為 G是連通的且有 n > 0 個頂點，所以恰有 n - 1 個邊會被選入 T 中。 2019/2/22

61 【作法】 假設有n個頂點的相連圖形，其Kruskal的演算步驟如下： 1.邊的權重值先由小到大排序。
2.從所有未走訪的邊中取出最小權重值的邊，記錄此邊已走訪，檢查是 否形成迴路。 (1)形成迴路，此邊不能加入MST中，回到步驟2。 (2)未形成迴路，此邊加入MST中，如果邊數已達（n-1）條則到 步驟3，否則回到步驟2。 3.Kruskal可以找出MST，結束。 2019/2/22

62 【實例】利用Kruskal 演算法來求出下圖的最小成本擴張樹。
2019/2/22

63 步驟1：將所有邊的權重值先由小到大排序 2019/2/22

64 2019/2/22

65 2019/2/22

66 2019/2/22

67 Prims 演算法 【定義】 假設有一個圖形G = (V,E) ，其中 V={1,2,3,...,n}，且最初設定 U={1}，U,V 是兩個頂點的集合，並且每次會產生一個邊。亦即從 U-V 集合中找一個頂點V，能與U集合中的某頂點形成最小成本的邊，把這一頂點V加入U集合，繼續此步驟，直到U集合等於V集合為止。 2019/2/22

68 【實例】利用Prims 演算法來求出下圖的最小成本擴張樹。
2019/2/22

69 2019/2/22

70 2019/2/22

71 2019/2/22

72 9-8 最短路徑 ( shortest path ) 最短路徑( shortest path )問題是目前圖形結構中常見的典型問題之一。因為圖形中某頂點到達各頂點的路徑不是唯一，如果要從眾多的路徑中找出路徑最短者，則稱為最短路徑問題，可分為兩種形式： 1.單點到其他各頂點之最短路徑。 2.各個節點之間之最短路徑。 2019/2/22

73 在單點到其他各頂點之最短路徑中，此問題的典型應用是由甲城市（頂點）到乙城市（頂點）之間的距離（權重值），計算由甲城市出發，經由多重交通網路的計算，到達乙城市的最短路徑，此種問題可行走的路徑，往往是有多條的，因此，我們必須要從這多條路徑中選擇最短路徑。一般而言，常用的方法是利用 Dijkstra's algorithm 求得。 2019/2/22

74 過程如下： 步驟 1 ： D[I] = A[F,I] ( I = 1 , N ) S = { F }
　　V = { 1 , 2 , 3 , .... , N } 　　其中：D為 N 個位置的陣列，用來儲存某一頂點到其他頂點的最短距離。 F 表示由某一起始點開始。 A[ F,I ] 是表示 F 點到 I 點的距離。 V 是網路中所有頂點的集合。 S 也是頂點的集合。 2019/2/22

75 從 V-S 集合中找一頂點 t 使得 D[t] 是最小值，並將 t 放入 S 集合，一直到 V-S 是空集合為止。 步驟 3 ：
步驟 2 ： 　　 從 V-S 集合中找一頂點 t 使得 D[t] 是最小值，並將 t 放入 S 集合，一直到 V-S 是空集合為止。 步驟 3 ： 　　根據下面的公式調整 D 陣列中的值。 　　D[I] = min(D[I],D[t]+A[t,I]) 　　此處 I 是指 t 的相鄰各頂點。 　　繼續回到步驟 2 執行。 2019/2/22

76 【實例】 求下圖的最短距離？其路徑為何？ 2019/2/22

77 2019/2/22

78 2019/2/22

79 2019/2/22

80 2019/2/22

81 2019/2/22

82 2019/2/22

83 <二>求最短路徑 2019/2/22

84 2019/2/22

85 2019/2/22

86 9-9 拓樸排序( Topological Sort )
所謂「工作(Activity)」是指將一個計劃分成數個子計劃，而每一個子計劃完成時，即是整個計劃的完成，這個就稱為工作。因此，如果我們將「工作」稱為工作網路上的「頂點」，而工作與工作之間的連線，代表著工作的優先順序時稱為工作網路上的「邊」。因此，這種以頂點來代表工作項目的網路稱為頂點工作網路(Activity On Vertex Network)，簡稱為AOV網路。 2019/2/22

87 【定義】 若在 AOV網路 中，Vi 是 Vj 的前行者，則在線性的排列中，Vi 一定在 Vj 的前面，此種特性稱之為拓樸排序 ( Topological Sort ) 。尋找 AOV網路之拓樸排序的過程如下： (１) 在 AOV網路中任意挑選一個沒有前行者的頂點。 (２) 輸出此頂點，並將該頂點所連接的邊刪除。重覆步驟 (１) 及步驟 ，一直到全部的頂點皆輸出為止。 2019/2/22

88 【應用】 這種事件應用的例子很多，例如：大專院校的選課資訊系統先修或擋修等限制、政府部門的公文有層層呈報和會簽的流程、資訊系統開發及專案管理等。 2019/2/22

89 【範例】 求下面 AOV網路之拓樸排序 2019/2/22

90 2019/2/22

91 2019/2/22

92 2019/2/22