第九章 圖形結構.

Presentation on theme: "第九章 圖形結構."— Presentation transcript:

1 第九章 圖形結構

2 目次 9.1 圖形的一些專有名詞 9.2 圖形資料結構表示法 9.3 圖形追蹤 9.4 擴展樹 9.5 最短路徑 9.6 含有負的路徑權重
9.1 圖形的一些專有名詞 9.2 圖形資料結構表示法 9.3 圖形追蹤 9.4 擴展樹 9.5 最短路徑 9.6 含有負的路徑權重 9.7 任兩點間的最短路徑 9.8 拓樸排序 9.9 臨界路徑 9.10 動動腦時間 9.11 練習題解答

3 9.0 圖學理論(graph theory) 尤拉問題：是否可以從某城市開始走，然後走遍全部的橋，再回到原先的起始城市？ (a) (b)

4 9.0 名詞解釋 — 圖(b) 假使尤拉問題要能成立的話，必須每個頂點具備偶數的分支度方可，此稱為尤拉循環(Eulerian cycle)
圓圈為「頂點」(vertex) 連線為「分支度」(degree)；Ex：節點c的分支度為5 假使尤拉問題要能成立的話，必須每個頂點具備偶數的分支度方可，此稱為尤拉循環(Eulerian cycle) Ex：

5 9.1 圖形的一些專有名詞 Ex： 名詞解釋 頂點(vertex)：圖中的圓圈 邊(edge)：每個頂點之間的連線
9.1 圖形的一些專有名詞 Ex： 名詞解釋 頂點(vertex)：圖中的圓圈 邊(edge)：每個頂點之間的連線 無方向圖形(undirected graph)：在邊上沒有箭頭者，如圖G1、G2 有方向圖形(directed graph)：在邊上有箭頭者，如圖G3 1 3 4 2 5 6 7 G1 G2 G3 G4

6 9.1 圖形的一些專有名詞 (con.t) 圖形 (graph) 是由所有頂點和所有邊組合而成的，以G=(V, E)表示
在無方向圖形中(V1, V2)和(V2, V1)代表相同的邊，但在有方向圖形中<V1, V2>和<V2, V1>是不一樣的邊 Ex：V(G1)={1, 2, 3, 4}； E(G1)={(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}； V(G3)={1, 2, 3}； E(G3)={<1, 2>, <2, 3>, <3, 2>}；(有方向圖形)

7 9.1 圖形的一些專有名詞 (con.t) 多重圖形(multigraph)：假使兩個頂點間，有多條相同的邊，此稱之為多重圖形，而不是圖形。如圖G4 完整圖形(complete graph)：在 n 個頂點的無方向圖形中，假使有n(n–1)/2個邊稱之，如圖G1 相鄰(adjacent) 在圖形的某一邊(V1, V2)，我們稱頂點V1與頂點V2是相鄰 有方向圖形中稱<V1, V2>為V1是adjacent toV2或V2是adjacent from V1 附著(incident)：我們稱頂點V1頂點V2是相鄰，而邊(V1, V2)是附著在頂點V1與頂點V2上。圖G3中附著在頂點V2的邊有<1, 2>, <2, 3>及<3, 2>

8 9.1 圖形的一些專有名詞 (con.t) 子圖(subgraph)：假使V(G‘) V(G)及E(G’) E(G)，則稱G‘是G的子圖，如下圖都是G1的子圖 路徑(path) 在圖形中G中，從頂點Vp到頂點Vq的路徑是指一系列的頂點Vp, Vi1, Vi2, ……, Vin, Vq，其中(Vp, Vi1), (Vi1, Vi2), ……, (Vin, Vq)是E(G)上的邊 假若G'是有方向圖形，則<Vp, Vi1>, <Vi1, Vi2>, ……, <Vin, Vq>是E(G')上的邊，故一個路徑是由一個邊或一個以上的邊所成 1 2 3 4

9 9.1 圖形的一些專有名詞 (con.t) 長度(length)：路徑長度是指該路徑上所有邊的數目
簡單路徑(simple path)：除了頭尾頂點之外，其餘的頂點皆在不相同的路徑上 G1的兩條路徑1, 2, 4, 3和1, 2, 4, 2，其長度皆為3，但前者是簡單路徑，而後者不是簡單路徑 循環(cycle)：是指在一條簡單路徑上，頭尾頂點皆有相同者稱之，如G1的1, 2, 3, 1或G3的1, 2, 1

