Microsoft PowerPoint - Graphs

Size: px

Start display at page:

Download "Microsoft PowerPoint - Graphs"

符估严
5 years ago
Views:

1 資料結構的圖形結構 (Graphs) 資訊科技系林偉川圖形的基本觀念在日常生活中, 我們常常將複雜觀念或問題使用圖形來表達, 例如 : 在進行系統分析電路分析電話佈線和企劃分析等因為圖形化可以讓人更容易了解, 所以圖形 (Graph) 是資料結構一種十分重要的結構例如 : 城市之間的公路圖, 如下圖所示 : 2

2 圖形的基本定義圖形是由有限的點和邊線集合所組成, 其定義如下所示 : 定義 8.: 圖形 G 是由 V 和 E 兩個集合組成, 寫成 : G = ( V, E ) V: 點 (Vertices) 組成的有限非空集合 E: 邊線 (Edges) 組成的有限集合, 這是成對的點集合圖形通常使用圓圈代表點, 點之間的連線是邊線 3 圖形的基本圖例圖形通常使用圓圈代表點, 點之間的連線是邊線例如 : 上述公路圖繪成的圖形 G 和另一個樹狀圖形 G2, 如下圖所示 : 4 2

3 圖形的基本表示法圖形一共擁有 5 個點 V V2 V5,V(G) 是圖形 G 的點集合,V(G2) 是圖形 G2, 如下所示 : V(G) = { V, V2, V3, V4, V5 } V(G2) = { V, V2, V3, V4, V5 } 圖形 G 點和點之間的邊線有 6 條,G2 有 4 條,E(G) 是圖形 G 的邊線集合,E(G2) 是圖形 G2, 如下所示 : E(G) = { (V,V2),(V,V3),(V2,V3),(V2,V4),(V3,V5),(V4,V5) } E(G2) = { (V,V2),(V,V3),(V2,V4),(V2,V5) } 上述邊線是使用括號括起的兩個點, 例如 :(V,V2) 表示從點 V 到 V2 存在一條邊線 5 圖形的基本圖形種類圖形是由點和邊線所組成, 依邊線集合 E(G) 中點是否擁有順序性, 可以分為兩種, 如下所示 : 無方向性圖形 (Undirected Graph): 圖形的邊線沒有標示方向的箭頭, 邊線只代表點間是相連的例如 : 圖形 G 和 G2 是無方向性圖形, 所以 (V,V2) 和 (V2,V) 代表同一條邊線方向性圖形 (Directed Graph): 在圖形的邊線加上箭號標示點間的順序性 6 3

4 方向性圖形的基本觀念圖形 G3 是方向性圖形,G3 圖形的點和邊線集合 V(G3) E(G3), 如下所示 : V(G3)={ V, V2, V3, V4, V5 } E(G3)={ <V,V2>,<V,V3>,<V2,V3>,<V3,V2>,<V2,V4>,<V4,V5 >,<V5,V3> } 7 圖形術語路徑 : 為連接兩點間的邊例如 : 圖形 G3 中 V 經由 <V,V2> 及 <V2,V4> 的邊到達 V4, 則其路徑為 (V,V2,V4) 路徑長度 : 兩點間其路徑上邊的個數例如 : 圖形 G3 中 V 到 V4 的路徑為 (V,V2,V4), 其路徑長度為 2 8 4

