數(shù)據(jù)結(jié)構(gòu)之圖

1、圖2/108主要內(nèi)容 圖的基本概念圖的基本概念 圖的抽象數(shù)據(jù)類型圖的抽象數(shù)據(jù)類型 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu) 圖的周游圖的周游 最短路徑問題最短路徑問題 最小支撐樹最小支撐樹圖3/108圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。線性表線性表: 線性結(jié)構(gòu)線性結(jié)構(gòu)樹樹: 層次結(jié)構(gòu)層次結(jié)構(gòu)圖圖: 結(jié)點之間的關(guān)系可以是任意的，即圖中任意兩個結(jié)點之間的關(guān)系可以是任意的，即圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。數(shù)據(jù)元素之間都可能相關(guān)。 ABCDE圖的基本概念圖4/108圖圖 G 是由兩個集合頂點集是由兩個集合頂點集 V(G) 和邊集和邊集 E(G) 組成的，記組成的，記作作

2、G=( V(G)，E(G) )，簡稱，簡稱G=(V，E)。ABCDEABCDEABCDEV(vertex)是頂點的有窮非空集合是頂點的有窮非空集合 E(edge)是兩個頂點之間的關(guān)系，即邊的有窮集合是兩個頂點之間的關(guān)系，即邊的有窮集合 圖的定義和基本術(shù)語圖5/108無向圖無向圖: 邊是頂點的無序?qū)Γ催厸]有方向性。邊是頂點的無序?qū)?，即邊沒有方向性。v1v2v3v5v4V = v1 , v2 , v3 , v4 , v5 E = ( v1 ,v2 ) , ( v1 ,v4 ) , ( v2 ,v3 ) , ( v2 ,v5 ) , ( v3 ,v4 ) , ( v3 ,v5 ) ( v1 , v

3、2 )表示頂點表示頂點 v1 和和 v2 之間的邊，之間的邊， ( v1 , v2 ) = ( v2 , v1 )。無向圖圖6/108有向圖有向圖: 其邊是頂點的有序?qū)?，即邊有方向性。其邊是頂點的有序?qū)?，即邊有方向性。v1v2v4v3V = v1 , v2 , v3 , v4 E = , , , 通常邊稱為弧，通常邊稱為弧，表示頂點表示頂點 v1 到到 v2 的弧。的弧。稱稱 v1 為弧尾，稱為弧尾，稱 v2 為弧頭。為弧頭。 有向圖圖7/108有時對圖的邊或弧賦予相關(guān)的數(shù)值，這種與有時對圖的邊或弧賦予相關(guān)的數(shù)值，這種與圖的邊或弧相關(guān)的數(shù)值叫做圖的邊或弧相關(guān)的數(shù)值叫做權(quán)權(quán)。 ABCDE5382

4、1497這些權(quán)可以表示從一個頂點到另一個頂點的距離。這些權(quán)可以表示從一個頂點到另一個頂點的距離?？梢员硎緩囊粋€頂點到另一個頂點的耗費?？梢员硎緩囊粋€頂點到另一個頂點的耗費。帶權(quán)圖圖8/108性質(zhì)性質(zhì): 若用若用 n 表示圖中頂點數(shù)目，用表示圖中頂點數(shù)目，用 e 表示表示邊或弧邊或弧的數(shù)的數(shù)目，若在圖中不存在頂點到自身的邊或弧，則目，若在圖中不存在頂點到自身的邊或弧，則對于無向圖，對于無向圖，0 e n(n- -1)12對于有向圖，對于有向圖，0 e n(n- -1)證明證明: 0 e 顯然成立顯然成立對對有向圖有向圖來說，每個頂點至多可發(fā)出來說，每個頂點至多可發(fā)出 n- -1 條弧，共條弧，共

5、 n 個頂點，個頂點，故至多有故至多有 n(n- -1) 條弧，即條弧，即 e n(n- -1) ；對對無向圖無向圖來說，由于邊無方向，則任一兩個頂點來說，由于邊無方向，則任一兩個頂點 v1 和和 v2，都，都有有 ( v1 , v2 ) = ( v2 , v1 ) ，故至多有，故至多有 n(n- -1) 條邊條邊 ；12基本性質(zhì)圖9/108有有 n(n- -1) 條邊的無向圖稱為條邊的無向圖稱為完全圖完全圖。 12v1v2v4v3有有 n(n-1) 條弧的有向圖稱為條弧的有向圖稱為有向完全圖有向完全圖。 v1v2v3有很少條邊或弧的圖稱為有很少條邊或弧的圖稱為稀疏圖稀疏圖。 反之稱為反之稱為

6、稠密圖稠密圖。 完全圖、稀疏圖、稠密圖圖10/108假設(shè)有兩個圖假設(shè)有兩個圖 G=(V, E) 和和 G=(V, E) ，如果，如果 V V，且，且 E E，則稱，則稱 G 為為 G 的子圖。的子圖。 v1v2v4v3求子圖求子圖v1v1v3v1v4v3v1v2v4v3v1v2v4v3子圖圖11/108v1v2v3v5v4子圖有子圖有v1v2v3v5v1v2v5v4v1v2v3v5v4子圖圖12/108對于無向圖對于無向圖 G=(V, E)，如果，如果邊邊 (v, v) E，則稱頂點，則稱頂點 v 和和 v 互為鄰接點，即互為鄰接點，即 v 和和 v 相相鄰接鄰接。 邊邊 (v, v) 依附于

7、頂點依附于頂點 v 和和 v ，或者說，或者說 (v, v) 與頂點與頂點 v 和和 v 相相關(guān)聯(lián)關(guān)聯(lián)。 對于有向圖對于有向圖 G=(V, E) ，如果弧，如果弧 E，則稱頂點，則稱頂點 v 鄰接到頂點鄰接到頂點 v，頂點，頂點 v 鄰接到頂點鄰接到頂點 v 。 vvvv弧弧 和頂點和頂點 v, v 相關(guān)聯(lián)。相關(guān)聯(lián)。鄰接與關(guān)聯(lián)圖13/108對于無向圖，對于無向圖，頂點頂點 v 的度的度是和是和 v 相關(guān)聯(lián)的邊的數(shù)目，記做相關(guān)聯(lián)的邊的數(shù)目，記做TD(v)。 v1v2v3v5v4頂點頂點 v3 的度為的度為 3對于有向圖，對于有向圖，頂點頂點 v 的度的度 TD(V) 分為兩部分分為兩部分出度、入

