第8章 圖形結構（Graphs） 8-1 圖形的基本觀念 8-2 圖形的表示法 8-3 圖形的走訪 8-4 擴張樹

Presentation on theme: "第8章 圖形結構（Graphs） 8-1 圖形的基本觀念 8-2 圖形的表示法 8-3 圖形的走訪 8-4 擴張樹"— Presentation transcript:

1 第8章 圖形結構（Graphs） 8-1 圖形的基本觀念 8-2 圖形的表示法 8-3 圖形的走訪 8-4 擴張樹
8-5 圖形的應用 - 最短路徑 8-6 圖形的應用 - 拓樸排序

2 8-1 圖形的基本觀念-說明 在日常生活中，我們常常將複雜觀念或問題使用圖形來表達，例如：在進行系統分析、電路分析、電話佈線和企劃分析等。因為圖形化可以讓人更容易了解，所以「圖形」（Graph）是資料結構一種十分重要的結構。例如：城市之間的公路圖，如下圖所示：

3 8-1 圖形的基本觀念-定義 圖形是由有限的頂點和邊線集合所組成，其定義如下所示： 圖形通常使用圓圈代表頂點，頂點之間的連線是邊線。
定義 8.1：圖形G是由V和E兩個集合組成，寫成： G = ( V, E ) V：「頂點」（Vertices）組成的有限非空集合。 E：「邊線」（Edges）組成的有限集合，這是成對的頂點集合。 圖形通常使用圓圈代表頂點，頂點之間的連線是邊線。

4 8-1 圖形的基本觀念-圖例 圖形通常使用圓圈代表頂點，頂點之間的連線是邊線。例如：上述公路圖繪成的圖形G1和另一個樹狀圖形G2，如下圖所示：

5 8-1 圖形的基本觀念-表示法 圖形一共擁有5個頂點V1、V2、…、V5，V(G1)是圖形G1的頂點集合，V(G2)是圖形G2，如下所示：
V(G1) = { V1, V2, V3, V4, V5 } V(G2) = { V1, V2, V3, V4, V5 } 圖形G1頂點和頂點之間的邊線有6條，G2有4條，E(G1)是圖形G1的邊線集合，E(G2)是圖形G2，如下所示： E(G1) = { (V1,V2),(V1,V3),(V2,V3),(V2,V4),(V3,V5),(V4,V5) } E(G2) = { (V1,V2),(V1,V3),(V2,V4),(V2,V5) } 上述邊線是使用括號括起的兩個頂點，例如：(V1,V2)表示從頂點V1到V2存在一條邊線。

6 8-1 圖形的基本觀念-圖形種類 圖形是由頂點和邊線所組成，依邊線集合E(G)中頂點是否擁有順序性，可以分為兩種，如下所示：
無方向性圖形（Undirected Graph）：圖形的邊線沒有標示方向的箭頭，邊線只代表頂點間是相連的。例如：圖形G1和G2是無方向性圖形，所以(V1,V2)和(V2,V1)代表同一條邊線。 方向性圖形（Directed Graph）：在圖形的邊線加上箭號標示頂點間的順序性。

7 8-1 圖形的基本觀念-方向性圖形 例如：圖形G3是方向性圖形，G3圖形的頂點和邊線集合V(G3)、E(G3)，如下所示：
V(G3)={ V1, V2, V3, V4, V5 } E(G3)={ <V1,V2>,<V1,V3>,<V2,V3>,<V3,V2>,<V2,V4>,<V4,V5>,<V5,V3> }

8 8-1 圖形的基本觀念-圖形術語1 完整圖形（Complete Graph）：一個n頂點的無方向性圖形擁有n(n-1)/2條邊線，例如：4頂點的完整圖形G4擁有6條邊線，如下圖所示： 子圖（Subgraph）：圖形G的子圖G’，是指G的頂點包含或等於G’的頂點，G的邊線包含或等於G’的邊線，例如：G5和G6是G4的子圖。

9 8-1 圖形的基本觀念-圖形術語2 相連圖形（Connected Graph）：圖形內任何兩個頂點都有路徑相連結。例如：圖形G1、G2、G3、G4、G5和G6是相連圖形。 不相連圖形（Disconnected Graph）：圖形內至少有兩個頂點間是沒有路徑相連的。例如：圖形G7的頂點3，如下圖所示：

10 8-1 圖形的基本觀念-圖形術語3 簡單路徑（Simple Directed Path）：除了第1個和最後1個頂點可以相同外，其它位在路徑上的頂點都不相同。例如：圖形G7的路徑<V5,V2>、<V2,V1>，寫成：5,2,1是簡單路徑，路徑5,2,1,4,2,1就不是簡單路徑。 循環（Cycle）：屬於簡單路徑的一種特例，也就是第1個和最後1個頂點是同一個頂點的路徑。例如：圖形G7的路徑5,2,4,5，第1個和最後1個頂點都是5。

