Chapter 12 圖形結構 12.1 圖形的一些專有名詞 12.2 圖形資料結構表示法 12.3 圖形追蹤 12.4 擴展樹

Presentation on theme: "Chapter 12 圖形結構 12.1 圖形的一些專有名詞 12.2 圖形資料結構表示法 12.3 圖形追蹤 12.4 擴展樹"— Presentation transcript:

1 Chapter 12 圖形結構 12.1 圖形的一些專有名詞 12.2 圖形資料結構表示法 12.3 圖形追蹤 12.4 擴展樹
12.1 圖形的一些專有名詞 12.2 圖形資料結構表示法 12.3 圖形追蹤 12.4 擴展樹 12.5 最短路徑 12.6 拓樸排序 12.7 臨界路徑法

2 12.1 圖形的一些專有名詞

3 12.1 圖形的一些專有名詞 頂點（vertex）：圖12-3的圓圈稱之。 邊（edge）：圖12-3每個頂點之間的連線稱之。
12.1 圖形的一些專有名詞 頂點（vertex）：圖12-3的圓圈稱之。 邊（edge）：圖12-3每個頂點之間的連線稱之。 無方向圖形（undirected graph）在邊上沒有箭頭者稱之。 有方向圖形（directed graph）：在邊上有箭頭者稱之。

4 12.1 圖形的一些專有名詞 圖形（graph）：是由所有頂點和所有邊組合而成的，以G=(V, E)表示。
12.1 圖形的一些專有名詞 圖形（graph）：是由所有頂點和所有邊組合而成的，以G=(V, E)表示。 多重圖形（mutigraph）：假使兩個頂點間，有多條相同的邊此稱之為多重圖形，而不是圖形。 完整圖形（complete graph）：在n個頂點的無方向圖形中，假使有n(n-1)/2個邊稱之。

5 12.1 圖形的一些專有名詞 相鄰（adjacent）：在圖形的某一邊 (V1, V2) 中，我們稱頂點V1與頂點V2是相鄰的。
12.1 圖形的一些專有名詞 相鄰（adjacent）：在圖形的某一邊 (V1, V2) 中，我們稱頂點V1與頂點V2是相鄰的。 附著（incident）：我們稱頂點V1和頂點V2是相鄰，而邊 (V1, V2) 是附著在頂點V1與V2頂點上。 子圖（subgraph）：假使V(G')V(G)及E(G')E(G)，我們稱G'是G的子圖。

6 12.1 圖形的一些專有名詞

7 12.1 圖形的一些專有名詞 路徑（path）：在圖形G中，從頂Vp到頂 點Vq的路徑是指一系列的頂點Vp, Vi1, Vi2..., Vin, Vq，其中(Vp, Vi1),(Vi1,Vi2)..., (Vin,Vq)是E(G)上的邊。 長度（length）：一條路徑上的長度是 指該路徑上所有邊的數目。

8 12.1 圖形的一些專有名詞 簡單路徑（simple path）：除了頭尾頂點之外，其餘的頂點皆在不相同的路徑上。
12.1 圖形的一些專有名詞 簡單路徑（simple path）：除了頭尾頂點之外，其餘的頂點皆在不相同的路徑上。 循環（cycle）：是指一條簡單路徑上，頭尾頂點皆有相同者稱之。 連通（connected）：在一個圖形G中，如果有一條路徑從V1到V2，那麼我們說 V1與V2是連通的。

9 12.1 圖形的一些專有名詞 圖12-4 G5不是連通的（因為g1與g2無法連接起來）。

10 12.1 圖形的一些專有名詞 連通單元（connected component）：或稱單元（component）是指該圖形中最大的連通子圖（maximum connected subgraph）如圖12-4之G5有兩個單元g1和g2。 緊密連通（strongly connected）：在一有方向圖形中如果V(G)中的每一對不同頂點Vi, Vj 各有一條從Vi到Vj及從Vj到Vi的有方向路徑者稱之。圖12-3 G3不是緊密連通，因為G3沒有V2到V1的路徑。

11 12.1 圖形的一些專有名詞 緊密連通單元（strongly connected component）：是指一個緊密連通最大子圖。如圖12-3 G3有兩個緊密連通單元。 分支度（degree）：附著在頂點的邊數。 內分支度（in-degree）：頂點V的內分支度是指以V為終點（即箭頭指向V）的邊數。 外分支度（out-degree）：頂點V的外分支度是以V為起點的邊數。