8、度出度、入度。 以頂點以頂點 v 為為頭頭的弧的數(shù)目稱為的弧的數(shù)目稱為 v 的入度，記為的入度，記為ID(v) ；以頂點以頂點 v 為為尾尾的弧的數(shù)目稱為的弧的數(shù)目稱為 v 的出度，記為的出度，記為OD(v)； 頂點頂點 v 的度為的度為 TD(v) = ID(v) + OD(v)。 頂點的度圖14/108v1v2v4v3頂點頂點 v1 的出度為的出度為 2頂點頂點 v1 的入度為的入度為 1頂點頂點 v1 的度為的度為 3性質(zhì)性質(zhì): 對于一個圖對于一個圖(無向圖、有向圖無向圖、有向圖)，如果頂點，如果頂點 vi 的度為的度為TD(vi)，那么具有那么具有 n 個頂點、個頂點、e 條邊或弧的圖

9、，必滿足如下關(guān)系條邊或弧的圖，必滿足如下關(guān)系e = TD(vi)12i = 1n無向圖、有向圖的邊或弧均計算無向圖、有向圖的邊或弧均計算兩遍兩遍。頂點的度圖15/108圖圖（無向圖無向圖 、有向圖）、有向圖）G 中若存在一條有窮非空序列中若存在一條有窮非空序列 w = v0 e1 v1 e2 v2 ek vk ，其中，其中 vi 和和 ei 分別為頂點和分別為頂點和邊邊（或（或弧弧），則稱），則稱 w 是從頂點是從頂點 v0 到到 vk 的一條路徑。的一條路徑。頂點頂點 v0 和和 vk 分別稱為路徑分別稱為路徑 w 的起點和終點。的起點和終點。路徑的長度是路徑上的邊的數(shù)目。路徑的長度是路徑上

10、的邊的數(shù)目。w 的長度為的長度為 k起點和終點相同的路徑稱為起點和終點相同的路徑稱為回路回路(環(huán)環(huán))。圖的其它術(shù)語v0v1v2vk- -1vk. . .e1e2ek圖16/108若路徑若路徑 w 的頂點的頂點 v0 , v1 , , vk ，除，除v0 和和vk可以相同之外，其他頂點可以相同之外，其他頂點互不相同，則稱互不相同，則稱 w 為為簡單路徑簡單路徑。如果構(gòu)成回路的路徑是簡單路徑，稱此回路為如果構(gòu)成回路的路徑是簡單路徑，稱此回路為簡單回路簡單回路。不帶回路的圖稱為不帶回路的圖稱為無環(huán)圖無環(huán)圖。不帶回路的有向圖稱為不帶回路的有向圖稱為有向無環(huán)圖有向無環(huán)圖。圖的其它術(shù)語v0v1v2vk-

11、-1vk. . .e1e2ekv0v1v2vk- -1vk. . .e1e2ek圖17/108無向圖無向圖G，如果從頂點，如果從頂點 v 到頂點到頂點 v 有路徑，則稱有路徑，則稱 v 和和 v 是連通的。是連通的。 如果對于無向圖如果對于無向圖 G 中任意兩個頂點中任意兩個頂點 vi , vj V, vi 和和 vj 都是連通的，都是連通的，則稱則稱 G 是是連通圖連通圖。 v1v2v3v5v4是否為連通圖是否為連通圖連通、連通圖、連通分量、強連通圖、強連通分量圖18/108連通分量連通分量指的是無向圖中的指的是無向圖中的最大連通子圖最大連通子圖。 ABCLHDEFGH非連通圖非連通圖連通分

12、量為連通分量為ABCLHDEFGH連通、連通圖、連通分量、強連通圖、強連通分量圖19/108有向圖有向圖G，如果從頂點，如果從頂點 v 到頂點到頂點 v 有路徑有路徑 或或 從頂點從頂點 v 到頂點到頂點 v 有路徑，則稱有路徑，則稱 v 和和 v 是是連通連通的。的。 在在有向圖有向圖 G 中，如果對于每一對中，如果對于每一對 vi, vj V，vivj ，從，從 vi 到到 vj 和和 從從 vj 到到 vi 都存在路徑，則稱都存在路徑，則稱 G 是是強連通圖強連通圖。 v1v2v4v3是否為強連通圖是否為強連通圖連通、連通圖、連通分量、強連通圖、強連通分量圖20/108有向圖中的有向圖中

13、的最大強連通子圖最大強連通子圖稱作有向圖的稱作有向圖的強連通分量強連通分量。 v1v2v4v3非強連通圖非強連通圖強連通分量強連通分量v2v1v4v3連通、連通圖、連通分量、強連通圖、強連通分量圖21/108網(wǎng)絡(luò)、自由樹 網(wǎng)絡(luò)網(wǎng)絡(luò) 帶權(quán)的連通圖。帶權(quán)的連通圖。 自由樹（自由樹（free tree） 不帶有簡單回路的無向圖，它是連通的，并不帶有簡單回路的無向圖，它是連通的，并且具有且具有|V|-1條邊。條邊。圖22/108圖的抽象數(shù)據(jù)類型class Graph /圖的圖的ADTpublic: int VerticesNum(); /返回圖的頂點個數(shù)返回圖的頂點個數(shù) int EdgesNum();

14、 /返回圖的邊數(shù)返回圖的邊數(shù) /返回與頂點返回與頂點oneVertex相關(guān)聯(lián)的第一條邊相關(guān)聯(lián)的第一條邊 Edge FirstEdge(int oneVertex); /返回與邊返回與邊PreEdge有相同關(guān)聯(lián)頂點有相同關(guān)聯(lián)頂點oneVertex的的下一條邊下一條邊 Edge NextEdge(Edge preEdge); 圖23/108圖的抽象數(shù)據(jù)類型（續(xù)）/添加一條邊添加一條邊 bool setEdge(int fromVertex,int toVertex,int weight); /刪一條邊刪一條邊 bool delEdge(int fromVertex,int toVertex);/如