5 圖形術語簡單路徑 (Simple Directed Path): 除了第個和最後個點可以相同外, 其它位在路徑上的點都不相同例如 : 圖形 G7 的路徑 <V5,V2> <V2,V>, 寫成 :5,2, 是簡單路徑, 路徑 5,2,,4,2, 就不是簡單路徑循環 (Cycle): 屬於簡單路徑的一種特例, 也就是第個和最後個點是同一個點的路徑例如 : 圖形 G7 的路徑 5,2,4,5, 第個和最後個點都是 5 9 圖形術語相連圖形 (Connected Graph): 圖形內任何兩個點都有路徑相連結例如 : 圖形 G G2 G3 G4 G5 和 G6 是相連圖形不相連圖形 (Disconnected Graph): 圖形內至少有兩個點間是沒有路徑相連的例如 : 圖形 G7 的點 3 完整圖形 (Complete Graph): 一個 n 點的無方向性圖形擁有 n(n-)/2 條邊線, 例如 :4 點的完整圖形 G4 擁有 6 條邊線子圖 (Subgraph): 圖形 G 的子圖 H, 是指 G 的點包含或等於 H 的點,G 的邊線包含或等於 H 的邊線, 例如 : G5 和 G6 是 G4 的子圖 5

6 圖形術語入支度 (In-degree): 有向圖中連向某點箭頭的邊線數例如 : 圖形 G7 點的入支度是 (2), 點 2 的入支度是 2 (4,5) 出支度 (Out-degree): 與內分支度相反, 指某點連向其他點的邊線數例如 : 圖形 G3 點 2 出支度是 2(3,4) 分支度 (Degree): 若為無向圖, 則分支度表示附著在點的邊數, 若為有向圖, 則分支度為入支度與出支度的總和例如 : 圖形 G3 點 2 分支度是 4 鄰接 (Adjacent): 如果兩個點間擁有一條邊線連結, 則這兩個點稱為鄰接圖形的表示法圖形結構可以使用多種方法來實作, 常用的方法有二種, 如下所示 : 鄰接矩陣表示法 (Adjacency Matrix) 鄰接串列表示法 (Adjacency Lists) 2 6

7 鄰接矩陣表示法圖形 G = (V, E) 是一個包含 n 個點的圖形, 可以使用一個 n * n 矩陣來儲存圖形, 在 C 語言是宣告一個 n * n 的二維陣列, 索引值代表點, 陣列元素值表示沒有邊線, 表示有邊線陣列 A 中若圖之點 Vi 與點 Vj 相鄰, 即存在邊線 (Vi,Vj), 則 A[i][j]=, 否則 A[i][j]=, 若 (V i,v j ) E( G) A[ i][ j] =, 若 (V i,v j ) E( G) 3 鄰接矩陣表示法 - 圖例無方向圖形 G 的鄰接矩陣表示法使用 5*5 的二維陣列儲存矩陣, 如果點 V 和 V2 鄰接, 陣列元素 (V,V2) 和 (V2,V) 的值是, 表示圖形包含點 V 到 V2 和點 V2 到 V 的路徑, 如下圖所示 : 4 7

8 鄰接矩陣表示法由鄰接矩陣很容易判斷是否有一邊線連接兩點, 對無向圖而言, 任一點 i 的列和為分支度對有向圖而言, 為出支度與各行和為入支度, 分支度為列與行的和 5 鄰接矩陣表示法圖形中不能有自己循環, 即點 Vi 至 Vi 不可能有邊的存在, 所以鄰接矩陣之 A[i][i]=, 即對角線元素皆為若為無向圖, 邊 (Vi,Vj) 存在表示 A[i][j]=A[j][i]=, 亦即無向圖之鄰接矩陣為一對稱矩陣, 故只需保存上三角或下三角部份即可, 大約可節省一半以上的空間對於有向圖則不一定是對稱的 6 8

9 鄰接矩陣表示法 - 標頭檔 2: #define MAX_VERTICES 6 3: int graph[max_vertices][max_vertices]; 4: /* 抽象資料型態的操作函數宣告 */ 5: extern void creategraph(int len, int *edge); 6: extern void printgraph(); 鄰接串列表示法鄰接串列表示法的圖形是使用單向串列來鏈結每個點的鄰接點, 使用一個點的結構陣列指標指向各點的鄰接點串列例如 : 無方向圖形 G 的鄰接串列表示法, 如下圖所示 : 8 9