10 9.1 圖形的一些專有名詞 (con.t) 連通(connected)：在一個圖形G中，如果有一條路徑從V1至V2，則V1與V2是連通的，圖G5就不是連通的 連通單元(connected component)：或稱單元(component)，是指該圖形中最大的連通子圖(maximal connected subgraph)，如G5有兩個單元g1、g2 1 3 2 4 5 6 7 8 g1 g2 G5

11 9.1 圖形的一些專有名詞 (con.t) 緊密連通(strongly connected)
在一有方向圖形中如果V(G)中的每一對不同頂點Vi, Vj各有一條從Vi至Vj及從Vj至Vi的有向路徑者稱之 G3不是緊密連通，因為G3沒有V2至V1的路徑 緊密連通單元(strongly connected component)：是指一個緊密連通最大子圖。如圖G3有兩個緊密連通單元 2 3 1

12 9.1 圖形的一些專有名詞 (con.t) 分支度(degree)：附著在頂點的邊數。如圖G1的頂點1其分支度為3。若為有方向圖形，則其分支度為內分支度與外分支度之和 內分支度(in-degree)：頂點V的內分支度是指以V為終點(即箭頭指向V)的邊數，如圖G3中頂點 2 的內分支度為 2，而頂點3的內分支度為1 外分支度(out-degree)：頂點V的外分支度是以V為起點的邊數，如圖G3中頂點 2 的外分支度為1。而頂點1和3的外分支度為1。「內分支度」和「外分支度」是針對有方向圖形而言

13 9.2 圖形資料結構表示法 圖形的資料結構表示法 相鄰矩陣(adjacency matrix)
9.2 圖形資料結構表示法 圖形的資料結構表示法 相鄰矩陣(adjacency matrix) 將圖形中的 n 個頂點，以一個 n × n 的二維矩陣來表示，其中每一元素Vij，若Vij = 1，表示圖形中 Vi 與 Vj 有一條邊為(Vi, Vj)，假若是有方向圖形的話，表示有一條邊為<Vi, Vj>。Vij = 0表示頂點i與頂點j沒有邊存在 Ex：下圖為G1之相鄰矩陣的表示法 1 2 3 4

14 9.2 圖形資料結構表示法 (con.t) 相鄰串列 Ex：右圖為G1之相鄰串列表示法
乃是將圖形中的每個頂點皆形成串列首，而在每個串列首的節點 Ex：右圖為G1之相鄰串列表示法 頂點1 1 2 3 頂點2 4 5 頂點3 6 7 頂點4 頂點5 頂點6 頂點7

15 9.3 圖形追蹤 圖形追蹤 圖形追蹤的目的 圖形追蹤的方法 從圖形的某一頂點開始，去拜訪圖形的其它頂點 判斷此圖形是不是連通；
9.3 圖形追蹤 圖形追蹤 從圖形的某一頂點開始，去拜訪圖形的其它頂點 圖形追蹤的目的 判斷此圖形是不是連通； 找出此圖形的連通單元； 畫出此圖形的擴展樹(spanning tree) 圖形追蹤的方法 縱向優先搜尋(depth first search) 橫向優先搜尋(breadth first search)

16 9.3 圖形追蹤(con.t) 9.3.1 縱向優先搜尋(以堆疊的形式來運作) 先拜訪起始點V；
縱向優先搜尋(以堆疊的形式來運作) 先拜訪起始點V； 然後選擇與V相鄰而未被拜訪的頂點W，以W為起始點做縱向優先搜尋； 假使有一頂點其相鄰的頂點皆被拜訪過時，就回到最近曾拜訪過之頂點，其尚有未被拜訪過的相鄰頂點，繼續做縱向優先搜尋； 假若從任何已走過的頂點，都無法再找到未被走過的相鄰頂點時，此時搜尋就結束了

17 9.3 圖形追蹤(con.t) 假設有一圖形如下： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10

18 9.3 圖形追蹤(con.t) 追蹤的步驟如下： (1) 先輸出V1(V1為起點) (2) 將V1的相鄰頂點V2及V3放入堆疊中

19 9.3 圖形追蹤(con.t) (4)彈出V1，由於V1已被輸出，故再彈出V4，將V4的相鄰頂點V2及V8放入堆疊
(5) 彈出V2，由於V2已被輸出過，故再彈出V8，再將V8的相鄰頂點V4、V5及V10放入堆疊 V2 V8 V5 V3 V4 V5 V10 V3