15、果如果oneEdge是邊則返回是邊則返回TRUE，否則返回，否則返回FALSE bool IsEdge(Edge oneEdge); /返回邊返回邊oneEdge的始點的始點 int FromVertex(Edge oneEdge); /返回邊返回邊oneEdge的終點的終點 int ToVertex(Edge oneEdge); /返回邊返回邊oneEdge的權(quán)的權(quán) int Weight(Edge oneEdge); ; 圖24/108順序存儲順序存儲鄰接矩陣鄰接矩陣鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯︵徑颖磬徑颖磬徑佣嘀乇磬徑佣嘀乇砣绾伪磉_(dá)頂點之間存在的聯(lián)系？如何表達(dá)頂點之間存在的聯(lián)系？多重鏈表，如何設(shè)計結(jié)點

16、結(jié)構(gòu)？多重鏈表，如何設(shè)計結(jié)點結(jié)構(gòu)？圖的存儲結(jié)構(gòu)圖25/108習(xí)慣性約定為每一個頂點設(shè)定一個序號，表示為每一個頂點設(shè)定一個序號，表示“頂點在圖中的頂點在圖中的位置位置”。12354圖26/108設(shè)圖設(shè)圖 G = ( V ，E ) 具有具有 n(n1) 個頂點個頂點 v1 , v2 , , vn 和和 m 條邊或弧條邊或弧 e1 , e2 , , em ，則，則 G 的鄰接矩陣是的鄰接矩陣是 nn 階階矩陣，記為矩陣，記為 A(G) 。其每一個元素其每一個元素 aij 定義為定義為:鄰接矩陣存放鄰接矩陣存放 n 個頂點信息和個頂點信息和 n2 條邊或弧信息。條邊或弧信息。aij = 01頂點頂點

17、vi 與與 vj 不相鄰接不相鄰接頂點頂點 vi 與與 vj 相鄰接相鄰接v1v2v4v3例例有向圖有向圖 GA(G) = 1 2 3 412340 1 1 00 0 0 00 0 0 11 0 0 0鄰接矩陣圖27/108v1v2v3v5v4例例無向圖無向圖 G0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0A(G) = 1 2 3 4 512345優(yōu)點優(yōu)點:1. 容易判斷任意兩個頂點之間是否有邊或弧。容易判斷任意兩個頂點之間是否有邊或弧。2. 容易求取各個頂點的度。容易求取各個頂點的度。鄰接矩陣圖28/108無向圖，頂點無向圖，頂點 vi 的度是鄰

18、接矩陣中第的度是鄰接矩陣中第 i 行或第行或第 i 列的元素之和。列的元素之和。例例 G1中，中，v1 的度為的度為 2。v1v2v3v5v4例無向圖例無向圖 G0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0A(G) = 1 2 3 4 512345鄰接矩陣圖29/108v1v2v4v3例有向圖例有向圖 GA(G) = 1 2 3 412340 1 1 00 0 0 00 0 0 11 0 0 0有向圖，頂點有向圖，頂點 vi 的出度是鄰接矩陣中第的出度是鄰接矩陣中第 i 行的元素之和。行的元素之和。頂點頂點 vi 的入度是鄰接矩陣中第的入度是鄰接矩

19、陣中第 i 列的元素之和。列的元素之和。例例 v1 的出度為的出度為 2；入度為；入度為 1。鄰接矩陣圖30/108無向圖的鄰接矩陣都是無向圖的鄰接矩陣都是對稱矩陣對稱矩陣。有向圖的鄰接矩陣一般不對稱。有向圖的鄰接矩陣一般不對稱。1 2 3 412340 1 1 00 0 0 00 0 0 11 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 01 2 3 4 512345故無向圖可以采用壓縮存儲方式故無向圖可以采用壓縮存儲方式無向圖無向圖有向圖有向圖鄰接矩陣圖31/108v1v2v3v5v4v65487935651aij = wij頂點頂點

20、vi 與與 vj 相鄰接相鄰接頂點頂點 vi 與與 vj 不相鄰接不相鄰接 5 7 4 8 9 5 6 5 A = 1 2 3 4 5 6123456 3 1 帶權(quán)圖(網(wǎng)) 的鄰接矩陣圖32/108對圖中每一個頂點建立一個單鏈表，指示與該頂點關(guān)聯(lián)的對圖中每一個頂點建立一個單鏈表，指示與該頂點關(guān)聯(lián)的邊邊或或出弧出弧。vexinfo firstarcadjvexnextarcarcinfo表結(jié)點表結(jié)點頭結(jié)點頭結(jié)點adjvex : 鄰接頂點位置鄰接頂點位置arcinfo : 邊的信息邊的信息nextarc : 下一條關(guān)聯(lián)邊結(jié)點下一條關(guān)聯(lián)邊結(jié)點vexinfo : 頂點的信息頂點的信息firstarc

21、: 第一條關(guān)聯(lián)邊結(jié)點第一條關(guān)聯(lián)邊結(jié)點鄰接表圖33/108v1v2v3v5v4例無向圖例無向圖 Ge1e2e3e4e5e601234v1v2v3v4v53e21e14e42e30e14e63e51e32e50e22e61e4如何獲取頂點的度？如何獲取頂點的度？頂點頂點 vi 的度為第的度為第 i 條鏈表中的結(jié)點數(shù)。條鏈表中的結(jié)點數(shù)。需要多少存儲空間？需要多少存儲空間？n + 2e鄰接表圖34/108v1v2v4v3例例有向圖有向圖 Ge1e2e3e40123v1v2v3v42e21e13e30e4如何獲取頂點的度？如何獲取頂點的度？頂點頂點 vi 的的出度出度為第為第 i 條條鏈表中的結(jié)點數(shù)。鏈

22、表中的結(jié)點數(shù)。需要多少存儲空間？需要多少存儲空間？n + e為了方便求頂點的為了方便求頂點的入度入度，引入引入逆鄰接表逆鄰接表0123v1v2v3v40e13e40e22e3最終需要多少存儲空間？最終需要多少存儲空間？2n + 2e鄰接表圖35/108鄰接矩陣與鄰接表鄰接矩陣與鄰接表存儲空間存儲空間求頂點的度求頂點的度求頂點的鄰接頂點求頂點的鄰接頂點鄰接表鄰接表一樣一樣一樣一樣判斷兩個頂點是否關(guān)聯(lián)判斷兩個頂點是否關(guān)聯(lián)鄰接矩陣鄰接矩陣0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 01 2 3 4 51234501234v1v2v3v4v53e21e14e