10 鄰接串列表示法 - 標頭檔 2: #define MAX_VERTICES /* 圖形的最大點數 */ 3: struct Vertex { /* 圖形點結構宣告 */ 4: int data; /* 點資料 */ 5: struct Vertex *next; /* 指下一個點的指標 */ 6: }; 7: typedef struct Vertex *Graph; /* 圖形的新型態 */ 8: struct Vertex head[max_vertices]; 9: /* 抽象資料型態的操作函數宣告 */ : extern void creategraph(int len, int *edge); : extern void printgraph(); 2: extern void dfs(int vertex); 3: extern void bfs(int vertex); 9 鄰接串列表示法來建立圖形函數 creategraph() 首先使用 for 迴圈初始點結構陣列 head[],next 指標都是指向 NULL, 讀入的第一條邊線是 (, 2), 從點連到點 2, 所以建立結尾點 2 的節點指標 newnode, 如下圖所示 : 2

11 鄰接串列表示法來建立圖形然後將節點插入結構陣列 head[] 索引 ( 即點 ) 的串列最後, 如下圖所示 : 2 鄰接串列表示法來建立圖形繼續讀入的邊線是 (2, ), 從點 2 連到點, 插入的是結構陣列 head[] 索引值 2 的串列最後, 如下圖所示 : 等到讀完所有邊線, 就可以完成圖形 G 的鄰接串列表示法 22

12 2 23 鄰接串列表示法來顯示圖形函數 printgraph(): 顯示圖形函數 printgraph() 使用迴圈走訪 head[] 陣列顯示鄰接串列表示法, 在取得每一個點串列的串列指標後, 使用 while 迴圈走訪串列的每一個節點, 如下所示 : while ( ptr!= NULL ) { printf("v%d ", ptr->data); ptr = ptr->next; } 24 圖形的走訪圖形結構與之前的二元樹和鏈結串列一樣, 都擁有特定的走訪方式例如 : 一個無方向圖形 G9, 如下圖所示 : G

13 圖形的走訪圖形 G9 的鄰接串列表示法, 如下圖所示 : 25 圖形的走訪 - 種類圖形 G9 的走訪可以分為偏向直的深度或橫的寬度兩種搜尋法, 如下所示 : 深度優先搜尋法 (Depth-first Search, DFS): 當在鄰接串列表示法走訪某一點後, 優先找尋點在結構陣列中的鄰接點寬度優先搜尋法 (Breadth-first Search, BFS): 當在鄰接串列表示法走訪某一點後, 優先找尋點串列的所有鄰接點 26 3

14 深度優先搜尋法 DFS 圖形 G9 的深度優先搜尋法是從點開始以深度優先方式來走訪圖形, 首先走訪點, 找尋結構陣列索引值的鄰接點, 結果找到未走訪的點 2, 點 2 從深度方向往下走訪, 即走訪結構陣列索引值 2 的鄰接點, 找到未走訪過的點 4, 繼續再往下搜尋結構陣列索引值 4 的鄰接點, 可以找到未走訪過的點 8 從點 8 走訪結構陣列索引值 8 的鄰接點, 找到未走訪的點 5, 因為點 5 的鄰接點 2 和 8 已經走訪過, 所以再回到點 8, 繼續找到點 6, 接著從結構陣列索引值 6 找到鄰接點 3, 最後找到點 7, 可以得圖形走訪的點順序, 如下所示 : 深度優先搜尋法 DFS- 演算法深度優先搜尋法的遞迴函數 dfs(v) 的操作步驟, 如下所示 : Step : 設定點 V 已走訪過, 為走訪過 visited[vertex] = ; Step 2: 如果點 V 存在有鄰接點 W 未被走訪過, 遞迴呼叫函數 dfs(w) while ( ptr!= NULL ) { if ( visited[ptr->data] == ) dfs(ptr->data); ptr = ptr->next; } 28 4