12 12.2 圖形資料結構表示法 相鄰矩陣（adjacent matrix）
12.2 圖形資料結構表示法 相鄰矩陣（adjacent matrix） 相鄰矩陣乃是將圖形中的n個頂點（vertices），以一個n×n的二維矩陣來表示，其中每一元素Vij，若Vij = 1，表示圖形中Vi與Vj有一條邊為(Vi , Vj) 。Vij = 0表示頂點i與頂點j沒有邊存在。

13 12.2 圖形資料結構表示法 ij

14 12.2 圖形資料結構表示法 因此相鄰矩陣是對稱性的，而且對角線皆為零，所以圖形中只需要儲存上三角形或下三角形即可，所需儲存空間為n(n-1)/2。 假若要求圖形中某一 頂點相鄰邊的數目 （即分支度），只要 算算相鄰矩陣中某一 列所有1之和或某一 行所有1之和。

15 12.2 圖形資料結構表示法 而在有方向圖形的相鄰矩陣中，列之和表示頂點的外分支度，行之和表示頂點的內分支度。

16 12.2 圖形資料結構表示法 相鄰串列（adjacent list）
12.2 圖形資料結構表示法 相鄰串列（adjacent list） 相鄰串列乃是將圖形中的每個頂點皆形成串列首，而在每個串列首的節點，表示它們之間有邊存在。

17 12.2 圖形資料結構表示法

18 12.2 圖形資料結構表示法

19 12.2 圖形資料結構表示法 從圖12-6 G1“知此圖形有4個頂點（因為有4個串列首），頂點2有3個邊（因為頂點2的串列首後有3個節點，分別節點1、節點3和節點4），餘此類推。 我們也可以從相鄰串列中得知某一頂點的分支度，由此頂點串列首後有n個節點便可計算出來。如圖12-6 G2"中頂點2的分支度是3，因為以頂點2之串列首後有3個節點分別是節點1、節點4和節點5。

20 12.2 圖形資料結構表示法 在有方向圖形中，每個串列首後面的節點數，表示此頂點的外分支度數目。如圖12-6 G3“的頂點2其後有1個節點，因此我們知頂點2的外分支度為1。 若要求內分支度的數目，則必須是把G3"變成相反的相鄰串列。步驟如下：

21 12.2 圖形資料結構表示法 先把圖12-5 G3'變為轉置矩陣（transpose matrix）

22 12.2 圖形資料結構表示法 再把轉置矩陣變為相鄰串列： 由此可知頂點1的內分支度0，頂點2的內分支度為2，而頂點3的內分支度為1。

23 12.3 圖形追蹤 圖形的追蹤是從圖形的某一頂點開始，去拜訪圖形的其他頂點。 圖形的追蹤有兩種方法：
12.3 圖形追蹤 圖形的追蹤是從圖形的某一頂點開始，去拜訪圖形的其他頂點。 圖形的追蹤有兩種方法： 縱向優先搜尋（depth first search） 橫向優先搜尋（breadth first search）

24 12.3 圖形追蹤 縱向優先搜尋（depth first search）： 圖形縱向優先搜尋的過程是： 先拜訪起始點V；
12.3 圖形追蹤 縱向優先搜尋（depth first search）： 圖形縱向優先搜尋的過程是： 先拜訪起始點V； 然後選擇與V相鄰而未被拜訪的頂點W，以W為起始點做縱向優先搜尋； 假使有一頂點其相鄰的頂點皆被拜訪過時，就退回到最近曾拜訪過之頂點，其尚有未被拜訪過的相鄰頂點，繼續做縱向優先搜尋； 假若從任何已走過的頂點，都無法再找到未被走過的相鄰頂點時，此時搜尋就結束了。 其實縱向優先搜尋乃是以堆疊（stack）方式來操作。

25 12.3 圖形追蹤圖形追蹤

26 12.3 圖形追蹤 先輸出V1(V1為起點) 。 將V1的相鄰頂點V2及V3放入 堆疊中。
12.3 圖形追蹤 先輸出V1(V1為起點) 。 將V1的相鄰頂點V2及V3放入 堆疊中。 彈出堆疊的第一個頂點V2，然後 將V2的相鄰頂點V1, V4及V5推入 到堆疊。