23、42e30e14e63e51e32e50e22e61e4鄰接矩陣與鄰接表比較圖36/108鄰接多重表 把鄰接表表示中代表同一條邊的兩個表目合為把鄰接表表示中代表同一條邊的兩個表目合為一個表目一個表目 圖的每條邊只用一個多重表表目表示圖的每條邊只用一個多重表表目表示 包括此邊的兩個頂點的序號包括此邊的兩個頂點的序號 兩個指針（一個指針指向與第一個頂點相關(guān)聯(lián)的下兩個指針（一個指針指向與第一個頂點相關(guān)聯(lián)的下一條邊，另一個指針指向與第二個頂點相關(guān)聯(lián)的下一條邊，另一個指針指向與第二個頂點相關(guān)聯(lián)的下一條邊）一條邊） 在以處理圖的邊為主，要求每條邊處理一次的在以處理圖的邊為主，要求每條邊處理一次的實際應(yīng)用中

24、特別有用。實際應(yīng)用中特別有用。圖37/108鄰接多重表無向圖無向圖有向圖有向圖圖38/108鄰接多重表G6的鄰接多重表表示圖39/108有向圖鄰接多重表 在頂點表中設(shè)計兩個指針在頂點表中設(shè)計兩個指針第一個指向以此頂點為始點的第一條邊第一個指向以此頂點為始點的第一條邊第二個指向以此頂點為終點的第一條邊第二個指向以此頂點為終點的第一條邊 邊表邊表第一個指針指向始點與本邊始點相同的下一條邊第一個指針指向始點與本邊始點相同的下一條邊第二個指針指向終點與本邊終點相同的下一條邊第二個指針指向終點與本邊終點相同的下一條邊 故僅用表中第一個鏈便得到有向圖的出邊表，故僅用表中第一個鏈便得到有向圖的出邊表，僅用第

25、二個鏈便得到有向圖的入邊表僅用第二個鏈便得到有向圖的入邊表 圖40/108鄰接多重表G7的鄰接多重表表示圖41/108課堂練習(xí) 給出下圖的鄰接矩陣、鄰接表和鄰接多給出下圖的鄰接矩陣、鄰接表和鄰接多重表表示。重表表示。A B C D E F 圖42/1086.4 圖的周游 圖的周游（圖的周游（graph traversal） 給出一個圖給出一個圖G和其中任意一個頂點和其中任意一個頂點V0，從，從V0出發(fā)系統(tǒng)地訪問出發(fā)系統(tǒng)地訪問G中所有的頂點，每個頂點中所有的頂點，每個頂點訪問一次，這叫做訪問一次，這叫做圖的周游圖的周游。深度優(yōu)先搜索深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索圖43/1086.4.1 深

26、度優(yōu)先搜索 深度優(yōu)先搜索（深度優(yōu)先搜索（depth-first search，簡稱，簡稱DFS） 基本思想基本思想 訪問一個頂點訪問一個頂點V，然后訪問該頂點鄰接到的未被訪問過，然后訪問該頂點鄰接到的未被訪問過的頂點的頂點V， 再從再從V出發(fā)遞歸地按照深度優(yōu)先的方式周游，出發(fā)遞歸地按照深度優(yōu)先的方式周游， 當(dāng)遇到一個所有鄰接于它的頂點都被訪問過了的頂點當(dāng)遇到一個所有鄰接于它的頂點都被訪問過了的頂點U時，則回到已訪問頂點序列中最后一個擁有未被訪問時，則回到已訪問頂點序列中最后一個擁有未被訪問的相鄰頂點的頂點的相鄰頂點的頂點W， 再從再從W出發(fā)遞歸地按照深度優(yōu)先的方式周游，出發(fā)遞歸地按照深度優(yōu)先的

27、方式周游， 最后，當(dāng)任何已被訪問過的頂點都沒有未被訪問的相最后，當(dāng)任何已被訪問過的頂點都沒有未被訪問的相鄰頂點時，則周游結(jié)束。鄰頂點時，則周游結(jié)束。圖44/108深度優(yōu)先搜索是類似于樹的一種先序遍歷深度優(yōu)先搜索是類似于樹的一種先序遍歷v1v2v3v5v4v6v7v8圖可分為三部分圖可分為三部分:基結(jié)點基結(jié)點第一個鄰接結(jié)點第一個鄰接結(jié)點導(dǎo)出的子圖導(dǎo)出的子圖其它鄰接頂點導(dǎo)其它鄰接頂點導(dǎo)出的子圖出的子圖深度優(yōu)先搜索順序深度優(yōu)先搜索順序: v1v2v4v8v5v3v6v76.4.1 深度優(yōu)先搜索深度優(yōu)先搜索樹（深度優(yōu)先搜索樹（depth-first search tree）圖45/1086.4.1 深

28、度優(yōu)先搜索（續(xù)）深度優(yōu)先搜索的順序是深度優(yōu)先搜索的順序是a，b，c，f，d，e，g圖46/108bool DFSTraverse ( Graph G ，int v ) / visited0.n-1 初始均為初始均為 0 ；v 指示頂點在數(shù)組中的位置指示頂點在數(shù)組中的位置 ；visitedv = true； visit(v) ； /訪問此頂點訪問此頂點for ( w=FirstVex(G,v) ;w=0;w=NextVex(G, v, w) )if ( ! visitedw ) DFSTraverse (G , w) ；return true ；圖47/1086.4.1 深度優(yōu)先搜索（續(xù)） 深度

29、優(yōu)先搜索算法的時間復(fù)雜度深度優(yōu)先搜索算法的時間復(fù)雜度 DFS對每一條邊處理一次（無向圖的每條邊從對每一條邊處理一次（無向圖的每條邊從兩個方向處理），每個頂點訪問一次。兩個方向處理），每個頂點訪問一次。 采 用 鄰 接 表 表 示 時 ， 有 向 圖 總 代 價 為采 用 鄰 接 表 表 示 時 ， 有 向 圖 總 代 價 為(|V|+|E|)，無向圖為，無向圖為(|V|+2|E|) 。 采用相鄰矩陣表示時，處理所有的邊需要采用相鄰矩陣表示時，處理所有的邊需要(|V|2)的時間的時間 ，所以總代價為，所以總代價為(|V|+|V|2)= (|V|2)。圖48/1086.4.2 廣度優(yōu)先搜索 廣度優(yōu)