15 寬度優先搜尋法 BFS 圖形 G9 的寬度優先搜尋法與深度優先搜尋法走訪圖形的差別在於走訪點後, 接著是走訪點的所有鄰接點, 即點 2 和 3, 然後才從點 2 和 3 開始走訪所有鄰接且未走訪過的點, 點 2 走訪點 4 和 5, 點 3 走訪點 6 和 7, 最後走訪點 8 整個寬度優先搜尋法走訪圖形的順序如下所示 : 寬度優先搜尋法 BFS 演算法寬度優先搜尋法的函數 bfs(v) 的操作步驟, 如下所示 : Step : 設定點 V 已經走訪過, 為走訪過 visited[vertex] = ; Step 2: 將點 V 存入佇列 enqueue(vertex); 3 5

16 寬度優先搜尋法 BFS 演算法 Step 3: 執行迴圈直到佇列空了為止, 如下 : while (!isqueueempty() ) { () 取出佇列的點 V vertice = dequeue(); ptr = head[vertex].next; (2) 將點 V 所有鄰接且未走訪的點 W 存入佇列, 且設定已走訪 while ( ptr!= NULL ) { if ( visited[ptr->data]== ) { enqueue(ptr->data); visited[ptr->data] = ; printf("[v%d] ", ptr->data); } ptr = ptr->next; } } 3 擴張樹擴張樹 (Spanning Trees) 是將無方向性圖形的所有點使用邊線連接起來, 但邊線並不會形成迴圈, 擴張樹的邊線數將比點少, 因為再多一條邊線, 圖形就會形成迴圈例如 : 32 6

17 擴張樹範例一個擁有四個點六條邊線的圖形, 依擴張樹的定義, 可以得三棵不同的擴張樹, 如下圖所示 : 33 圖形走訪建立擴張樹擴張樹可以使用走訪的搜尋法來建立, 因為只需將圖形走訪過的點順序, 使用邊線一一連接起來, 就可以建立成擴張樹, 依照搜尋法的不同, 分成二種擴張樹, 如下所示 : 深度優先擴張樹 (DFS Spanning Trees) 寬度優先擴張樹 (BFS Spanning Trees) 34 7

18 深度優先擴張樹深度優先搜尋走訪圖形 G9 的點順序, 如下 :,2,4,8,5,6,3,7 現在只需將走訪經過的邊線保留下來, 就可以建立深度優先擴張樹, 如下圖所示 : 35 寬度優先擴張樹寬度優先搜尋走訪圖形 G9 的點順序, 如下 :,2,3,4,5,6,7,8 保留點走訪到點 2,3 的邊線, 點 2 走訪到 4,5, 點 3 走訪點 6,7, 點 4 走訪到點 8, 可以建立走訪的寬度優先擴張樹, 如下圖所示 : 36 8

19 加權圖形表示法圖形在解決問題時通常需要替邊線加上一個數值, 這個數值稱為權值 (Weights), 常見的權值有 : 時間成本或長度, 擁有權值的圖形稱為加權圖形, 一樣可以分別使用鄰接矩陣和鄰接串列來表示 37 加權圖形表示法例如 : 一個方向性圖形 G9, 如下圖所示 : 38 9

20 加權圖形鄰接矩列表示法以鄰接矩陣的加權圖形來說, 只需將原來儲存和的陣列元素換成各點間的權值如果點間無邊線連接, 就使用無窮大表示所以, 圖形 G9 的加權鄰接矩陣表示法, 如下圖所示 : 39 加權圖形鄰接串列表示法鄰接串列表示法的加權圖形只是在點結構新增成員變數 weight 儲存權值, 圖形 G9 的加權鄰接串列表示法, 如下圖所示 : 4 2

21 加權圖表示法圖形每一邊都附加一個數值, 此數值為此邊之加權, 則稱此圖為加權圖最低成本擴張樹從加權圖形建立的擴張樹因為邊線擁有權值, 所以可以計算邊線的權值和, 換句話說, 圖形建立的擴張樹會因連接的邊線權值不同, 而建立出不同成本的擴張樹, 因為各種建立方法會產生不同成本, 所以如何找出最低成本擴張樹 (Minimum-cost Spanning Trees) 就成為一個重要的問題 42 2