20 9.3 圖形追蹤(con.t) (6) 以此類推… (7)最後彈出V3、V9、V9、V7、V10、V5、V3，由於這些頂點皆已輸出過；此時堆疊是空的，表示搜尋已結束 從上述的搜尋步驟可知其順序為：V1、V2、V4、V8、V5、V10、V9、V6、V3、V7。讀者須注意的是此順序並不是唯一，而是根據頂點放入堆疊的順序而定

21 9.3 圖形追蹤(con.t) 9.3.2 橫向優先搜尋(以佇列的形式來運作) 追蹤的步驟如下：
橫向優先搜尋(以佇列的形式來運作) 橫向搜尋先拜訪完所有的相鄰頂點，再去找尋下一層的其他頂點 橫向優先搜尋，其拜訪頂點的順序是V1, V2, V3, V4, V5, V6, V7, V8, V9, V10 追蹤的步驟如下： (1) 先拜訪V1並將相鄰的V2及V3也放入佇列 V2 V3

22 9.3 圖形追蹤(con.t) (2) 拜訪V2，再將V2的相鄰頂點V4及V5放入佇列 (由於V1已被拜訪過，故不放入佇列中。)

23 9.3 圖形追蹤(con.t) (4)拜訪V4，並將V8放入佇列(由於V2已被拜訪過，故不放入佇列。)
以此類推，最後得知，以橫向優先搜尋的拜訪順序是：V1、V2、V3、V4、V5、V6、V7、V8、V9、V10 V5 V6 V7 V8

24 9.4 擴展樹 擴展樹是以最少的邊數，來連接圖形中所有的頂點 。如下圖有一完整圖形 下列是其部份的擴展樹

25 9.4 擴展樹 (con.t) 9.3曾提及圖形的追蹤，其可用於畫出圖形的擴展樹。 下列為其兩種不同追蹤方式所產生的擴展樹
假若使用縱向優先搜尋的追蹤方式，則稱為縱向優先搜尋擴展樹 (depth first search spanning tree)，如左圖 若使用橫向優先搜尋的追蹤方式，則稱為橫向優先搜尋擴展樹(breadth first search spanning tree) ，如右圖 下列為其兩種不同追蹤方式所產生的擴展樹 V3 V2 V4 V5 V6 V7 V8 V9 V10 V1

26 9.4 擴展樹 (con.t) 若G = (V, E)是一圖形，而S=(V, T)是G的擴展樹。其中T是追蹤時所拜訪過的邊，而以K表示追蹤後所未被拜訪的邊。此時擴展樹具有下列幾點特性： E = T+K； V中的任何兩個頂點V1及V2，在S中有唯一的邊； 加入K中任何一個邊於S中，會造成循環

27 9.4 擴展樹 (con.t) 若圖形中每一個邊加上一些數值，此數值稱為比重(weight)，而稱此圖形為比重圖形(weight graph) 假設此比重是成本(cost)或距離(distance)，則此圖形稱為網路(network) 從擴展樹的定義，得知一個圖形有許多不同的擴展樹，假若在網路中有一擴展樹具有最小成本時，則稱此為最小成本擴展樹(minimum cost spanning tree)。

28 9.4 擴展樹 (con.t) 求最小成本擴展樹有兩種方法 Prim’s 演算法 Kruskal’s 演算法 Sollin’s 演算法
有一網路，G = (V, E)，其中V={1, 2, 3, ……, n}起初設定 U={1}，U 及 V 是兩個頂點的集合，然後從 V-U 集合中找一頂點 x，能與 U 集合中的某頂點形成最小的邊，把這一頂點 x 加入 U 集合，繼續此步驟，直到 U 集合等於 V 集合為止 Kruskal’s 演算法 有一網路G = (V, E)，V = {1, 2, 3, ……, n}，E 中每一邊皆有一成本，T = (V, φ)表示開始時 T 沒有邊。首先從 E 中找具有最小成本的邊；若此邊加入 T 中不會形成循環，則將此邊從 E 刪除並加入 T 中，直到 T 中含有 n–1 個邊為止 Sollin’s 演算法