30、先搜索（廣度優(yōu)先搜索（breadth-first search，簡，簡稱稱BFS） 它的基本思想是訪問頂點它的基本思想是訪問頂點V0， 然后訪問然后訪問V0鄰接到的所有未被訪問過的頂點鄰接到的所有未被訪問過的頂點V01，V02，V0i， 再依次訪問再依次訪問V01，V02，V0i鄰接到的所有未鄰接到的所有未被訪問的頂點，被訪問的頂點， 如此進行下去，直到訪問遍所有的頂點。如此進行下去，直到訪問遍所有的頂點。圖49/108深度優(yōu)先搜索類似于樹的層次遍歷，深度優(yōu)先搜索類似于樹的層次遍歷，廣度優(yōu)先搜索順序廣度優(yōu)先搜索順序: v1v2v3v4v5v6v7v8v1v2v3v5v4v6v7v8只有父輩結(jié)點

31、被只有父輩結(jié)點被訪問后才會訪問訪問后才會訪問子孫結(jié)點！子孫結(jié)點！把圖人為的分層，把圖人為的分層，按層遍歷。按層遍歷。廣度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索樹（廣度優(yōu)先搜索樹（breadth-first search tree）圖50/108v1v2v3v5v4v6v7v8廣度優(yōu)先搜索順序廣度優(yōu)先搜索順序: v1v2v3v4v6v5v7v8v1v2v3v4v5v6v7v8廣度優(yōu)先搜索圖51/1086.4.2 廣度優(yōu)先搜索（續(xù)）廣度優(yōu)先搜索的順序是a，b，d，e，f，c，g圖52/1086.4.2 廣度優(yōu)先搜索（續(xù)）/廣度優(yōu)先搜索算法的實現(xiàn)廣度優(yōu)先搜索算法的實現(xiàn)void BFS(Graph& G,

32、int V) /初始化廣度優(yōu)先周游要用到的隊列初始化廣度優(yōu)先周游要用到的隊列 using std:queue; queue Q; /訪問頂點訪問頂點V，并標(biāo)記其標(biāo)志位，并標(biāo)記其標(biāo)志位， V入隊入隊 G.MarkV= VISITED; Visit(G, V); Q.push(V); while(!Q.empty() /如果隊列仍然有元素如果隊列仍然有元素圖53/1086.4.2 廣度優(yōu)先搜索（續(xù)） int V=Q.front(); /頂部元素頂部元素 Q.pop(); /出隊出隊 /將與該點相鄰的每一個未訪問結(jié)點都入隊將與該點相鄰的每一個未訪問結(jié)點都入隊for(Edge e=G.FirstEdg

33、e(V); G.IsEdge(e);e=G.NextEdge(e) if(G.MarkG.ToVertex(e)= UNVISITED)圖54/1086.4.2 廣度優(yōu)先搜索（續(xù)） G.MarkG.ToVertex(e)=VISITED; Visit(G, G.ToVertex(e); /入隊入隊 Q.push(G.ToVertex(e); 圖55/1086.4.2 廣度優(yōu)先搜索（續(xù)） 廣度優(yōu)先搜索算法的時間復(fù)雜度廣度優(yōu)先搜索算法的時間復(fù)雜度 與深度優(yōu)先搜索算法的時間復(fù)雜度相同與深度優(yōu)先搜索算法的時間復(fù)雜度相同圖56/108練習(xí)對于入圖所示的有向圖，試寫出：對于入圖所示的有向圖，試寫出：（1）

34、從頂點）從頂點出發(fā)進行深度優(yōu)先搜索所得出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；到的深度優(yōu)先生成樹；（2）從頂點）從頂點出發(fā)進行廣度優(yōu)先搜索所得出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；到的廣度優(yōu)先生成樹；12345圖57/1086.4.3 拓?fù)渑判?先決條件問題。先決條件問題。 拓?fù)渑判颍ㄍ負(fù)渑判颍╰opological sort） 將一個有向無環(huán)圖中所有頂點在不違反將一個有向無環(huán)圖中所有頂點在不違反先決條件關(guān)系先決條件關(guān)系的前提下排成線性序列的的前提下排成線性序列的過程稱為過程稱為拓?fù)渑判蛲負(fù)渑判驁D58/1086.4.3 拓?fù)渑判颍ɡm(xù)） 拓?fù)湫蛄型負(fù)湫蛄?對于有向?qū)τ谟邢驘o環(huán)圖無環(huán)圖G

35、=（V，E），），V里里頂頂點的線性序列稱作一個點的線性序列稱作一個拓?fù)湫蛄型負(fù)湫蛄?，如，如果該頂點序列滿足：果該頂點序列滿足： 若在有向無環(huán)圖若在有向無環(huán)圖G中從頂點中從頂點Vi到到Vj有一條路徑，有一條路徑，則在序列中頂點則在序列中頂點Vi必在頂點必在頂點Vj之前。之前。圖59/1086.4.3 拓?fù)渑判颍ɡm(xù)）課程編號課程編號課程名稱課程名稱先決條件先決條件C1C2C3C4C5程序語言基礎(chǔ)程序語言基礎(chǔ)離散數(shù)學(xué)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)微機原理微機原理編譯原理編譯原理C6操作系統(tǒng)操作系統(tǒng)C1C1 , C2C3C3 , C4表示課程之間優(yōu)先關(guān)系的有向圖表示課程之間優(yōu)先關(guān)系的有向圖C1C2C3C5

36、C4C6拓?fù)渑判蚩梢詾橥負(fù)渑判蚩梢詾?C1 C2 C3 C5 C4 C6C4 C1 C2 C3 C5 C6圖60/1086.4.3 拓?fù)渑判颍ɡm(xù)） 任何無環(huán)有向圖，其頂點都可以排在一任何無環(huán)有向圖，其頂點都可以排在一個拓?fù)湫蛄欣铮渫負(fù)渑判虻姆椒ㄊ牵簜€拓?fù)湫蛄欣?，其拓?fù)渑判虻姆椒ㄊ牵?（1）從圖中選擇一個入度為）從圖中選擇一個入度為0的頂點且輸?shù)捻旤c且輸出之。出之。 （2）從圖中刪掉此頂點及其所有的出邊。）從圖中刪掉此頂點及其所有的出邊。 （3）回到第（）回到第（1）步繼續(xù)執(zhí)行。）步繼續(xù)執(zhí)行。圖61/108例，例，v1v2v4v3v6v5拓?fù)渑判蛲負(fù)渑判騰1v6v4v3v2v5圖62/108v