22 最低成本擴張樹樹狀結構是圖形的特例, 樹不允許循環, 且 n 個點的樹狀結構, 其邊數為 n- 一個圖形的擴張樹為其本身子圖, 且點皆相同如果一加權圖, 其邊線上的加權和稱為成本, 則擴張樹中其總加權值最低者, 是其最低成本擴張樹 43 最低成本擴張樹圖例例如 : 一個擁有權值的無方向性加權圖形 G 找出最低成本擴張樹, 如下圖所示 : 44 22

23 最低成本擴張樹 - 克魯斯卡演算法克魯斯卡 (Kruskal) 提出建立最低成本擴張樹的演算法, 首先將各邊線依權值從小到大排列, 如下表所示 : 45 最低成本擴張樹 - 克魯斯卡演算法接著從權值最低的一條邊線開始建立最低成本擴張樹, 其步驟如下所示 : Step : 選擇第一條最低權值的邊線 (, 2) 加入擴張樹, 如下圖所示 : 46 23

24 最低成本擴張樹 - 克魯斯卡演算法 Step 2: 選擇第二低權值的邊線 (2, 4) 加入擴張樹, 只需加入的邊線不會形成迴圈, 以此例邊線 (2, 4) 並不會形成迴圈 Step 3: 如果加入第三低權值的邊線 (, 4), 因為會形成迴圈, 所以選擇下一條不會形成迴圈的低權值邊線 (3, 5), 如下圖所示 : 47 最低成本擴張樹 - 克魯斯卡演算法 Step 4: 邊線 (2, 5) 也不會形成迴圈, 將邊線 (2, 5) 加入擴張樹, 現在所有點都已經連接, 建立的就是一棵最低成本擴張樹, 如下圖所示 : 48 24

25 最低成本擴張樹 - 實作最低成本擴張樹的實作是以權值從小到大使用單向鏈結串列儲存圖形的邊線點和權值, 如下圖所示 : 49 最低成本擴張樹 - 標頭檔 2: #define MAX_VERTICES 6 /* 最大點數加一 */ 3: struct Edge { /* 圖形邊線結構宣告 */ 4: int from; /* 開始點 */ 5: int to; /* 終點點 */ 6: int weight; /* 權值 */ 7: struct Edge *next; /* 指下一條邊線 */ 8: }; 9: typedef struct Edge *EdgeList; /* 邊線的結構新型態 */ : EdgeList first = NULL; /* 邊線串列開始指標 */ : int vertex[max_vertices]; /* 檢查迴圈的點陣列 */ 2: /* 抽象資料型態的操作函數宣告 */ 3: extern void createedge(int len, int *edge); 4: extern void minspantree(); 5: extern void addset(int from, int to); 6: extern int issameset(int from, int to); 5 25

26 最低成本擴張樹 - 演算法函數 minspantree() 使用邊線的單向鏈結串列找出最低成本擴張樹, 其操作步驟如下所示 : Step : 走訪邊線的單向串列直到串列的結尾, 如下 : () 如果邊線不會形成迴圈且成本最小, 就將邊線加入擴張樹 if (!issameset(ptr->from,ptr->to) ) addset(ptr->from,ptr->to); (2) 移動指標到串列的下一條邊線節點 ptr = ptr->next; 5 圖形的應用 - 最短路徑最短路徑問題 (Shortest Paths Problems) 是指一個加權圖形 G = (V, E), 邊線的權值不是負值且擁有一個點為來源 (Source), 問題是找出來源點到其它點的各條路徑中, 各邊線權值和為最低的路徑, 也就是最短路徑最短路徑求法的常用方法有二種, 如下所示 : 一個點到多點的求法 (Dijkstra 演算法 ) 各點至其它點的求法 (Floyd 演算法 ) 52 26