27 12.3 圖形追蹤 彈出V1，由於V1已被輸出，故再彈 出V4，將V4的相鄰頂點V2及V8放入堆疊。
12.3 圖形追蹤 彈出V1，由於V1已被輸出，故再彈 出V4，將V4的相鄰頂點V2及V8放入堆疊。 (5)彈出V2，由於V2已被輸出過， 故再彈出V8，再將V8的相鄰 頂點V4、V5及V10放入堆疊。

28 12.3 圖形追蹤 彈出V4，由於V4已輸出過，故再彈出V5，然後將V5的相鄰頂點V2及V8放入堆疊中。
12.3 圖形追蹤 彈出V4，由於V4已輸出過，故再彈出V5，然後將V5的相鄰頂點V2及V8放入堆疊中。 彈出V2及V8，由於此二頂點已 被輸出過，故再彈出V10，再 將V10 的相鄰點V8及V9放入堆疊。

29 12.3 圖形追蹤 彈出V8，此頂點已被輸出，故再彈出V9，將V9的相鄰頂點V6、V7及V1放入堆疊。
12.3 圖形追蹤 彈出V8，此頂點已被輸出，故再彈出V9，將V9的相鄰頂點V6、V7及V1放入堆疊。 彈出V6，再將V6的相鄰頂點V3及V9放入堆疊。

30 12.3 圖形追蹤 彈出V3，將V1 、 V6與V7放入堆疊。 彈出V1及V6，此二頂點已被輸出，故再彈出V7，再將V3及V9放入堆疊。

31 12.3 圖形追蹤 最後彈出V3, V9, V9, V7, V10, V5, V3，由於這些頂點皆已輸出過；此時堆疊是空的，表示搜尋已結束。
12.3 圖形追蹤 最後彈出V3, V9, V9, V7, V10, V5, V3，由於這些頂點皆已輸出過；此時堆疊是空的，表示搜尋已結束。 從上述的搜尋步驟可知其順序為：V1, V2, V4, V8, V5, V10, V9, V6, V3, V7。讀者需注意的是此順序並不是唯一，而是根據頂點放入堆疊的順序而定。

32 12.3 圖形追蹤 橫向優先搜尋（breadth first search） 橫向搜尋先拜訪完所有的相鄰頂點，再去找尋下一層的其他頂點。
12.3 圖形追蹤 橫向優先搜尋（breadth first search） 橫向搜尋先拜訪完所有的相鄰頂點，再去找尋下一層的其他頂點。 如圖12-7以橫向優先搜尋，其拜訪頂點的順序是V1, V2, V3, V4, V5, V6, V7, V8, V9, V10。 縱向優先搜尋是以堆疊來操作，而橫向優先搜尋則以佇列來運作。

33 12.3 圖形追蹤 先拜訪V1並將相鄰的V2及V3也放入佇列。 拜訪V2，再將V2的相鄰頂點V4及V5放入佇列。
12.3 圖形追蹤 先拜訪V1並將相鄰的V2及V3也放入佇列。 拜訪V2，再將V2的相鄰頂點V4及V5放入佇列。 （由於V1已被拜訪過，故不放入佇列中。）

34 12.3 圖形追蹤 拜訪V3，並將V6及V7放入佇列。 （同理V1也已拜訪過，故也不放入佇列。）
12.3 圖形追蹤 拜訪V3，並將V6及V7放入佇列。 （同理V1也已拜訪過，故也不放入佇列。） 拜訪V4，並將V4放入佇列（由於V2已被拜訪過，故不放入佇列。）

35 12.3 圖形追蹤 以此類推，最後得知，以橫向優先搜尋的拜訪順序是： V1, V2, V3, V4, V5, V6, V7, V8, V9, V10 。

36 12.3 圖形追蹤 若G是一顆樹，則必須具備： G有n-1個邊，而且沒有循環； G是連通的。如圖12-3 G2共有7個頂點，有6個邊，沒有循環，而且是連通的。 此樹稱為自由樹（free tree），此時若加上一邊時，則會形成循環。假若一圖形有循環的現象，則稱此圖形為cyclic；若沒有循環，則稱此圖形為 acyclic。

37 12.4 擴展樹 擴展樹(spanning tree)是 以最少的邊數，來連接圖 形中所有的頂點。 下列是其部份的擴展樹