11 8-1 圖形的基本觀念-圖形術語4 鄰接（Adjacent）：如果兩個頂點間擁有一條邊線連結，則這兩個頂點稱為鄰接。
內分支度（In-degree）：指某頂點擁有箭頭的邊線數。例如：圖形G7頂點1的內分支度是1，頂點2的內分支度是2。 外分支度（Out-degree）：與內分支度相反，指某頂點擁有尾端（非箭頭端）的邊線數。例如：圖形G7頂點1和5的外分支度都是1。

12 8-2 圖形的表示法 8-2-1 鄰接矩陣表示法 8-2-2 鄰接串列表示法

13 8-2 圖形的表示法 圖形結構可以使用多種方法來實作，常用的方法有二種，如下所示： 鄰接矩陣表示法（Adjacency Matrix）。
鄰接串列表示法（Adjacency Lists）。

14 8-2-1 鄰接矩陣表示法-說明 圖形G = (V, E)是一個包含n個頂點的圖形，可以使用一個n X n矩陣來儲存圖形，在C語言是宣告一個n X n的二維陣列，索引值代表頂點，陣列元素值0表示沒有邊線，1表示有邊線。

15 8-2-1 鄰接矩陣表示法-圖例 無方向圖形G1的鄰接矩陣表示法使用5 X 5的二維陣列儲存矩陣，如果頂點V1和V2鄰接，陣列元素(V1,V2)和(V2,V1)的值是1，表示圖形包含頂點V1到V2和頂點V2到V1的路徑，如下圖所示：

16 8-2-1 鄰接矩陣表示法-標頭檔 01: /* 程式範例: Ch8-2-1.h */
02: #define MAX_VERTICES 6 /* 最大頂點數加一 */ 03: int graph[MAX_VERTICES][MAX_VERTICES]; 04: /* 抽象資料型態的操作函數宣告 */ 05: extern void createGraph(int len, int *edge); 06: extern void printGraph();