27 一個點到多點的最短路徑從一個點到多點最短路徑的求法中, 最著名的是 Dijkstra 演算法例如 : 從基隆到高雄, 中間經過台北新竹台中或桃園, 各城市間的距離, 如下圖所示 : 53 一個點到多點的最短路徑點基隆到各點城市間的距離, 很明顯的! 可以發現基隆到新竹的最短路徑, 也是基隆到台中或高雄最短路徑的一部分, 也就是說, 已知的最短路徑點, 可能就是其它點最短路徑上經過的點, 如下表所示 : 54 27

28 Dijkstra 演算法的最短路徑 Dijkstra 演算法是依據上述最短路徑的特性, 提出解決單來源最短路徑的問題 (Single-source Shortest Paths) 的演算法,Dijkstra 演算法使用鄰接矩陣表示法建立圖形例如 : 圖形 G 的鄰接矩陣表示法, 如下圖所示 : 55 Dijkstra 演算法最短路徑的步驟 Dijkstra 演算法的完整操作步驟, 如下所示 : Step : 初始相關陣列的內容 : () 將 graph[source][i] 來源點複製到一維陣列 dist[i] (2) 設為 selected[i] 和 pi[i] 的陣列元素初值 Step 2: 執行點總數減次的迴圈來計算最短路徑, 如下所示 : () 走訪陣列 dist[] 找出最短距離的點 W, 且此點沒有選過 (2) 將點 W 設為選過, 即 selected[w] = (3) 走訪陣列 dist[], 如果有未選過的點 X, 則 : ) 比較 dist[x] 和 graph[w][x]+dist[w] 的距離大小 :»a. 如果 graph[w][x]+dist[w] 小, 存入 dist[x]»b. 如果更改距離, 指定點 X 的前點為 W,pi[X] = W 56 28

Dijkstra 演算法過程 Dijkstra 演算法計算圖形 G 來源點到其它各點最短路徑的過程, 如下表所示 : 57 最短路徑的第一次迴圈第一次迴圈搜尋陣列 dist[] 的最短距離點 W 是點 2 的 35, 然後走訪陣列 dist[], 將未選過的點 X:3 4 5 6, 依序計算下列公式, 如下所示 : MIN (dist(x),dist(w)+ 鄰接矩陣 (W,X))

29 Dijkstra 演算法過程 Dijkstra 演算法計算圖形 G 來源點到其它各點最短路徑的過程, 如下表所示 : 57 最短路徑的第一次迴圈第一次迴圈搜尋陣列 dist[] 的最短距離點 W 是點 2 的 35, 然後走訪陣列 dist[], 將未選過的點 X: , 依序計算下列公式, 如下所示 : MIN (dist(x),dist(w)+ 鄰接矩陣 (W,X)) MIN() 函數可以傳回兩個參數距離的最短距離如果 dist(w)+ 鄰接矩陣 (W,X) 比較短, 例如 : 點到點 3 的距離是 dist[3] = 9, 透過點 2 到點 3 的距離, 如下所示 : dist(2) + 鄰接矩陣 (2, 3) = dist[2] + graph[2][3] = = 8 距離 8 小於 dist[3] = 9, 所以更新 dist[3] = 8, 同時, 將 pi[3] 更新為 2, 表示點 3 最短路徑的前一個點 58 是 2 同理, 點 4 更新為 65 29

30 最短路徑的第二次迴圈第 2 次迴圈搜尋陣列 dist[] 的最短距離點 W 是點 4 的 65, 然後走訪陣列 dist[], 將未選過的點 X:3 5 6, 其中點 5 可由點 4 到達, 其距離為 : dist[4] + graph[4, 5] = = 更新 dist[5] =, 同時, 將 pi[5] 更新為 4, 表示點 5 最短路徑的前一個點是 4 重複上述操作, 執行點數減一次迴圈, 就可以完成點到其它點的最短路徑計算 59 找出最短路徑如何知道最短路徑經過哪些點? 可以從 pi[] 陣列得知例如 : 點到點 6 的路徑, 從 pi[6] 開始, 前一個點是 5,pi[5] = 3, 表示點 5 的前一個點是 3, 點 3 的前一個點是 2, 所以得到路徑 :,2,3,5,6 6 3