37、1v2v4v3v6v5例，例，拓?fù)渑判蛲負(fù)渑判騰1v3v2存在環(huán)存在環(huán)圖63/1086.4.3 拓?fù)渑判颍ɡm(xù)）/隊列方式實現(xiàn)的拓?fù)渑判蜿犃蟹绞綄崿F(xiàn)的拓?fù)渑判?void TopsortbyQueue(Graph& G) for(int i=0;iG.VerticesNum();i+)G.Marki=UNVISITED; /初始化標(biāo)記數(shù)組初始化標(biāo)記數(shù)組 using std:queue; queue Q; /初始化隊列初始化隊列 for(i=0; iG.VerticesNum(); i+) if(G.Indegreei=0) Q.push(i); /圖中入度為圖中入度為0的頂點入隊的頂點入隊 whi

38、le(!Q.empty() /如果隊列中還有圖的頂點如果隊列中還有圖的頂點 圖64/1086.4.3 拓?fù)渑判颍ɡm(xù)） int V=Q.front(); /頂部元素頂部元素 Q.pop(); /一個頂點出隊一個頂點出隊 Visit(G, V); /訪問該頂點訪問該頂點 G.MarkV=VISITED; /邊邊e的終點的入度值減的終點的入度值減1 for(Edge e= G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e) G.IndegreeG.ToVertex(e)-; if(G.IndegreeG.ToVertex(e)=0) Q.push(G.ToVert

39、ex(e); /入度為入度為0的頂點入隊的頂點入隊 圖65/1086.4.3 拓?fù)渑判颍ɡm(xù)） for(i=0; iG.VerticesNum(); i+) if(G.Marki=UNVISITED) Print(“圖有環(huán)圖有環(huán)”); /圖有環(huán)圖有環(huán) break; 圖66/108蘭州蘭州太原太原北京北京濟南濟南徐州徐州鄭州鄭州西安西安旅客希望?？空驹缴僭胶?，則應(yīng)選擇旅客希望?？空驹缴僭胶茫瑒t應(yīng)選擇濟南濟南北京北京太原太原蘭州蘭州旅客考慮的是旅程越短越好，旅客考慮的是旅程越短越好，1120920720210540340640190濟南濟南徐州徐州鄭州鄭州西安西安蘭州蘭州6.5 最短路徑圖67/10

40、8通常在實際中，航運、鐵路、船行都具有有向性，故我通常在實際中，航運、鐵路、船行都具有有向性，故我們以帶權(quán)有向圖為例介紹最短路徑算法。們以帶權(quán)有向圖為例介紹最短路徑算法。帶權(quán)無向圖的最短路徑算法也通用。帶權(quán)無向圖的最短路徑算法也通用。 從單個源點到其余各頂點的最短路徑算法。從單個源點到其余各頂點的最短路徑算法。 每一對頂點之間的最短路徑算法。每一對頂點之間的最短路徑算法。帶權(quán)圖的最短路徑計算問題圖68/108尋找從單個源點到其余各頂點的最短路徑算法：尋找從單個源點到其余各頂點的最短路徑算法：思想思想: 貪心算法貪心算法(局部最優(yōu)局部最優(yōu))，按路徑長度遞增的次序產(chǎn)生最短路徑。，按路徑長度遞增的次

41、序產(chǎn)生最短路徑。貪心算法貪心算法: 利用局部最優(yōu)來計算全局最優(yōu)。利用局部最優(yōu)來計算全局最優(yōu)。利用已得到的頂點的最短路徑來計算其它頂點的最短路徑。利用已得到的頂點的最短路徑來計算其它頂點的最短路徑。例，例，v5v0v1v4v3601005v21030201050求從求從 v0 到其余各頂點的最短路徑。到其余各頂點的最短路徑。1. 初始初始，Di 的值為的值為 v0 到到 vi 的弧的權(quán)值的弧的權(quán)值Di 表示表示 v0 到到 vi 的最短路徑的長度的最短路徑的長度顯然，顯然，Di 中的最小值中的最小值 D2 便是便是 v0到到 v2 的最短路徑的長度，的最短路徑的長度，Path2=( v0 , v

42、2 )Pathi表示表示v0 到到 vi 的最短路徑的最短路徑DIjkstra算法圖69/108設(shè)下一條最短路徑的終點是設(shè)下一條最短路徑的終點是 vk ，則這條最短路徑或者是，則這條最短路徑或者是 ( v0 , vk ) 、或者是或者是 v0 經(jīng)過經(jīng)過 v2 或或 v4 到達(dá)到達(dá) vk 的路徑的路徑 ；2. 如何尋找下一條最短路徑？如何尋找下一條最短路徑？例，例，v5v0v1v4v3601005v21030201050設(shè)下一條最短路徑的終點是設(shè)下一條最短路徑的終點是 vj ，則，則這條最短路徑或者是這條最短路徑或者是 ( v0 , vj ) 、或、或者是者是 v0 經(jīng)過經(jīng)過 v2 到達(dá)到達(dá) v

43、j 的路徑的路徑 ；其中取其中取 Di(D2除外除外) 中的最小值得中的最小值得到到 v4，Path4=( v0 , v4 ) 。3. 如何尋找下一條最短路徑？如何尋找下一條最短路徑？取取 Di(D2、D4 除外除外) 中的最小值得到中的最小值得到 v3 ，Path3=( v0 , v4 , v3 ) 。DIjkstra算法應(yīng)用圖70/108例，例，v5v0v1v4v3601005v21030201050帶權(quán)鄰接矩陣帶權(quán)鄰接矩陣 10 30 1000 1 2 3 4 5 5 50 10 20 60 012345v21030100v0v2v2106030100v0v4v430v2 , v450

44、90v0v4v3v350v2 , v4 , v3 60v0v4v3v5v560v2 , v4 , v3 , v5 v1v1v2v3v4v5最短路徑最短路徑新頂點新頂點S頂點頂點路徑長度路徑長度每次修改都用每次修改都用的是最新加入的是最新加入集合集合 S 的頂點的頂點圖71/1086.5.1 單源最短路徑其中的其中的Dist類可以如下定義：類可以如下定義：Class Distint length; /與源與源s的距離的距離int pre; /前面的頂點前面的頂點;而而minVertex()函數(shù)可用最小堆（函數(shù)可用最小堆（Minheap）等方式實現(xiàn)。等方式實現(xiàn)。圖72/1086.5.1 單源最短路