17 void createGraph(int len, int *edge) {
int from, to; /* 邊線的起點和終點*/ int i, j; for ( i = 1; i < MAX_VERTICES; i++ ) for ( j = 1; j < MAX_VERTICES; j++ ) if ( i != j ) graph[i][j] = MAX; /* 矩陣設為無窮大*/ else graph[i][j] = 0; /* 對角線設為*/ for ( i = 0; i < len; i++ ) { /* 讀取邊線的迴圈*/ from = edge[i*3]; /* 邊線的起點*/ to = edge[i*3+1]; /* 邊線的終點*/ graph[from][to]=edge[i*3+2];/* 存入圖形的邊線*/ } /* 函數: 顯示圖形*/ void printGraph() { /* 使用迴圈顯示圖形*/ for ( i = 1; i < MAX_VERTICES; i++ ) { if ( graph[i][j] == MAX ) printf(" ∞"); printf("%4d", graph[i][j]); printf("\n");

18 8-2-2 鄰接串列表示法-說明 鄰接串列表示法的圖形是使用單向串列來鏈結每個頂點的鄰接頂點，使用一個頂點的結構陣列指標指向各頂點的鄰接頂點串列。例如：無方向圖形G1的鄰接串列表示法，如下圖所示：

19 8-2-2 鄰接串列表示法-標頭檔 01: /* 程式範例: Ch8-2-2.h */
02: #define MAX_VERTICES 10 /* 圖形的最大頂點數 */ 03: struct Vertex { /* 圖形頂點結構宣告 */ 04: int data; /* 頂點資料 */ 05: struct Vertex *next; /* 指下一個頂點的指標 */ 06: }; 07: typedef struct Vertex *Graph; /* 圖形的新型態 */ 08: struct Vertex head[MAX_VERTICES]; 09: /* 抽象資料型態的操作函數宣告 */ 10: extern void createGraph(int len, int *edge); 11: extern void printGraph(); 12: extern void dfs(int vertex); 13: extern void bfs(int vertex);

20 void createGraph(int len, int *edge) {
Graph newnode, ptr; /* 頂點指標*/ int from, to; /* 邊線的起點和終點*/ int i; for ( i = 1; i < MAX_VERTICES; i++ ) { head[i].data = i; /* 設定頂點值*/ head[i].next = NULL; /* 清除圖形指標*/ } for ( i = 0; i < len; i++ ) { /* 讀取邊線的迴圈*/ from = edge[i*2]; /* 邊線的起點*/ to = edge[i*2+1]; /* 邊線的終點*/ /* 配置新頂點的記憶體*/ newnode = (Graph)malloc(sizeof(struct Vertex)); newnode->data = to; /* 建立頂點內容*/ newnode->next = NULL; /* 設定指標初值*/ ptr = &(head[from]); /* 指標陣列的頂點指標*/ while ( ptr->next != NULL ) /* 走訪至串列尾*/ ptr = ptr->next; /* 下一個頂點*/ ptr->next = newnode; /* 插入結尾*/ /* 函數: 顯示圖形*/ void printGraph() { Graph ptr; int i; /* 使用迴圈顯示圖形*/ for ( i = 1; i < MAX_VERTICES; i++ ) { ptr = head[i].next; /* 頂點指標*/ if ( ptr != NULL ) { /* 有使用的節點*/ printf("頂點V%d =>", head[i].data);/* 頂點值*/ while ( ptr != NULL ) { /* 走訪顯示*/ printf("V%d ", ptr->data); /* 頂點內容*/ ptr = ptr->next; /* 下一個頂點*/ } printf("\n");

21 8-2-2 鄰接串列表示法- 建立圖形1 函數createGraph()首先使用for迴圈初始頂點結構陣列head[]，next指標都是指向NULL，讀入的第一條邊線是(1, 2)，從頂點1連到頂點2，所以建立結尾頂點2的節點指標newnode，如下圖所示：

22 8-2-2 鄰接串列表示法- 建立圖形2 然後將節點插入結構陣列head[]索引1（即頂點1）的串列最後，如下圖所示：

23 8-2-2 鄰接串列表示法- 建立圖形3 繼續讀入的邊線是(2, 1)，從頂點2連到頂點1，插入的是結構陣列head[]索引值2的串列最後，如下圖所示： 等到讀完所有邊線，就可以完成圖形G1的鄰接串列表示法。

24 8-2-2 鄰接串列表示法- 顯示圖形 函數printGraph()：顯示圖形
函數printGraph()使用迴圈走訪head[]陣列顯示鄰接串列表示法，在取得每一個頂點串列的串列指標後，使用while迴圈走訪串列的每一個節點，如下所示： while ( ptr != NULL ) { printf(“V%d ”, ptr->data); //show出目前的內容 ptr = ptr->next; //繼續往下移動 }

25 8-3 圖形的走訪 8-3-1 深度優先搜尋法DFS 8-3-2 寬度優先搜尋法BFS

26 8-3 圖形的走訪-說明1 圖形結構與之前的二元樹和鏈結串列一樣，都擁有特定的走訪方式。例如：一個無方向圖形G8，如下圖所示：

27 8-3 圖形的走訪-說明2 圖形G8的鄰接串列表示法，如下圖所示：

28 8-3 圖形的走訪-種類 圖形G8的走訪可以分為偏向直的深度（結構陣列索引）或橫的寬度（頂點串列）兩種搜尋法，如下所示：
深度優先搜尋法（Depth-first Search, DFS）： 當在鄰接串列表示法走訪某一頂點後，優先找尋頂點在結構陣列中的鄰接頂點。 寬度優先搜尋法（Breadth-first Search, BFS）：當在鄰接串列表示法走訪某一頂點後，優先找尋頂點串列的所有鄰接頂點。

29 8-3-1 深度優先搜尋法DFS-說明 1→2→4→8→5→6→3→7
圖形G8的深度優先搜尋法是從頂點1開始以深度優先方式來走訪圖形，首先走訪頂點1，找尋結構陣列索引值1的鄰接頂點，結果找到未走訪的頂點2，頂點2從深度方向往下走訪，即走訪結構陣列索引值2的鄰接頂點，找到未走訪過的頂點4，繼續再往下搜尋結構陣列索引值4的鄰接頂點，可以找到未走訪過的頂點8。 從頂點8走訪結構陣列索引值8的鄰接頂點，找到未走訪的頂點5，因為頂點5的鄰接頂點2和8已經走訪過，所以再回到頂點8，繼續找到頂點6，接著從結構陣列索引值6找到鄰接頂點3，最後找到頂點7，可以得圖形走訪的頂點順序，如下所示： 1→2→4→8→5→6→3→7

30 8-3-1 深度優先搜尋法DFS-演算法 深度優先搜尋法的遞迴函數dfs(V)的操作步驟，如下所示：
Step 1：設定頂點V已走訪過，1為走訪過。 visited[vertex] = 1; Step 2：如果頂點V存在有鄰接頂點W未被走訪過，遞迴呼叫函數dfs(W)。 while ( ptr != NULL ) { if ( visited[ptr->data] == 0 ) //點沒有被拜訪過 dfs(ptr->data); ptr = ptr->next; }

31 #include <stdio.h>
#include <stdlib.h> #include "ex8.h" #include "createGraph.c" int visited[MAX_VERTICES]; /* 走訪記錄陣列*/ /* 函數: 圖形的深度優先搜尋法*/ void dfs(int vertex, int pre) { Graph ptr; visited[vertex] = 1; /* 記錄已走訪過*/ if ( pre != 0 ) printf("[V%d]->[V%d] ", pre, vertex); ptr = head[vertex].next; /* 頂點指標*/ pre = vertex; while ( ptr != NULL ) { /* 走訪至串列尾*/ if ( visited[ptr->data] == 0 ) /* 是否走訪過*/ dfs(ptr->data, pre); /* 遞迴走訪呼叫*/ ptr = ptr->next; /* 下一個頂點*/ } /* 主程式*/ int main() { int edge[20][2] = { {1, 2}, {2, 1}, /* 邊線陣列*/ {1, 3}, {3, 1}, {2, 4}, {4, 2}, {2, 5}, {5, 2}, {3, 6}, {6, 3}, {3, 7}, {7, 3}, {4, 8}, {8, 4}, {5, 8}, {8, 5}, {6, 8}, {8, 6}, {7, 8}, {8, 7} }; int i; /* 設定走訪初值*/ for ( i = 1; i < MAX_VERTICES; i++ ) visited[i] = 0; createGraph(20, &edge[0][0]); /* 建立圖形*/ printf("圖形G的鄰接矩陣內容:\n"); printGraph(); /* 顯示圖形*/ printf("圖形的深度優先走訪:\n"); dfs(1, 0); /* 顯示走訪過程*/ printf("\n"); system("PAUSE"); return 0; }

32 8-3-2 寬度優先搜尋法BFS-說明 圖形G8的寬度優先搜尋法與深度優先搜尋法走訪圖形的差別在於走訪頂點1後，接著是走訪頂點1的所有鄰接頂點，即頂點2和3，然後才從頂點2和3開始走訪所有鄰接且未走訪過的頂點，頂點2走訪頂點4和5，頂點3走訪頂點6和7，最後走訪頂點8。 整個寬度優先搜尋法走訪圖形的順序。如下所示： 1→2→3→4→5→6→7→8

33 8-3-2 寬度優先搜尋法BFS-演算法1 寬度優先搜尋法的函數bfs(V)的操作步驟，如下所示：
Step 1：設定頂點V已經走訪過，1為走訪過。 visited[vertex] = 1; Step 2：將頂點V存入佇列。 enqueue(vertex);

34 8-3-2 寬度優先搜尋法BFS-演算法2 Step 3：執行迴圈直到佇列空了為止，如下：
while ( !isQueueEmpty() ) { (1) 取出佇列的頂點V。 vertice = dequeue(); ptr = head[vertex].next; //linklist的頭 (2) 將頂點V所有鄰接且未走訪的頂點W存入佇列，且設定已走訪。 while ( ptr != NULL ) { if ( visited[ptr->data]==0 ) { enqueue(ptr->data); visited[ptr->data] = 1; printf("[V%d] ", ptr->data); } ptr = ptr->next;

35 8-4 擴張樹 8-4-1 圖形走訪建立擴張樹 8-4-2 加權圖形表示法 8-4-3 最低成本擴張樹

36 8-4 擴張樹-說明 「擴張樹」（Spanning Trees）是將無方向性圖形的所有頂點使用邊線連接起來，但邊線並不會形成迴圈，換句話說，擴張樹的邊線數將比頂點少1，因為再多一條邊線，圖形就會形成迴圈。例如：一個無方向性圖形，如下圖所示：

37 8-4 擴張樹-範例 一個擁有四個頂點六條邊線的圖形，依擴張樹的定義，可以得三棵不同的擴張樹，如下圖所示：

38 8-4-1 圖形走訪建立擴張樹-說明 擴張樹可以使用第8-3節走訪的搜尋法來建立，因為只需將圖形走訪過的頂點順序，使用邊線一一連接起來，就可以建立成擴張樹，依照搜尋法的不同，分成二種擴張樹，如下所示： 深度優先擴張樹（DFS Spanning Trees）。 寬度優先擴張樹（BFS Spanning Trees）。

39 8-4-1 圖形走訪建立擴張樹-深度優先擴張樹 深度優先搜尋走訪圖形G8的頂點順序，如下：
1,2,4,8,5,6,3,7 現在只需將走訪經過的邊線保留下來，就可以建立深度優先擴張樹，如下圖所示：

40 8-4-1 圖形走訪建立擴張樹-寬度優先擴張樹 寬度優先搜尋走訪圖形G8的頂點順序，如下：
1,2,3,4,5,6,7,8 保留頂點1走訪到頂點2,3的邊線，頂點2走訪到4,5，頂點3走訪頂點6,7，頂點4走訪到頂點8，可以建立走訪的寬度優先擴張樹，如下圖所示：

41 8-4-2 加權圖形表示法-說明 圖形在解決問題時通常需要替邊線加上一個數值，這個數值稱為「權值」（Weights），常見的權值有：時間、成本或長度，擁有權值的圖形稱為加權圖形，一樣可以分別使用鄰接矩陣和鄰接串列來表示。

42 8-4-2 加權圖形表示法-圖例 例如：一個方向性圖形G9，如下圖所示：

43 8-4-2 加權圖形表示法-鄰接矩列表示法 以鄰接矩陣的加權圖形來說，只需將原來儲存1和0的陣列元素換成各頂點間的權值。如果頂點間無邊線連接，就使用無窮大∞表示。所以，圖形G9的加權鄰接矩陣表示法，如下圖所示：

44 8-4-2 加權圖形表示法-鄰接串列表示法 鄰接串列表示法的加權圖形只是在頂點結構新增成員變數weight儲存權值，圖形G9的加權鄰接串列表示法，如下圖所示：

45 8-4-3 最低成本擴張樹-說明 從加權圖形建立的擴張樹因為邊線擁有權值，所以可以計算邊線的權值和，換句話說，圖形建立的擴張樹會因連接的邊線權值不同，而建立出不同成本的擴張樹，因為各種建立方法會產生不同成本，所以如何找出「最低成本擴張樹」（Minimum-cost Spanning Trees）就成為一個重要的問題。

46 8-4-3 最低成本擴張樹-圖例 例如：一個擁有權值的無方向性加權圖形G10找出最低成本擴張樹，如下圖所示：

47 8-4-3 最低成本擴張樹-克魯斯卡演算法 克魯斯卡（Kruskal）提出建立最低成本擴張樹的演算法，首先將各邊線依權值從小到大排列，如下表所示：

48 8-4-3 最低成本擴張樹-步驟1 接著從權值最低的一條邊線開始建立最低成本擴張樹，其步驟如下所示：
Step 1：選擇第一條最低權值的邊線(1, 2)加入擴張樹，如下圖所示：

49 8-4-3 最低成本擴張樹-步驟2,3 Step 2：選擇第二低權值的邊線(2, 4)加入擴張樹，只需加入的邊線不會形成迴圈，以此例邊線(2, 4)並不會形成迴圈。 Step 3：如果加入第三低權值的邊線(1, 4)，因為會形成迴圈，所以選擇下一條不會形成迴圈的低權值邊線(3, 5)，如下圖所示：

50 8-4-3 最低成本擴張樹-步驟4 Step 4：邊線(2, 5)也不會形成迴圈，將邊線(2, 5)加入擴張樹，現在所有頂點都已經連接，建立的就是一棵最低成本擴張樹，如下圖所示：

51 8-4-3 最低成本擴張樹-實作 最低成本擴張樹的實作是以權值從小到大使用單向鏈結串列儲存圖形的邊線頂點和權值，如下圖所示：

52 8-4-3 最低成本擴張樹-標頭檔 01: /* 程式範例: Ch8-4-3.h */
02: #define MAX_VERTICES /* 最大頂點數加一 */ 03: struct Edge { /* 圖形邊線結構宣告 */ 04: int from; /* 開始頂點 */ 05: int to; /* 終點頂點 */ 06: int weight; /* 權值 */ 07: struct Edge *next; /* 指下一條邊線 */ 08: }; 09: typedef struct Edge *EdgeList; /* 邊線的結構新型態 */ 10: EdgeList first = NULL; /* 邊線串列開始指標 */ 11: int vertex[MAX_VERTICES]; /* 檢查迴圈的頂點陣列 */ 12: /* 抽象資料型態的操作函數宣告 */ 13: extern void createEdge(int len, int *edge); 14: extern void minSpanTree(); 15: extern void addSet(int from, int to); 16: extern int isSameSet(int from, int to);

53 8-4-3 最低成本擴張樹-演算法 函數minSpanTree()使用邊線的單向鏈結串列找出最低成本擴張樹，其操作步驟如下所示：
Step 1：走訪邊線的單向串列直到串列的結尾，如下： (1) 如果邊線不會形成迴圈，就將邊線加入擴張樹。 if ( !isSameSet(ptr->from,ptr->to) ) addSet(ptr->from,ptr->to); (2) 移動指標到串列的下一條邊線節點。 ptr = ptr->next;

54 8-5 圖形的應用 - 最短路徑 8-5-1 一個頂點到多頂點的最短路徑 8-5-2 各頂點至其它頂點的最短路徑

55 8-5 圖形的應用 - 最短路徑 最短路徑問題（Shortest Paths Problems）是指一個加權圖形G = (V, E)，邊線的權值不是負值且擁有一個頂點為來源（Source），問題是找出來源頂點到其它頂點的各條路徑中，各邊線權值和為最低的路徑，也就是最短路徑。最短路徑求法的常用方法有二種，如下所示： 一個頂點到多頂點的求法（Dijkstra演算法）。 各頂點至其它頂點的求法（Floyd演算法）。

56

57 8-5-1 一個頂點到多頂點的最短路徑-說明 從一個頂點到多頂點最短路徑的求法中，最著名的是Dijkstra演算法。例如：從基隆到高雄，中間經過台北、新竹、台中或桃園，各城市間的距離，如下圖所示：

58 8-5-1 一個頂點到多頂點的最短路徑-原理 頂點1基隆到各頂點城市間的距離，很明顯的！可以發現基隆到新竹的最短路徑，也是基隆到台中或高雄最短路徑的一部分，也就是說，已知的最短路徑頂點，可能就是其它頂點最短路徑上經過的頂點，如下表所示：

59 8-5-1 一個頂點到多頂點的最短路徑-Dijkstra演算法說明
Dijkstra演算法是依據上述最短路徑的特性，提出解決「單來源最短路徑的問題」（Single-source Shortest Paths）的演算法，Dijkstra演算法使用鄰接矩陣表示法建立圖形。例如：圖形G11的鄰接矩陣表示法，如下圖所示：

60 8-5-1 一個頂點到多頂點的最短路徑-Dijkstra演算法步驟
Step 1：初始相關陣列的內容： (1) 將graph[source][i]來源頂點複製到一維陣列dist[i]。 (2) 設為selected[i]和pi[i]的陣列元素初值。 Step 2：執行頂點總數減1次的迴圈來計算最短路徑，如下所示： (1) 走訪陣列dist[]找出最短距離的頂點W，且此頂點沒有選過。 (2) 將頂點W設為選過，即selected[W] = 1。 (3) 走訪陣列dist[]，如果有未選過的頂點X，則： 1) 比較dist[X]和graph[W][X]+dist[W]的距離大小： a. 如果graph[W][X]+dist[W]小，存入dist[X]。 b. 如果更改距離，指定頂點X的前頂點為W，pi[X] = W。

61 8-5-1 一個頂點到多頂點的最短路徑-Dijkstra演算法過程
Dijkstra演算法計算圖形G11來源頂點1到其它各頂點最短路徑的過程，如下表所示： dist[ ]:計算每個結點間的成本 pi[ ]:前一個節點

62 8-5-1 一個頂點到多頂點的最短路徑-第一次迴圈
第一次迴圈搜尋陣列dist[]的最短距離頂點W是頂點2的35，然後走訪陣列dist[]，將未選過的頂點X：3、4、5、6，依序計算下列公式，如下所示： MIN (dist(X),dist(W)+鄰接矩陣(W,X)) MIN()函數可以傳回兩個參數距離的最短距離。如果dist(W)+鄰接矩陣(W,X)比較短，例如：頂點1到頂點3的距離是dist[3] = 90，透過頂點2到頂點3的距離，如下所示： dist(2) + 鄰接矩陣(2, 3) = dist[2] + graph[2][3] = = 80 距離80小於dist[3] = 90，所以更新dist[3] = 80，同時，將pi[3]更新為2，表示頂點3最短路徑的前一個頂點是2。同理，頂點4更新為65。 //Pi[ N]記入前頂點是什麼?

63 8-5-1 一個頂點到多頂點的最短路徑-第二次迴圈
第2次迴圈搜尋陣列dist[]的最短距離頂點W是頂點4的65，然後走訪陣列dist[]，將未選過的頂點X：3、5、6，其中頂點5可由頂點4到達，其距離為： dist[4] + graph[4, 5] = = 110 更新dist[5] = 110，同時，將pi[5]更新為4，表示頂點5最短路徑的前一個頂點是4。 重複上述操作，執行頂點數減一次迴圈，就可以完成頂點1到其它頂點的最短路徑計算。

64 8-5-1 一個頂點到多頂點的最短路徑-找出最短路徑
如何知道最短路徑經過哪些頂點？可以從pi[]陣列得知。 例如：頂點1到頂點6的路徑，從pi[6]開始，前一個頂點是5，pi[5] = 3，表示頂點5的前一個頂點是3，頂點3的前一個頂點是2，所以得到路徑：1,2,3,5,6。

65 8-5-2 各頂點至其它頂點的最短路徑-說明 R. W. Floyd教授的演算法可以計算出各頂點至其它頂點的最短路徑。例如：以上一節的加權圖形G11為例，Floyd演算法是將鄰接矩陣表示法的內容複製到二維陣列dist[][]，如下圖所示：

66 8-5-2 各頂點至其它頂點的最短路徑-說明 Floyd演算法使用迴圈重覆執行n次的頂點數，(i, j)是矩陣座標，走訪二維陣列的每一個元素來計算下列公式，如下所示： distn(i,j)=MIN(distn-1(i,j),distn-1(i,n)+distn-1(n,j)) 上述n值是第n次執行迴圈MIN()函數，函數找出兩個參數的最小值。當計算出distn-1後，在計算distn(i,j)時一共有兩種情況，如下所示： 沒有經過頂點n：最短距離仍然為distn-1(i,j)。 如果有經過頂點n：最短距離是比較distn-1(i,n)+distn-1(n,j)和distn-1(i,j)找出最小值，經過頂點n的路徑就是從頂點i到n和頂點n到j。

67 8-5-2 各頂點至其它頂點的最短路徑-第一次迴圈
現在執行第一次公式的計算，如下所示： dist1(i,j) = MIN(dist0(i,j),dist0(i,1)+dist0(1,j)) 上述dist0是初始的二維陣列。在計算每一個元素後的陣列內容，如下圖所示：

68 8-5-2 各頂點至其它頂點的最短路徑-第二次迴圈
繼續第二次公式的計算，如下所示： dist2(i,j) = MIN(dist1(i,j),dist1(i,2)+dist1(2,j)) 計算後的陣列內容，如下圖所示：

69 8-5-2 各頂點至其它頂點的最短路徑-執行完迴圈
等到執行完全部迴圈一共是頂點數6次後，就可以得到最後的二維陣列內容，如下圖所示：

70 #include <stdio.h> #include <stdlib.h>
#include "adjacencyMatrix.c" int dist[MAX_VERTICES]; /* 路徑長度陣列*/ int pi[MAX_VERTICES]; /* 前一頂點陣列*/ /* 函數: 找尋某一頂點至各頂點的最短距離*/ void shortestPath(int source, int num) { int selected[MAX_VERTICES]; /* 選擇的頂點陣列*/ int min_len; /* 最短距離*/ int min_vertex = 1; /* 最短距離的頂點*/ int i,j; for ( i = 1; i <= num; i++ ) { /* 初始陣列迴圈*/ selected[i] = 0; /* 清除陣列內容*/ pi[i] = 0; /* 清除陣列內容*/ dist[i] = graph[source][i]; /* 初始距離*/ } selected[source] = 1; /* 開始頂點加入集合*/ dist[source] = 0; /* 設定開始頂點距離*/ printf("V \n"); for ( j = 1; j <= num; j++ ) { /* 顯示dist[]陣列內容*/ if ( j == 1 ) printf("%d", source); /* 選擇頂點*/ if ( dist[j] == MAX ) printf(" ∞"); else printf("%4d", dist[j]); /* 顯示距離*/ printf("\n"); /* 一共執行頂點數-1次的迴圈*/ for ( i = 1; i <= num-1; i++ ) { min_len = MAX; /* 先設為無窮大*/ /* 找出最短距離頂點的迴圈*/ for ( j = 1; j <= num; j++ ) /* 從不屬於集合的頂點陣列找尋最近距離頂點s */ if ( min_len > dist[j] && selected[j] == 0 ) { min_vertex = j; /* 目前最短的頂點*/ min_len = dist[j]; /* 記錄最短距離*/ } selected[min_vertex] = 1; /* 將頂點加入集合*/ printf("%d", min_vertex); /* 顯示選擇的的頂點*/ if ( i == 1 ) pi[min_vertex] = 1;/* 前頂點*/ /* 計算開始頂點到各頂點最短距離陣列的迴圈*/ for ( j = 1; j <= num; j++ ) { if ( selected[j] == 0 && /* 是否距離比較短*/ dist[min_vertex]+graph[min_vertex][j]<dist[j]) { /* 指定成較短的距離*/ dist[j]=dist[min_vertex]+graph[min_vertex][j]; pi[j] = min_vertex; /* 記錄前一個頂點*/ if ( dist[j] == MAX ) printf(" ∞"); else printf("%4d", dist[j]);/* 顯示最短距離*/ printf("\n"); printf("前一頂點陣列: \n"); printf("V \n"); printf("%4d", pi[j]); /* 顯示前一個頂點*/

71 int main() { int edge[7][3] = { {1, 2, 35}, /* 加權邊線陣列*/ {1, 3, 90}, {2, 3, 45}, {2, 4, 30}, {3, 5, 25}, {4, 5, 45}, {5, 6, 200} }; int end = 6; createGraph(7, &edge[0][0]); /* 建立圖形*/ printf("圖形G的鄰接矩陣內容:\n"); printGraph(); /* 顯示圖形*/ printf("從頂點到各頂點最近距離的Dijkstra計算過程:\n"); shortestPath(1,6); /* 找尋最短路徑*/ printf("\n從頂點到頂點的路徑為(倒過來顯示): "); while ( end != 0 ) { printf("%4d", end); /* 顯示前一個頂點*/ end = pi[end]; } printf("\n"); printf("100可以從頂點到達的頂點: "); for ( end = 2; end <= 6; end++ ) if (dist[end] <= 100 ) printf("V%d ", end); system("PAUSE"); return 0;

72 8-6 圖形的應用 - 拓樸排序(AOV網路與拓樸排序)
工作或作業計劃都需要分割成數個小計劃，如果使用方向性圖形來表示各小計劃間的前後關連，這種圖形稱為「頂點工作網路」（Activity On Vertex Network），簡稱AOV網路。 不過問題是每個小計劃或工作間都擁有關連，所以準備進行某個小計劃前，需要等到其它小計劃先行完成。 例如：主修資訊科學的學生，在選修資料結構這門課前，需要先修過C語言課程，如果沒有修過C語言，就不能選修資料結構。 換句話說，因為課程有先後順序，所以如何找出修課的先後順序，而且不會造成先修課程尚未修過的擋修問題，就是「拓樸排序」（Topological Sort）。

73 8-6 圖形的應用 - 拓樸排序(AOV網路圖例1)
例如：一個方向性圖形G12表示課程間的先後關連，如下圖所示：

74 8-6 圖形的應用 - 拓樸排序(AOV網路圖例2)
圖形G12是一個AOV網路，其頂點代表課程，頂點1需要等到讀完頂點3和2的課程後，才可以選修，頂點3是其它頂點的「先行者」（Predecessor），頂點2是頂點1、5和6的「立即先行者」（Immediate Predecessor）。 頂點4的課程需要等到頂點1,5,7的課程都讀完，它是圖形其它頂點的「後繼者」（Successor），頂點1、5和7的「立即後繼者」（Immediate Successor）。

75 8-6 圖形的應用 - 拓樸排序(拓樸排序演算法推導過程1)
拓樸排序的圖形需要計算頂點的內分支度，內分支度為0的頂點表示沒有先修課程，所以是課程的開始。 拓樸排序就是從內分支度為0的頂點開始處理，先輸出此頂點，接著將頂點相連接的邊線刪除，如下圖所示：

76 8-6 圖形的應用 - 拓樸排序(拓樸排序演算法推導過程2)
頂點2因為邊線已經刪除，內分支度也成為0，輸出頂點2。繼續將頂點2連接的三條邊線刪除，如下圖所示：

77 8-6 圖形的應用 - 拓樸排序(拓樸排序演算法推導過程3)
現在頂點1、5和6的內分支度都是0，只需刪除這三個頂點和邊線，輸出頂點1、5和6後，如下圖所示：

78 8-6 圖形的應用 - 拓樸排序(加權鄰接串列表示法)
圖形G12的加權鄰接串列表示法，如下圖所示：

79 8-6 圖形的應用 - 拓樸排序(拓樸排序演算法推導過程4)
繼續上述操作，刪除頂點7，最後輸出頂點7和4，就可以得到拓樸排序的結果，如下所示： 3→2→1→5→6→7→4

80 8-6 圖形的應用 - 拓樸排序(拓樸排序演算法)
Step 1：走訪head[]陣列將內分支度為0的頂點存入佇列。 for ( i = 1; i <= num; i++ ) if ( head[i].data == 0 ) enqueue(i); Step 2：從佇列取出頂點，直到佇列空了為止，如下： while ( !isQueueEmpty() ) { (1) 取出佇列元素，輸出拓樸排序的頂點。 vertex = dequeue(); printf(" %d ", vertex); (2) 走訪頂點的鄰接串列，將所有鄰接頂點的內分支度減1。 ptr = head[vertex].next; while ( ptr != NULL ) { vertex = ptr->data; head[vertex].data--; (3) 如果頂點減1後的內分支度為0，將此頂點存入佇列。 if ( head[vertex].data == 0 ) enqueue(vertex); ptr = ptr->next; }

81 8-6 圖形的應用 - 拓樸排序(擁有迴圈的AOV網路1)
AOV網路輸出拓樸排序的條件是頂點間沒有循環路徑的迴圈，如果AOV網路擁有迴圈，就沒有辦法找出拓樸排序，因為每一個計劃都在等待其它計劃的執行。例如：在圖形G12加上2條邊線，如下圖所示：

82 8-6 圖形的應用 - 拓樸排序(擁有迴圈的AOV網路2)
圖形擁有迴圈5→6→7→5，拓樸排序無法輸出圖形的所有節點，在輸出3→2→1後留下的圖形，頂點6等待頂點5，頂點7等待頂點6，頂點5等待頂點7，循環等待其它計劃的完成，換句話說，這個計劃將無法完成，如下圖所示：