31 各點至其它點的最短路徑 R. W. Floyd 教授的演算法可以計算出各點至其它點的最短路徑例如 : 以上一節的加權圖形 G 為例,Floyd 演算法是將鄰接矩陣表示法的內容複製到二維陣列 dist[][], 如下圖所示 : 6 各點至其它點的最短路徑 Floyd 演算法使用迴圈重覆執行 n 次的點數,(i, j) 是矩陣座標, 走訪二維陣列的每一個元素來計算下列公式, 如下所示 : dist n (i,j)=min(dist n- (i,j),dist n- (i,n)+dist n- (n,j)) 上述 n 值是第 n 次執行迴圈 MIN() 函數, 函數找出兩個參數的最小值當計算出 dist n- 後, 在計算 distn(i,j) 時一共有兩種情況, 如下所示 : 沒有經過點 n: 最短距離仍然為 dist n- (i,j) 如果有經過點 n: 最短距離是比較 dist n- (i,n)+dist n- (n,j) 和 dist n- (i,j) 找出最小值, 經過點 n 的路徑就是從點 i 到 n 和點 n 到 j 62 3

32 各點至其它點之第一次迴圈現在執行第一次公式的計算, 如下所示 : dist (i,j) = MIN(dist (i,j),dist (i,)+dist (,j)) 上述 dist 是初始的二維陣列在計算每一個元素後的陣列內容, 如下圖所示 : 63 各點至其它點之第二次迴圈繼續第二次公式的計算, 如下所示 : dist 2 (i,j) = MIN(dist (i,j),dist (i,2)+dist (2,j)) 計算後的陣列內容, 如下圖所示 : 64 32

33 各點至其它點的執行完迴圈等到執行完全部迴圈一共是點數 6 次後, 就可以得到最後的二維陣列內容, 如下圖所示 : 65 拓樸排序 (AOV 網路與拓樸排序 ) 工作或作業計劃都需要分割成數個小計劃, 如果使用方向性圖形來表示各小計劃間的前後關連, 這種圖形稱為點工作網路 (Activity On Vertex Network), 簡稱 AOV 網路不過問題是每個小計劃或工作間都擁有關連, 所以準備進行某個小計劃前, 需要等到其它小計劃先行完成例如 : 主修資訊科學的學生, 在選修資料結構這門課前, 需要先修過 C 語言課程, 如果沒有修過 C 語言, 就不能選修資料結構換句話說, 因為課程有先後順序, 所以如何找出修課的先後順序, 而且不會造成先修課程尚未修過的擋修問題, 就是拓樸排序 (Topological Sort) 66 33

34 拓樸排序 (AOV 網路圖例 ) 例如 : 一個方向性圖形 G2 表示課程間的先後關連, 如下圖所示 : 67 拓樸排序 (AOV 網路圖例 ) 圖形 G2 是一個 AOV 網路, 其點代表課程, 點需要等到讀完點 3 和 2 的課程後, 才可以選修, 點 3 是其它點的先行者 (Predecessor), 點 2 是點 5 和 6 的立即先行者 (Immediate Predecessor) 點 4 的課程需要等到點,5,7 的課程都讀完, 它是圖形其它點的後繼者 (Successor), 點 5 和 7 的立即後繼者 (Immediate Successor) 68 34

35 拓樸排序 ( 拓樸排序演算法 ) 拓樸排序的圖形需要計算點的內分支度, 內分支度為的點表示沒有先修課程, 所以是課程的開始拓樸排序就是從內分支度為的點開始處理, 先輸出此點, 接著將點相連接的邊線刪除, 如下圖所示 : 69 拓樸排序 ( 拓樸排序演算法 ) 點 2 因為邊線已經刪除, 內分支度也成為, 輸出點 2 繼續將點 2 連接的三條邊線刪除, 如下圖所示 : 7 35