38 12.4 擴展樹 假若使用縱向優先搜尋的追蹤方式，則稱為縱向優先搜尋擴展樹。 若使用橫向優先搜尋的追蹤方式，則稱為橫向優先搜尋擴展樹。
12.4 擴展樹 假若使用縱向優先搜尋的追蹤方式，則稱為縱向優先搜尋擴展樹。 若使用橫向優先搜尋的追蹤方式，則稱為橫向優先搜尋擴展樹。 因此我們可將圖12-7畫出其兩種不同追蹤方式所產生的擴展樹，如圖12-8(a) (b)所示。

39 12.4 擴展樹

40 12.4 擴展樹 求最小成本擴展樹有兩種方法： Prim's algorithm Kruskal's algorithm

41 12.4 擴展樹 Prim's algorithm 有一網路，G = (V, E)，其中V = {1, 2, 3, ....., n }起初設定U={1}，U及V是兩個頂點的集合，然後從V-U集合中找一頂點x，能與U集合中的某頂點形成最小的邊，把這一頂點x加入U集合，繼續此步驟，直到U集合等於V集合為止。

42 12.4 擴展樹

43 12.4 擴展樹 若以Prim's algorithm來找最小成本擴展樹，其過程如下：
12.4 擴展樹 若以Prim's algorithm來找最小成本擴展樹，其過程如下： V= {1, 2, 3, 4, 5, 6, 7}，U = {1}。 從V-U = {2, 3, 4, 5, 6, 7}中找一頂點， 與U = {1}頂點能形成最小成本的邊； 發現是頂點6，然後加此頂點於U中， U= {1, 6}。

44 12.4 擴展樹 此時V-U = {2, 3, 4, 5, 7}，從這些頂點找一頂點，與U = {1, 6}頂點能形成最小成本的邊，答案是頂點5，因為其成本或距離為9；加此頂點於U中，U = {1, 5, 6}，V-U = {2, 3, 4, 7}。

45 12.4 擴展樹 以同樣方法找到一頂點2，能與V中的頂點1形成最小的邊，加此頂點於U中，
12.4 擴展樹 以同樣方法找到一頂點2，能與V中的頂點1形成最小的邊，加此頂點於U中， U = {1, 2, 5, 6}，V-U = {3, 4, 7}

46 12.4 擴展樹 同樣方法將頂點3加入U中，U ={1, 2, 3, 5, 6}，V-U = {4, 7}。
12.4 擴展樹 同樣方法將頂點3加入U中，U ={1, 2, 3, 5, 6}，V-U = {4, 7}。 以同樣的方法將頂點4加入U中，U = {1, 2, 3, 4, 5, 6}，V-U = {7}。

47 12.4 擴展樹 將頂點7加入U中，U = {1, 2, 3, 4, 5, 6, 7}，V-U =∮，V = U，此時的圖形就是最小成本擴展樹。

48 12.4 擴展樹 Kruskal's algorithm
12.4 擴展樹 Kruskal's algorithm 有一網路G = (V,E)，V={1, 2, 3, ....., n}，E中每一邊皆有一成本，T = (v,∮)表示開始時沒有邊。 首先從E中找具有最小成本的邊；若此邊加入T中不會形成循環，則將此邊從E刪除並加入T中，直到T中含有n-1個邊為止。

49 12.4 擴展樹 圖12-9以Kruskal's algorithm來找出最小成本擴展樹，其過程如下：
12.4 擴展樹 圖12-9以Kruskal's algorithm來找出最小成本擴展樹，其過程如下： 在圖12-9中以頂點1到 頂點6的邊具最小成本。 同樣方法頂點2到 頂點3的邊具有 最小成本。

50 12.4 擴展樹 以同樣的方法可知頂點2到頂點4的邊有最小成本。 以同樣的方法知頂點5到頂點6的邊有最小成本。

51 12.4 擴展樹 從其餘的邊中，知頂點3到頂點4具有最小成本，但此邊加入T後會形成循環，故不考慮，而以頂點2到頂點7邊加入T中。

52 12.4 擴展樹 由於頂點4到頂點7的邊會使T形成循環，故不考慮，最後最小成本擴展樹如下：

53 12.4 擴展樹 因此我們發現不論由Prim's algorithm或Kruskal's algorithm來求最小成本擴展樹，所得到的圖形是一樣的。

54 12.5 最短路徑 要找出某一頂點到其他節點的最短路徑，可以利用Dijkstra‘s algorithm求得。 其過程如下：