29 9.5 最短路徑 求得最短路徑(shortest path)的方法
9.5 最短路徑 求得最短路徑(shortest path)的方法 步驟1： D[I] = A[F, I] (I = 1, N)，S = {F}，V = {1, 2, ……, N} D為N個位置的陣列，用來儲存某一頂點到其他頂點的最短 距離，F表示由某一起始點開始，A[F, I]是表示F點到I點的距 離，V是網路中所有頂點的集合，S也是頂點的集合 步驟2： 從V–S集合中找一頂點t使得D[t]是最小值，並將t放入S集合， 一直到V–S是空集合為止 步驟3： 根據公式調整D陣列中的值。 D[I] = min(D[I], D[t]+A[t, I]) ((I, t)E) 此處I是指t的相鄰各頂點。繼續回到步驟2執行

30 9.6 含有負的路徑權重 負的路徑權重表示經過此路徑可以節省成本
9.6 含有負的路徑權重 負的路徑權重表示經過此路徑可以節省成本 例如：某一條路徑太過於擁塞了，為了使大家少走這條路徑，而將其它路徑的權重設為負的，以鼓勵大家來走 雖然我們允許路徑權重可以為負的，但此情況在有方向圖形中是不可以有負的循環。因為如果有負的循環，則可能會導致–∞的情況發生，如下圖所示： 1 2 3 -3 4

31 9.6 含有負的路徑權重 (con.t) 當有負的權重時應如何地求解呢? Bellman和Ford提出了一演算法，如下所示：
Void BellmanFord(int n, int v) { int i, k; for (i=0; i<n; i++) dist[i] = length[v][i]; for(k=2; k<= n-1; k++) /*必經過的edge個數*/ for(對每一u，如u != v，u至少有一incoming edge) for(對<i, u>) for(dist[u] > dist[i] + length[i][u]) dist[u] = dist[i] + length[i][u]; }

32 9.7 任兩點間的最短路徑 任何兩點之間的最短距離(All – pairs shortest paths)
9.7 任兩點間的最短路徑 任何兩點之間的最短距離(All – pairs shortest paths) Ak[i][j] = min{ Ak-1[i][j] , Ak-1[i][k]+ Ak-1[k][j]}, k≧1及A0[i][j] = length[i][j] 此處的 k 為經過節點的名稱，即 Ak[i][j] 表示由 i 到 j 經由 k 節點的最短距離

33 9.7任兩點間的最短路徑 (con.t) 演算法如下： void AllPairLength(int n) { int i, j, k;
for(i=0; i<n; i++) for(j=0; j<n; j++) a[i][j] = length[i][j]; for(k=0; k<n; k++) if ((a[i][k] +a[k][j]) < a[i][j]) a[i][j] = a[i][k] + a[k][j]; }

34 9.8 拓樸排序 名詞解釋 AOV-network：在一有方向圖形中，每一頂點代表工作(task)或活動(activity)，而邊表示工作之間的優先順序(precedence relations)。即邊(Vi, Vj)表示Vi的工作必先處理完後才能去處理Vj的工作，此種有方向圖形稱之為activity on vertex network或AOV-network V2 V1 V3 V4 V5 V6 V7 V8 V9 V10 V11

35 9.8 拓樸排序 (con.t) 立即前行者(immediate predecessor)與立即後繼者(immediate successor)：若在有方向圖形G中有一邊 <Vi, Vj>，則稱Vi 是Vj 的立即前行者，而Vj是Vi的立即後繼者。在上圖中 V7 是V8、V9、V10 的立即前行者，而 V8、V9、V10 是 V7 的立即後繼者 前行者(predecessor)與後繼者(successor)：在AOV-network中，假若從頂點Vi到頂點Vj存在一條路徑，則稱Vi是Vj的前行者，而Vj是Vi的後繼者。如上圖V3是V6的前行者，而V6是V3的後繼者

36 9.8 拓樸排序 (con.t) 拓樸排序(topological sort) 如何找尋AOV-network的拓樸排序呢？
若在AOV-network中，Vi是Vj的前行者，則在線性排列中，Vi 一定在 Vj 的前面，此種特性稱之為拓樸排序 如何找尋AOV-network的拓樸排序呢？ 步驟1：在AOV-network中任意挑選沒有前行者的頂點 步驟2：輸出此頂點，並將此頂點所連接的邊刪除。重覆步驟1及步驟2，一值到全部的頂點皆輸出為止