45、徑/Dijkstra算法算法void Dijkstra(Graph& G,int s, Dist* &D) D=new DistG.VerticesNum(); /初始化初始化Mark數(shù)組、數(shù)組、D數(shù)組數(shù)組 /minVertex函數(shù)中會用到函數(shù)中會用到Mark數(shù)組的信息數(shù)組的信息for(int i=0;iG.VerticesNum();i+) G.Marki=UNVISITED; Di.length= INFINITY; Di.pre=s; Ds.length=0;圖73/1086.5.1 單源最短路徑 for(i=0;i(Dv.length +G.Weight(e) DG.ToVertex(

46、e).length=Dv.length +G.Weight(e); DG.ToVertex(e).pre=v; 圖75/108練習(xí)以下圖為例，按以下圖為例，按Dijkstra算法計算得到的從算法計算得到的從頂點頂點A到其他各個頂點的最短路徑和最短路到其他各個頂點的最短路徑和最短路徑長度。徑長度。A B C D E 10 18 5 5 2 2 2 圖76/1086.5.2 每對頂點間的最短路徑 Floyd算法算法 算法思想：算法思想： 假設(shè)用相鄰矩陣假設(shè)用相鄰矩陣adj表示圖表示圖 Floyd算法遞歸地產(chǎn)生一個矩陣序列算法遞歸地產(chǎn)生一個矩陣序列adj(0)，adj(1)， adj(k) ， ad

47、j(n) adj(k)i，j等于從頂點等于從頂點Vi到頂點到頂點Vj中間頂點序號不大中間頂點序號不大于于k的最短路徑長度的最短路徑長度 圖77/1086.5.2 每對頂點間的最短路徑 假設(shè)已求得矩陣假設(shè)已求得矩陣adj(k-1)，那么從頂點，那么從頂點Vi到頂點到頂點Vj中間頂點的中間頂點的序號不大于序號不大于k的最短路徑有兩種情況：的最短路徑有兩種情況： 一種是中間不經(jīng)過頂點一種是中間不經(jīng)過頂點Vk，那么就有，那么就有 adj(k)i，j=adj(k-1)i，j 另一種是中間經(jīng)過頂點另一種是中間經(jīng)過頂點Vk，那么，那么adj(k)i，j adj(k-1)i，j，且且adj(k)i，j= ad

48、j(k-1)i，k+ adj(k-1)k，j圖78/1086.5.2 每對頂點間的最短路徑(0)(1)041adj =path=01adj =path= (2)(3)301adj =path=0adj = 1path=圖79/1086.5.2 每對頂點間的最短路徑/Floyd算法算法void Floyd(Graph& G, Dist* &D) int i,j,v; /i,j,v作為計數(shù)器作為計數(shù)器 D=new Dist*G.VerticesNum(); for(i=0; ;iG.VerticesNum();i+) Di=new DistG.VerticesNum(); /初始化初始化D數(shù)組數(shù)組

49、for(i=0;iG.VerticesNum();i+)for(j=0;jG.VerticesNum();j+)圖80/1086.5.2 每對頂點間的最短路徑 if(i=j) Dij.length=0; Dij.pre=i; else Dij=INFINITY; Dij.pre=-1; for(v=0;v(Div.length+Dvj.lengthfor(v=0;vG.VerticesNum();v+) for(i=0;iG.VerticesNum();i+) for(j=0;j(Div.length +Dvj.length)Dij.length =Div.length +Dvj.length

50、; Dij.pre=Dvj.pre; 圖82/1086.5.2 每對頂點間的最短路徑 注：其中注：其中DistDist類型與類型與DijkstraDijkstra算法用到算法用到的的DistDist類型一致。類型一致。 因為因為FloydFloyd算法的時間復(fù)雜度主要在于三算法的時間復(fù)雜度主要在于三重重forfor循環(huán)，所以很明顯，其復(fù)雜度是循環(huán)，所以很明顯，其復(fù)雜度是O(nO(nn nn n).).圖83/108一個連通圖一個連通圖 G 的一個包含所有頂點的的一個包含所有頂點的極小連通子圖極小連通子圖 T 是是 (1) T 包含包含 G 的所有頂點的所有頂點 n 個個(2) T 為連通子圖為

51、連通子圖(3) T 包含的邊數(shù)最少包含的邊數(shù)最少ABCLHJ支撐樹支撐樹ABCLHJT 是一棵有是一棵有 n 個頂點，個頂點，n- -1 條邊的條邊的支撐樹支撐樹。支撐樹圖84/108性質(zhì)性質(zhì): 一個有一個有n個頂點的連通圖的支撐樹有且僅有個頂點的連通圖的支撐樹有且僅有n- -1條邊。條邊。1. 如果一棵如果一棵支撐支撐樹樹有有 n 個頂點和小于個頂點和小于 n- -1 條邊，則為條邊，則為非連通圖非連通圖。2. 如果一棵支撐樹有如果一棵支撐樹有 n 個頂點和多于個頂點和多于 n- -1 條邊，則一定有環(huán)。條邊，則一定有環(huán)。構(gòu)成一棵構(gòu)成一棵 n 頂點支撐樹需要頂點支撐樹需要 n- -1 條邊，

52、條邊，少于少于 n- -1 ，則必有邊斷開，不再連通。，則必有邊斷開，不再連通。構(gòu)成一棵構(gòu)成一棵 n 頂點支撐樹需要頂點支撐樹需要 n- -1 條邊，條邊，若再添加一條邊，必會使得與它關(guān)聯(lián)的那兩個頂點之間有了若再添加一條邊，必會使得與它關(guān)聯(lián)的那兩個頂點之間有了第二條路徑。第二條路徑。ABCLHJ支撐樹的性質(zhì)圖85/108性質(zhì)性質(zhì): 一個連通圖的支撐樹并不唯一一個連通圖的支撐樹并不唯一ABCLHJABCLHJABCLHJ生成樹生成樹ABCLHJ刪除環(huán)中的任一條邊刪除環(huán)中的任一條邊支撐樹的性質(zhì)圖86/108支撐樹的代價支撐樹的代價:為樹上各邊的權(quán)之總和。為樹上各邊的權(quán)之總和。如何求取如何求取最小支

53、撐樹最小支撐樹？代價最小的生成樹稱為代價最小的生成樹稱為最小支撐樹最小支撐樹。實際價值？實際價值？v1v2v3v5v4v61556536642v1v2v3v5v4v615342生成樹生成樹v1v2v3v5v4v653642最小支撐樹(生成樹)圖87/108最小支撐樹（生成樹） 普里姆算法（普里姆算法（Prim） 克魯斯卡爾算法（克魯斯卡爾算法（Kruskal）圖88/108思想：思想：重復(fù)執(zhí)行重復(fù)執(zhí)行:N = ( V , E ) 是具有是具有 n 個頂點的連通圖，設(shè)個頂點的連通圖，設(shè) U 是最小生成是最小生成樹中頂點的集合，設(shè)樹中頂點的集合，設(shè) TE 是最小生成樹中邊的集合；是最小生成樹中邊的

54、集合； 初始，初始，U = u1 ，TE = ，在所有在所有 uU，vV- -U 的邊的邊 ( u , v ) 中尋找代價中尋找代價最小最小的的邊邊( u , v ) ，并納入集合，并納入集合 TE 中；中；同時將同時將 v 納入集合納入集合 U 中；中；直至直至 U = V 為止。為止。集合集合 TE 中必有中必有 n- -1 條邊。條邊。 PrimPrim算法算法圖89/108v1v2v3v5v4v61556536642例，例，v1v31v25v53v64v42初始初始: U = v1 ，V- -U = v2 , v3 , v4 , v5 , v6 TE = U = v1 , v3 ，V-

55、 -U = v2 , v4 , v5 , v6 U = v1 , v3 , v6 ，V- -U = v2 , v4 , v5 重點重點: 邊一定存在于邊一定存在于 U 與與 V- -U 之間。之間。U = v1 , v3 , v4 , v6 ，V- -U = v2 , v5 U = v1 , v2 , v3 , v4 , v6 ，V- -U = v5 U = v1 , v2 , v3 , v4 , v5 , v6 ，V- -U = PrimPrim算法算法圖90/108Kruskal圖91/108v1v2v3v5v4v61556536642v1v2v3v5v4v615342初始初始 TE =

56、當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v1 , v3 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v4 , v6 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v2 , v5 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v3 , v6 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v1 , v4 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v3 , v4 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v2 , v3 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v1 , v2 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v3 , v5 )當(dāng)前權(quán)值最小邊當(dāng)前權(quán)值最小邊 ( v5 , v6 )Kruskal算法圖92/108算法時間復(fù)雜度算法時間復(fù)雜度:O(n2)與邊的個

57、數(shù)無關(guān)；與邊的個數(shù)無關(guān)；適合于求邊稠密的網(wǎng)的最小生成樹。適合于求邊稠密的網(wǎng)的最小生成樹。Kruskal 算法算法算法時間復(fù)雜度算法時間復(fù)雜度: O( e log e ) e為網(wǎng)的邊的數(shù)目為網(wǎng)的邊的數(shù)目.適合于求邊稀疏的網(wǎng)的最小生成樹。適合于求邊稀疏的網(wǎng)的最小生成樹。最小支撐樹算法分析Prim 算法算法圖93/108有向無環(huán)圖也可作為描述工程管理的有效工具。有向無環(huán)圖也可作為描述工程管理的有效工具。開始開始蓋房蓋房買材料買材料招工人招工人材料材料齊備齊備人員人員齊備齊備挖土挖土填地基填地基地基地基建好建好壘墻壘墻墻壘墻壘好好地鋪地鋪好好鋪地鋪地房屋房屋建好建好刷墻刷墻擦地擦地頂點表示頂點表示事件

58、事件(狀態(tài)狀態(tài))弧表示弧表示活動活動每個事件表示在它之前的活動已經(jīng)每個事件表示在它之前的活動已經(jīng)完成完成，在它之后的活動可以，在它之后的活動可以開始開始312611537為弧加為弧加權(quán)權(quán)，通常表示活動所需要的時間，通常表示活動所需要的時間這種這種邊邊表示活動的表示活動的帶權(quán)的無環(huán)有向圖帶權(quán)的無環(huán)有向圖稱為稱為 AOE 網(wǎng)網(wǎng)關(guān)鍵路徑圖94/108開始開始蓋房蓋房買材料買材料招工人招工人材料材料齊備齊備人員人員齊備齊備挖土挖土填地基填地基地基地基建好建好壘墻壘墻墻壘墻壘好好地鋪地鋪好好鋪地鋪地房屋房屋建好建好刷墻刷墻擦地擦地312611537通常，通常，AOE 網(wǎng)中只有一個入度為網(wǎng)中只有一個入度為

59、 0 的頂點的頂點(源點源點)，一個出度為，一個出度為 0 的頂點的頂點(匯點匯點)。對于一個對于一個 AOE 網(wǎng)，最關(guān)心的兩個問題網(wǎng)，最關(guān)心的兩個問題:1. 完成整項工程至少需要多少時間？完成整項工程至少需要多少時間？2. 哪些活動是影響工程進度的關(guān)鍵？哪些活動是影響工程進度的關(guān)鍵？完成工程的最短時間是從源點到匯點的最長路徑的長度，這里的完成工程的最短時間是從源點到匯點的最長路徑的長度，這里的最長路徑叫做最長路徑叫做關(guān)鍵路徑關(guān)鍵路徑。圖95/108v1v2v3v4v5v6v7a8 = 3a1 = 6a2 = 3a3 = 1a4 = 1a5 = 9a6 = 6a7 = 2ve(vi) 事件事件

60、 vi 的最早發(fā)生時間的最早發(fā)生時間vl (vi) 事件事件 vi 的最遲發(fā)生時間的最遲發(fā)生時間e(ai) 活動活動 ai 的最早開始時間的最早開始時間l (ai) 活動活動 ai 的最遲開始時間的最遲開始時間l (ai) - - e(ai) 意味著完成活動意味著完成活動 ai 的時間余量的時間余量l (ai) = = e(ai) 的活動叫做的活動叫做關(guān)鍵活動關(guān)鍵活動；顯然，關(guān)鍵路徑上的活動都是關(guān)鍵活動。顯然，關(guān)鍵路徑上的活動都是關(guān)鍵活動。關(guān)鍵活動的工效直接影響到整個工期。關(guān)鍵活動的工效直接影響到整個工期。例例 a1 a3 a5 a7 ve(v1) = 0vl (v1) = 0e(a1) =