55 12.5 最短路徑 步驟1： D[I] = A[F, I] (I = 1, N) S = {F}
12.5 最短路徑 步驟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也是頂點的集合。

56 12.5 最短路徑 步驟2：從V-S集合中找一頂點t使得D[t]是最小值，並將t放入S集合，一直到V-S是空集合為止。
12.5 最短路徑 步驟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執行。

57 12.5 最短路徑 圖12-10頂點表示城市，邊是表示兩城市之間所需花費的成本。

58 12.5 最短路徑 F = 1 ; S = {1} , V = {1, 2, 3, 4, 5, 6, 7} 很清楚的看出D陣列中D[2] = 4最少，因此將頂點2加入到S集合中，S = {1, 2}，V-S = {3, 4, 5, 6, 7}，而且頂點2之相鄰頂點有3和5，所以

59 12.5 最短路徑 D[3] = min(D[3], D[2]+A[2, 3]) =min(6, 4+1) = 5 此時D陣列變為
12.5 最短路徑 D[3] = min(D[3], D[2]+A[2, 3]) =min(6, 4+1) = 5 D[5] = min(D[5], D[2]+A[2, 5]) = min(∞, 4+7) = 11 此時D陣列變為

60 12.5 最短路徑 從V-S = {3, 4, 5, 6, 7}中找出D陣列的最小值是D[3] = 5，而頂點3的相鄰點為5、6
12.5 最短路徑 從V-S = {3, 4, 5, 6, 7}中找出D陣列的最小值是D[3] = 5，而頂點3的相鄰點為5、6 ∴S = {1, 2, 3}，V-S = {4, 5, 6, 7} D[5] = min(D[5], D[3]+A[3, 5]) = min(11, 5+6) = 11 D[6] = min(D[6], D[6]+A[3, 6]) = min(∞, 5+4) = 9 所以D陣列變為

61 12.5 最短路徑 從V-S = {4, 5, 6, 7}中挑出最小為D[4] = 6而4的相鄰點為3、6 ∴D[3] = min(D[3], D[4]+A[4, 3]) = min(5, 6+2) = 5 D[6] = min(D[6], D[4]+A[4, 6]) = min(9, 6+5) = 9 所以D陣列為

62 12.5 最短路徑 將4加入S集合中，從V-S = {5, 6, 7}中得知D[6] = 9為最小而頂點6與頂點5、7相鄰 所以D陣列變為
12.5 最短路徑 將4加入S集合中，從V-S = {5, 6, 7}中得知D[6] = 9為最小而頂點6與頂點5、7相鄰 D[5] = min(D[5], D[6]+A[6, 5]) = min(11, 9+1) = 10 D[7]= min(D[7], D[6]+A[6, 7]) = min(∞, 9+8) = 17 所以D陣列變為 將6加入S集合後，V-S = {5, 7}

63 12.5 最短路徑 從V-S = {5, 7}集合中，得知D[5] = 10最小，而頂點5的相鄰頂點7。將5加入S，V-S = {7}
12.5 最短路徑 從V-S = {5, 7}集合中，得知D[5] = 10最小，而頂點5的相鄰頂點7。將5加入S，V-S = {7} D[7] = min(D[7], D[5]+A[5, 7]) = min(17, 10+6) = 16 由於頂點7為最終頂點，將其加入S集合後，V-S = {∮}，最後D陣列為

64 12.5 最短路徑 此陣列表示從頂點1到任何頂點的距離，如D[7]表示從頂點1到頂點7的距離為16。餘此類推。
12.5 最短路徑 此陣列表示從頂點1到任何頂點的距離，如D[7]表示從頂點1到頂點7的距離為16。餘此類推。 假若我們也想知道從頂點1到頂點7所經過的頂點也很簡單，首先假設有一列Y其情形如下：

65 12.5 最短路徑 由於1為起始頂點，故將Y陣列初始值皆設為1。然後檢查上述1-4步驟，凡是D[I] > D[t]+A[t, I]的話，則將t放入Y[I]中，在步驟1 中，D[3] > D[2]+A[2,3]且D[5] > D[2]+A[2, 5]，所以將2分別放在Y[3]和Y[5]中。

66 12.5 最短路徑 步驟2中，D[6] > D[3]+A[3, 6]，所以將3放入Y[6]中。
12.5 最短路徑 步驟2中，D[6] > D[3]+A[3, 6]，所以將3放入Y[6]中。 在步驟3中，D[5] > D[6]+A[6, 5]，D[7] > D[6]+A[6, 7]，故分別將6放在Y[5]和Y[7]中。