37 9.8 拓樸排序 (con.t) 拓樸排序過程如下，假設有一圖形：
(1) 輸出V1，並刪除<V1, V2>與<V1, V6>兩個邊 V2 V1 V6 V4 V3 V5 V7 V8 V2 V6 V4 V3 V5 V7 V8

38 9.8 拓樸排序 (con.t) (2) 此時V2和V6皆沒有前行者，若輸出V2則刪除<V2, V3>與<V2, V4>兩個邊 (3) 運用相同的原理，選擇輸出V6，並刪除<V6, V4>與<V6, V5>兩個邊 V6 V4 V3 V5 V7 V8 V4 V3 V5 V7 V8

39 9.8 拓樸排序 (con.t) (4) 輸出V3，並刪除<V3, V5>及<V3, V7>兩個邊

40 9.8 拓樸排序 (con.t) (6) 輸出V5，並刪除<V5, V8> (7) 輸出V7，並刪除<V7, V8>

41 9.8 拓樸排序 (con.t) 拓樸排序並非只有一種，因為在過程2時，假若選的頂點不是V2，其拓樸排序所排出來的順序就會不一樣。因此AOV-network的拓樸排序並不是唯一。 上述的方式，其資料的排列順序是V1、V2、V6、V3、V4、V5、V7及V8

42 9.9 臨界路徑法 有一AOV-network 如下：
9.9 臨界路徑法 有一AOV-network 如下： 有 7 個事件 V1、V2、V3、……、V7 ；有 11 個活動 a12、a13、a15、……、a47、a57、a67 V1是專案起始點，V7是結束點，其他如V5表示必須完成的活動 a13=3表示V1到V3需要3天時間，a35 = 2為V3到V5需要2天時間 a45為虛擬活動路徑(dummy activity path)其值為0，因為我們假設V5需要V1, V3及V4事件完成之後才可進行事件V5 V3 V1 V2 V4 V5 V6 V7 a15＝4 a13＝3 a12＝3 a24＝1 A35＝2 a45＝0 a57＝5 a47＝9 a46＝3 a67＝6 a34＝3

43 9.9 臨界路徑法 (con.t) 臨界路徑(Critical Path)
AOE網路上的活動是可以並行處理的，而一個計畫所需完成的最短時間，是從起始點到結束點間最長的路徑來算。長度為最長的路徑稱為臨界路徑 臨界路徑可能不止一條 AOE-network上活動的時間 最早開始時間(Early Start time)表示一活動最早開始的時間，以ES(i)表示活動ai最早開始時間； 最晚開始時間(Lastest Start time)指一活動在不影響整個計畫完成之下，最晚能夠開始進行的時間，以LS(i)表示活動ai最晚開始的時間

44 9.9 臨界路徑法 (con.t) 活動臨界之數量 臨界活動(Critical Activity)
LS(i) – ES(i)為一活動臨界之數量 它表示在不耽誤或增加整個計畫完成之時間下，i 活動所能夠延遲時間之數量 LS(i)–ES(i) = 3，表示 i 活動可以延遲三天也不會影響整個計畫的完成 臨界活動(Critical Activity) 當LS(i) = ES(i)，即LS(i)–ES(i) = 0時，表示 i 是臨界的活動

45 9.9 臨界路徑法 (con.t) 臨界路徑(critical path) V1 V3 a13＝3 a67＝6 a34＝3 a46＝3 V6

46 9.9 臨界路徑法 (con.t) 9.9.1 計算最早發生的時間 如何求得AOE網路的臨界路徑呢？
首先要計算事件最早發生的時間ES(j)及事件最晚發生的時間LS(j) 其中 ES(j) = max{ES(j), ES(i) + <i, j>時間} (i p(j)) p(j)是所有與 j 相鄰頂點所成的集合 計算最早發生的時間 首先我們利用拓樸排序，每當輸出一個事件時，就修正此事件到各事件之最早的時間，如果拓樸排序輸出是事件 j，而事件 j 指向事件 k，此時的 ES(k) = max{ES(k), ES(j) + <j, k>時間}

47 9.9 臨界路徑法 (con.t) 9.9.2 計算最晚開始的時間
計算最晚開始的時間 LS(j) = min{LS(j), LS(i) – <j, i>時間} {i s(j)} s(j)是所有與頂點 j 相鄰頂點的集合 若藉拓樸排序，將每一事件一一輸出時，然後利用 LS(k) = min{LS(k), LS(j) –<j, k>}