36 拓樸排序 ( 拓樸排序演算法 ) 現在點 5 和 6 的內分支度都是, 只需刪除這三個點和邊線, 輸出點 5 和 6 後, 如下圖所示 : 繼續上述操作, 刪除點 7, 最後輸出點 7 和 4, 就可以得到拓樸排序的結果, 如下所示 : 拓樸排序 ( 加權鄰接串列表示法 ) 圖形 G2 的加權鄰接串列表示法, 如下圖所示 : 72 36

37 拓樸排序 ( 拓樸排序演算法 ) Step : 走訪 head[] 陣列將內分支度為的點存入佇列 for ( i = ; i <= num; i++ ) if ( head[i].data == ) enqueue(i); Step 2: 從佇列取出點, 直到佇列空了為止, 如下 : while (!isqueueempty() ) { () 取出佇列元素, 輸出拓樸排序的點 vertex = dequeue(); printf(" %d ", vertex); (2) 走訪點的鄰接串列, 將所有鄰接點的內分支度減 ptr = head[vertex].next; while ( ptr!= NULL ) { vertex = ptr->data; head[vertex].data--; (3) 如果點減後的內分支度為, 將此點存入佇列 if ( head[vertex].data == ) enqueue(vertex); ptr = ptr->next; } } 73 拓樸排序 ( 擁有迴圈的 AOV 網路 ) AOV 網路輸出拓樸排序的條件是點間沒有循環路徑的迴圈, 如果 AOV 網路擁有迴圈, 就沒有辦法找出拓樸排序, 因為每一個計劃都在等待其它計劃的執行例如 : 在圖形 G2 加上 2 條邊線, 如下圖所示 : 74 37

38 拓樸排序 ( 擁有迴圈的 AOV 網路 ) 圖形擁有迴圈 , 拓樸排序無法輸出圖形的所有節點, 在輸出 3 2 後留下的圖形, 點 6 等待點 5, 點 7 等待點 6, 點 5 等待點 7, 循環等待其它計劃的完成, 換句話說, 這個計劃將無法完成, 如下圖所示 : 75 請寫出答案. 現有圖形如下三圖, 請將之以 V 和 E 兩個集合表示? 請寫出 G2 圖之 a-d 之簡單路徑? 路徑長為多少? 請寫出 G2 之循環為何? 請寫出 G2 G3 圖之各點入支度出支度分支度為何? 鄰接矩陣表示法為何? a a b c b c G d a e d G2 b c d G3 f 76 38

39 請寫出答案 2. 現有一個圖形之鄰接矩陣如下, 請畫出此圖? 並將之以 V 和 E 兩個集合表示? 請寫出右圖之各點入支度出支度分支度為何? 此圖共有幾邊? 請寫出答案. 現有一個圖形如下, 鄰接矩陣表示法為何? 深度優先搜尋法之次序為何? 寬度優先搜尋法之次序為何?{ } 2. 深度優先搜尋法之擴張樹為何? 寬度優先搜尋法之擴張樹為何?

40 請寫出答案現有一個加權圖如下, 並將之以鄰接矩陣表示?

Microsoft PowerPoint - DS&Algorithm [相容模式]

Microsoft PowerPoint - DS&Algorithm [相容模式] 資料結構與演算法陳怡芬什麼是 Data structure? 將資料群組織起來的抽象資料型態, 稱為資料結構典型的資料結構資料表格 (Table) 堆疊 (stack) 佇列 (queue) 串列 (list) 樹 (tree) 圖形 (graph) table, stack, queue: 可用陣列表現出來 List, tree, graph: 適合用指標表現出來堆疊 (Stack) 將資料依序從堆疊下面儲存起來,