67 12.5 最短路徑 在步驟4中，D[7] >D[5]+A[5, 7]，故將5放入Y[7]中。

68 12.5 最短路徑 此為最後的Y陣列，表示到達頂點7必須先經過頂點5，經過頂點5必先經過頂點6，經過頂點6必先經過頂點3，而經過頂點3必須先經過頂點2，因此經過的頂點為頂點1-->頂點2-->頂點3-->頂點6-->頂點5-->頂點7。

69 12.5 最短路徑 另一種表達方式 上述的解決方式似乎繁瑣了一點，筆者現利用另一種表達方式，讀者比較一下是否簡單了一些，但是其基本原理是一樣的，即是直接從A走到B不見得是最短的，也許從A經由C再到B是最短的。

70 12.5 最短路徑 假設Uj是從頂點1到頂點j最短的距離，U1 = 0而Uj的值 (j =2, 3, ....., n) 計算如下：
12.5 最短路徑 假設Uj是從頂點1到頂點j最短的距離，U1 = 0而Uj的值 (j =2, 3, ....., n) 計算如下： Uj = min{Ui + dij}，其中Ui為頂點1到頂點i的最短距離。 dij為從i到j的距離。 此處的i表示到j頂點的前一個頂點，因此有可能不止一個。

71 12.5 最短路徑 上述是計算從頂點1到各頂點的最短距離，其經過的頂點，我們也可以將其記錄起來。頂點j記錄標籤 = [Uj, n]，n為使得Uj為最短距離的前一頂點；因此 Uj = min{Ui + dij} = Un+dnj 首先頂點1定義為[0,-]

72 12.5 最短路徑

73 12.6 拓樸排序 AOV-network：在一個有方向圖形中，每一頂點代表工作（task）或活動（activity），而邊表示工作之間的優先順序（precedence relations）。 即邊（Vi, Vj）表示Vi的工作必先處理完後才能去處理Vj的工作，此種有方向圖形稱之為activity on vertex network或AOV-network。

74 12.6 拓樸排序

75 12.6 拓樸排序 立即前行者（immediate predecessor）與立即後繼者（immediate successor）：若在有方向圖形G中有一邊<Vi, Vj>，則稱Vi是Vj的立即前行者，而Vj是Vi的立即後繼者。 在圖12-12中V7是V8, V9, V10的立即前行者，而V8, V9, V10是V7的立即後繼者。

76 12.6 拓樸排序 前行者（predecessor）與後繼者（successor）：在AOV-network中，假若從頂點Vi到頂點Vj存在一條路徑，則稱Vi是Vj的前行者，而Vj是Vi的後繼者。 如圖12-12 V3是V6的前行者，而V6是V3的後繼者。

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

78 12.6 拓樸排序

79 12.6 拓樸排序 輸出V1，並刪除<V1, V2>與<V1, V6>兩個邊。

80 12.6 拓樸排序 此時V2和V6皆沒有前行者，若輸出V2則刪除<V2, V3>與<V2, V4>兩個邊。

81 12.6 拓樸排序 運用相同的原理，選擇輸出V6，並刪除<V6, V4>與<V6, V5>兩個邊。
12.6 拓樸排序 運用相同的原理，選擇輸出V6，並刪除<V6, V4>與<V6, V5>兩個邊。 輸出V3，並刪除<V3, V5>與<V3, V7>兩個邊。

82 12.6 拓樸排序 輸出V4，並刪除<V4, V5>。 輸出V5，並刪除<V5, V8> 。
12.6 拓樸排序 輸出V4，並刪除<V4, V5>。 輸出V5，並刪除<V5, V8> 。 輸出V7，並刪除<V7, V8>。 輸出V8。

83 12.6 拓樸排序 圖12-13的拓樸排序並非只有一種，因為在過程2時，假若選的頂點不是V2，其拓樸排序所排出來的順序就會不一樣。
12.6 拓樸排序 圖12-13的拓樸排序並非只有一種，因為在過程2時，假若選的頂點不是V2，其拓樸排序所排出來的順序就會不一樣。 因此AOV-network的拓樸排序並不是唯一。 若依上述的方式，其資料的排序順序是V1, V2, V6, V3, V4, V5, V7及V8。

84 12.7 臨界路徑法 利用AOV-network的邊來代表某種活動（activity），而頂點表示事件（events），則稱此網路為AOE-network。 圖12-15是一個AOE-network，其中有7個事件分別是V1, V2, V3,..., V7，有11個活動分別為a12, a13, a15, a24, a34, a35, a45, a46, a47, a57, a67。 而且從圖12-14可知V1這個專案（project）的起始點，V7是結束點，其他如V5表示必須完成活動。

85 12.7 臨界路徑法 a13 = 3 表示V1到V3所需的時間為3天，a35 = 2 為V3到V5所需的時間為2天，餘此類推。
12.7 臨界路徑法 a13 = 3 表示V1到V3所需的時間為3天，a35 = 2 為V3到V5所需的時間為2天，餘此類推。 而a45為虛擬活動路徑（dummy activity path）其值為0，因為我們假設V5需要V1, V3及V4事件完成之後才可進行事件V5。

86 12.7 臨界路徑法

87 12.7 臨界路徑法 目前有不少的技術已開發完成，用來評估各個計畫的績效，如專案評估與技術查核（Project Evaluation and Review Technique, PERT）及臨界路徑法（Critical Path Method, CPM）。 一個計畫所需完成的最短時間，是從起始點到結束點間最短的路徑來算。長度為最長的路徑稱為臨界路徑（Critical Path）。

88 12.7 臨界路徑法 在AOE-network上所有的活動皆有兩種時間：
12.7 臨界路徑法 在AOE-network上所有的活動皆有兩種時間： 最早時間（Early time）表示一活動最早開始的時間，以earliest (i) 表示活動ai最早開始的時間； 最晚時間（Latest time）指一活動在不影響整個計畫完成之下，最晚能夠開始進行的時間，以latest(i)表示活動ai最晚的時間。

89 12.7 臨界路徑法 latest(i)減去earliest(i)為一活動臨界之數量，它表示在不耽誤或增加整個計畫完成之時間下，i活動所能夠延遲時間之數量。 例如latest(i) - earliest(i) =3，表示i活動可以延遲三天也不會影響整個計畫的完成。當latest(i) = earliest(i)時，表示i活動是臨界的活動（Critical Activity）。

90 12.7 臨界路徑法 臨界路徑分析的目的，在於辨別那些路徑是臨界活動，以便能夠集中資源在這些臨界活動上，進而縮短計畫完成的時間。
12.7 臨界路徑法 臨界路徑分析的目的，在於辨別那些路徑是臨界活動，以便能夠集中資源在這些臨界活動上，進而縮短計畫完成的時間。 然而並不是加速臨界活動就可以縮短計畫完成的時間，除非此臨界活動是在全部的臨界路徑上。 圖12-15的臨界路徑如圖12-16所示：

91 12.7 臨界路徑法

92 12.7 臨界路徑法 若將圖12-15 a47的活動增加速度，由原來的3天提前2天完成，並不會使整個計畫提前1天，它仍需15天才可完成。
12.7 臨界路徑法 若將圖12-15 a47的活動增加速度，由原來的3天提前2天完成，並不會使整個計畫提前1天，它仍需15天才可完成。 因為還有一條臨界路徑V1, V3, V4, V6, V7，其不包括a47，故不會縮短計畫完成的時間。但若將a13由原來的3天加快速度，使其1天就可完成，此時整個計畫就可提前2天完成，故只需13天就可完成。

93 12.7 臨界路徑法 計算事件最早發生的時間 首先要計算事件最早發生的時間earliest及事件最晚發生的時間latest(j)，其中： earliest(j) = max { earliest(j), earliest(i) +<i,j>時間 } i p(j) p(j) 是所有與j相鄰頂點所成的集合。 將圖12-15以相鄰串列表示之，如圖12-17所示：

94 12.7 臨界路徑法

95 12.7 臨界路徑法 12.7.2 計算事件最晚發生的時間 接下來計算事件最晚發生的時間latest(j)，計算如下：
12.7 臨界路徑法 計算事件最晚發生的時間 接下來計算事件最晚發生的時間latest(j)，計算如下： latest(j)=min{latest(j), latest(i)-<j,i>時間} i s(j) 此處s(j)是所有頂點j的相鄰頂點。 將圖12-14以反相鄰串列表示之，如圖12-18

96 12.7 臨界路徑法