離散數(shù)學(xué) 圖.ppt

1、第7章 圖,學(xué)習(xí)要點(diǎn): 理解圖的定義和與圖相關(guān)的術(shù)語。 理解圖是一個(gè)表示復(fù)雜非線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 掌握圖的鄰接矩陣表示及其實(shí)現(xiàn)方法。 掌握圖的鄰接表表示及其實(shí)現(xiàn)方法。 了解圖的緊縮鄰接表表示方法。 掌握圖的廣度優(yōu)先搜索方法。 掌握圖的深度優(yōu)先搜索方法。 掌握單源最短路徑問題的Dijkstra算法。 掌握有負(fù)權(quán)邊的單源最短路徑問題的Bellman-Ford算法 掌握所有頂點(diǎn)對之間最短路徑問題的Floyd算法。 掌握構(gòu)造最小支撐樹的Prim算法。 掌握構(gòu)造最小支撐樹的Kruskal算法。 理解圖的最大匹配問題的增廣路徑算法。,2020/8/27,1,第7章 圖,7.1 圖的定義和術(shù)語 圖(Gra

2、ph)圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E) 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?有向圖圖G中的每條邊都是有方向 有向圖G是由兩個(gè)集合V(G)和E(G)組成的 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是有向邊（也稱弧）的有限集合，弧是頂點(diǎn)的有序?qū)?，記為，v,w是頂點(diǎn)，v為弧尾，w為弧頭 無向圖圖G中每條邊都是沒有方向 無向圖G是由兩個(gè)集合V(G)和E(G)組成的 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記?（v,w）或（w,v)，并且（v,w)=(w,v),2020/8/27,2,20

3、20/8/27,3,圖G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,圖G2中：V(G2)=1,2,3,4,5,6,7 E(G2)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),有向完備圖n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1) 無向完備圖n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2 關(guān)聯(lián) P225 權(quán)與圖的邊或弧相關(guān)的數(shù)叫 網(wǎng)帶權(quán)的圖叫 子圖如果圖G(V,E)和圖G(V,E),滿足： VV EE 則稱G為G的子圖 頂點(diǎn)的度 無向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù) 有向圖中，頂點(diǎn)的度分成入度與出度,假設(shè)一頂點(diǎn)v,

4、入度：以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目，記為ID（v） 出度：以頂點(diǎn)v為起點(diǎn)的邊的數(shù)目，記為OD（v） 路徑路徑是頂點(diǎn)的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E 或 E,(1jn),2020/8/27,4,路徑長度沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和 回路第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫 簡單路徑序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫 簡單回路除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫 連通從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說V和W是連通的 連通圖圖中任意兩個(gè)頂點(diǎn)都是連通的叫 連通分量非連通圖的每一個(gè)連通部分叫 強(qiáng)連通圖有向圖中，如果對每一對Vi,VjV, ViVj,從Vi到V

5、j 和從Vj到 Vi都存在路徑，則稱G是,2020/8/27,5,2020/8/27,6,2020/8/27,7,路徑：1，2，3，5，6，3 路徑長度：5 簡單路徑：1，2，3，5 回路：1，2，3，5，6，3，1 簡單回路：3，5，6，3,路徑：1，2，5，7，6，5，2，3 路徑長度：7 簡單路徑：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 簡單回路：1，2，3，1,2020/8/27,8,連通圖,強(qiáng)連通圖,非連通圖 連通分量,7.2 圖的表示法 鄰接矩陣表示頂點(diǎn)間相聯(lián)關(guān)系的矩陣 定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣,2020/8

6、/27,9,特點(diǎn)： 無向圖的鄰接矩陣對稱，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無向圖需存儲(chǔ)空間為n(n+1)/2 有向圖鄰接矩陣不一定對稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n 無向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和 有向圖中， 頂點(diǎn)Vi的出度是A中第i行元素之和 頂點(diǎn)Vi的入度是A中第i列元素之和 網(wǎng)絡(luò)的鄰接矩陣可定義為：,2020/8/27,10,2020/8/27,11,2020/8/27,12,基本思想：對圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息。每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。 第i個(gè)單鏈表表示依附于頂點(diǎn)Vi的邊(對有向圖是以頂點(diǎn)Vi為頭或尾的弧)。,7.2.

7、2 鄰接鏈表法,鄰接表 實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表存放頂點(diǎn)Vi的所有鄰接頂點(diǎn)。,2020/8/27,13,特點(diǎn) 無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù) 有向圖中 頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù) 頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù) 逆鄰接表：有向圖中對每個(gè)結(jié)點(diǎn)建立以Vi為終點(diǎn)的邊的單鏈表,2020/8/27,14,求解麻煩！,例,習(xí)題1、 有如圖所示的有向圖，畫出該圖的： (1) 鄰接矩陣； (2) 鄰接表。,2020/8/27,15,7.2.3 十字鏈表法,十字鏈表(Orthogonal List)是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是將有向圖

8、的正鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。 在這種結(jié)構(gòu)中，每條弧的弧頭結(jié)點(diǎn)和弧尾結(jié)點(diǎn)都存放在鏈表中，并將弧結(jié)點(diǎn)分別組織到以弧尾結(jié)點(diǎn)為頭(頂點(diǎn))結(jié)點(diǎn)和以弧頭結(jié)點(diǎn)為頭(頂點(diǎn))結(jié)點(diǎn)的鏈表中。,2020/8/27,16,2020/8/27,17, data域：存儲(chǔ)和頂點(diǎn)相關(guān)的信息； 指針域firstin：指向以該頂點(diǎn)為弧頭的第一條弧所對應(yīng)的弧結(jié)點(diǎn)； 指針域firstout：指向以該頂點(diǎn)為弧尾的第一條弧所對應(yīng)的弧結(jié)點(diǎn)； 尾域tailvex：指示弧尾頂點(diǎn)在圖中的位置； 頭域headvex：指示弧頭頂點(diǎn)在圖中的位置； 指針域hlink：指向弧頭相同的下一條??； 指針域tlink：指向弧尾相同的下一條弧；

9、Info域：指向該弧的相關(guān)信息；,2020/8/27,18,2020/8/27,19,7.2.4 鄰接多重表,鄰接多重表(Adjacency Multilist)是無向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 鄰接表是無向圖的一種有效的存儲(chǔ)結(jié)構(gòu)，在無向圖的鄰接表中，一條邊(v,w)的兩個(gè)表結(jié)點(diǎn)分別初選在以v和w為頭結(jié)點(diǎn)的鏈表中，很容易求得頂點(diǎn)和邊的信息，但在涉及到邊的操作會(huì)帶來不便。 鄰接多重表的結(jié)構(gòu)和十字鏈表類似，每條邊用一個(gè)結(jié)點(diǎn)表示；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)與鄰接表中的完全相同，而表結(jié)點(diǎn)包括六個(gè)域如圖7-14所示。,2020/8/27,21, Data域：存儲(chǔ)和頂點(diǎn)相關(guān)的信息； 指針域firstedge

10、：指向依附于該頂點(diǎn)的第一條邊所對應(yīng)的表結(jié)點(diǎn)； 標(biāo)志域mark：用以標(biāo)識(shí)該條邊是否被訪問過； ivex和jvex域：分別保存該邊所依附的兩個(gè)頂點(diǎn)在圖中的位置； info域：保存該邊的相關(guān)信息； 指針域ilink：指向下一條依附于頂點(diǎn)ivex的邊； 指針域jlink：指向下一條依附于頂點(diǎn)jvex的邊；,鄰接多重表與鄰接表的區(qū)別： 后者的同一條邊用兩個(gè)表結(jié)點(diǎn)表示，而前者只用一個(gè)表結(jié)點(diǎn)表示；除標(biāo)志域外，鄰接多重表與鄰接表表達(dá)的信息是相同的，因此，操作的實(shí)現(xiàn)也基本相似。,7.3 圖的遍歷 深度優(yōu)先遍歷(DFS) 方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)；然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷

11、圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止（問題：什么時(shí)候會(huì)出現(xiàn)這種情況？）,2020/8/27,24,類似于：樹的前序遍歷！,2020/8/27,25,深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7,2020/8/27,26,深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7,深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7,2020/8/27,27,深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5,2020/8/27,28,深度遍歷：V1,V3 ,V7

12、 ,V6 ,V2 ,V5 ,V8 ,V4,2020/8/27,29,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,2020/8/27,30,1、已知一個(gè)圖如下所示, 則從頂點(diǎn)a 出發(fā)按深度優(yōu)先搜索則可以得到的一種頂點(diǎn)序列為_,(A) a, b, e, d, f ,c (B) a, c, f, e, b, d (C) a, e, b, c, f, d (D) a, e, d, f, b,c,2020/8/27,31,2、如下圖所示的帶權(quán)有向圖G,試回答以下問題:,給出從結(jié)點(diǎn)v1出發(fā)按深度優(yōu)先搜索遍歷G所得的結(jié)點(diǎn)序列,并給出按廣度優(yōu)先搜索遍歷G所得的結(jié)點(diǎn)序列.,2020/8

13、/27,32,7.3 圖的遍歷 廣度優(yōu)先搜索(BFS) 方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接頂點(diǎn)；然后分別從這些鄰接頂點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,類似于：樹的層次遍歷！,7.4生成樹 生成樹 定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫 說明： 一個(gè)圖可以有許多棵不同的生成樹 所有生成樹具有以下共同特點(diǎn)： 生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同

14、生成樹是圖的極小連通子圖 一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊 生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的 在生成樹中再加一條邊必然形成回路 含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹,2020/8/27,33,在對無向連通圖進(jìn)行遍歷時(shí)，遍歷所得到的連通分量包含了圖中全部頂點(diǎn)和n1條邊，它們構(gòu)成了連通圖的一棵生成樹。,由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；,由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。,對于非連通圖，則需要進(jìn)行多次遍歷過程，每次從一個(gè)新的頂點(diǎn)出發(fā)，并且每次得到的頂點(diǎn)訪問序列是各個(gè)連通分量中的頂點(diǎn)集。,2020/8/27,35,35,最小生成樹 問題提出,2020/8/27

15、,36,要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)， 頂點(diǎn)表示城市 權(quán)城市間建立通信線路所需花費(fèi)代價(jià) 希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立 該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小最小代價(jià)生成樹,問題分析,n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路 n個(gè)城市間建立通信網(wǎng)，只需n-1條線路 問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把 所有城市（頂點(diǎn)）均連起來，且總耗費(fèi) （各邊權(quán)值之和）最小,最小生成樹性質(zhì) 用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這2個(gè)算法做貪心選擇的方式不同，它們都

16、利用了下面的最小生成樹性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。,2020/8/27,37,構(gòu)造最小生成樹方法 方法一：Prim算法 算法思想：設(shè)G=(V,E)是連通網(wǎng)，T是N上最小生成樹中邊的集合 初始令U=u0,(u0V), T= 在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0) 將(u0,v0)并入集合T，同時(shí)v0并入U(xiǎn) 重復(fù)上述操作直至U=V為止，則T=(V, T)為N的最小生成樹

17、,2020/8/27,38,2020/8/27,39,1,方法二：Kruskal算法 算法思想：設(shè)G=(V,E)，令最小生成樹 初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,)，每個(gè)頂點(diǎn)自成一個(gè)連通分量 在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊 依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止,2020/8/27,40,2020/8/27,41,2020/8/27,42,算法描述：,Prim算法與Kruskal算法的比較 從算法的時(shí)間復(fù)雜性看: 當(dāng)e= (n2)時(shí)，Kruskal算法比Prim算法差， 但當(dāng)e

18、= o(n2)時(shí)，Kruskal算法卻比Prim算法好得多。,算法分析： 設(shè)輸入的連通賦權(quán)圖有e條邊，則將這些邊依其權(quán)值組成優(yōu)先隊(duì)列需要O(e)時(shí)間；while循環(huán)中，DeleteMin運(yùn)算需要O(loge)時(shí)間，因此關(guān)于優(yōu)先隊(duì)列所作運(yùn)算的時(shí)間為O(eloge)。 實(shí)現(xiàn)UnionFind所需的時(shí)間為O(eloge)。 Kruskal算法所需的計(jì)算時(shí)間是O(eloge)。,7.6 有向無環(huán)圖及其應(yīng)用,有向無環(huán)圖：是圖中沒有回路(環(huán))的有向圖。是一類具有代表性的圖，主要用于研究工程項(xiàng)目的工序問題、工程時(shí)間進(jìn)度問題等。 一個(gè)工程都可分為若干個(gè)稱為活動(dòng)的子工程(或工序)，各個(gè)子工程受到一定的條件約束：

19、某個(gè)子工程必須開始于另一個(gè)子工程完成之后；整個(gè)工程有一個(gè)開始點(diǎn)(起點(diǎn))和一個(gè)終點(diǎn)。人們關(guān)心： 工程能否順利完成?影響工程的關(guān)鍵活動(dòng)是什么? 估算整個(gè)工程完成所必須的最短時(shí)間是多少?,對工程的活動(dòng)加以抽象：圖中頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex Network ，AOV網(wǎng)) 。,7.6.1 拓?fù)渑判?問題提出：學(xué)生選修課程問題 頂點(diǎn)表示課程 有向弧表示先決條件，若課程i是課程j的先決條件，則圖中有弧 學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)拓?fù)渑判?2020/8/27,45,拓?fù)渑判虬袮OV網(wǎng)絡(luò)中各

20、頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過程叫 檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校艟W(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán) 拓?fù)渑判虻姆椒?在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之 從圖中刪除該頂點(diǎn)和所有以它為尾的弧 重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止,2020/8/27,46,2020/8/27,47,2020/8/27,48,拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一

21、個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?2020/8/27,49,2020/8/27,50,2020/8/27,51,2020/8/27,52,2020/8/27,53,2020/8/27,54,7.6.2 關(guān)鍵路徑,1關(guān)鍵路徑的定義,2關(guān)鍵路徑的基本術(shù)語,3關(guān)鍵路徑的算法,2020/8/27,55,1關(guān)鍵路徑的定義,用頂點(diǎn)表示事件，用弧表示活動(dòng)，用權(quán)值表示活動(dòng)所需要的時(shí)間，這種構(gòu)造的有向無環(huán)圖稱為邊表示活動(dòng)的網(wǎng)，簡稱AOE網(wǎng)。,在AOE網(wǎng)中存在唯一的、入度為0的頂點(diǎn)，稱為源點(diǎn)。,存在唯一的、出度為0的頂點(diǎn)，稱為匯點(diǎn)。,從源點(diǎn)到匯點(diǎn)的最長路徑的長度即為完成整個(gè)工程任務(wù)所需的時(shí)間，該長度最長的路徑稱為關(guān)

22、鍵路徑，關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。,2020/8/27,56,與AOE有關(guān)的研究問題 完成整個(gè)工程至少需要多少時(shí)間? 哪些活動(dòng)是影響工程進(jìn)度(費(fèi)用)的關(guān)鍵?,2020/8/27,57,工程完成最短時(shí)間：從起點(diǎn)到終點(diǎn)的最長路徑長度(路徑上各活動(dòng)持續(xù)時(shí)間之和) 。長度最長的路徑稱為關(guān)鍵路徑，關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)是影響整個(gè)工程的關(guān)鍵。 設(shè)v0是起點(diǎn)，從v0到vi的最長路徑長度稱為事件vi的最早發(fā)生時(shí)間，即是以vi為尾的所有活動(dòng)的最早發(fā)生時(shí)間。,2020/8/27,58,2020/8/27,59,2關(guān)鍵路徑的基本術(shù)語, 事件Vi的最早發(fā)生時(shí)間Ve(i)：從源點(diǎn)V0到頂點(diǎn)Vi的最長

23、路徑長度。, 事件Vi的最晚發(fā)生時(shí)間Vl(i)：在保證匯點(diǎn)按其最早發(fā)生時(shí)間發(fā)生的前提下，事件Vi的最晚發(fā)生時(shí)間。, 活動(dòng)ai的最早開始時(shí)間e(i)：如果活動(dòng)ai對應(yīng)的弧為，則e(i)為從源點(diǎn)到頂點(diǎn)Vj的最長路徑的長度，即e(i)Ve(j)。, 活動(dòng)ai的最晚開始時(shí)間l(i)：如果活動(dòng)ai對應(yīng)的弧為，則l(i)為在保證事件Vk的最晚發(fā)生時(shí)間vl(k)的前提下（或者在保證不推遲整個(gè)工期的前提下），活動(dòng)ai的最晚開始時(shí)間，故有l(wèi)(i)Vl(k)dut()。, 活動(dòng)ai的松弛時(shí)間（時(shí)間余量）：活動(dòng)ai的最晚開始時(shí)間與最早開始時(shí)間之差。, 關(guān)鍵活動(dòng)：松弛時(shí)間（時(shí)間余量）為0的活動(dòng)。, 算法思想 利用拓?fù)?/p>

24、排序求出AOE網(wǎng)的一個(gè)拓?fù)湫蛄校?從拓?fù)渑判虻男蛄械牡谝粋€(gè)頂點(diǎn)(源點(diǎn))開始，按拓?fù)漤樞蛞来斡?jì)算每個(gè)事件的最早發(fā)生時(shí)間ve(i) ； 從拓?fù)渑判虻男蛄械淖詈笠粋€(gè)頂點(diǎn)(匯點(diǎn))開始，按逆拓?fù)漤樞蛞来斡?jì)算每個(gè)事件的最晚發(fā)生時(shí)間vl(i) ；,2020/8/27,60,對于圖7-24的AOE網(wǎng)，處理過程如下： 拓?fù)渑判虻男蛄惺牵?(v0, v1, v2, v3 , v4, v5 , v6 , v7 , v8) 根據(jù)計(jì)算ve(i)的公式(7-2)和計(jì)算vl(i)的公式(7-3) ，計(jì)算各個(gè)事件的ve(i)和vl(i)值，如表7-2所示。 根據(jù)關(guān)鍵路徑的定義，知該AOE網(wǎng)的關(guān)鍵路徑是： (v0, v2, v

25、4, v7 , v8) 和(v0, v2, v5 , v7 , v8) 。 關(guān)鍵路徑活動(dòng)是：， 。,2020/8/27,61,2020/8/27,62,表7-2 圖7-24的ve(i)和vl(i)的值,7.7 最短路徑,若用帶權(quán)圖表示交通網(wǎng)，圖中頂點(diǎn)表示地點(diǎn)，邊代表兩地之間有直接道路，邊上的權(quán)值表示路程(或所花費(fèi)用或時(shí)間) 。從一個(gè)地方到另一個(gè)地方的路徑長度表示該路徑上各邊的權(quán)值之和。問題： 兩地之間是否有通路? 在有多條通路的情況下，哪條最短?,考慮到交通網(wǎng)的有向性，直接討論的是帶權(quán)有向圖的最短路徑問題，但解決問題的算法也適用于無向圖。 將一個(gè)路徑的起始頂點(diǎn)稱為源點(diǎn)，最后一個(gè)頂點(diǎn)稱為終點(diǎn)。,

26、2020/8/27,64,7.7.1 單源點(diǎn)最短路徑,對于給定的有向圖G=(V，E)及單個(gè)源點(diǎn)Vs，求Vs到G的其余各頂點(diǎn)的最短路徑。 針對單源點(diǎn)的最短路徑問題，Dijkstra提出了一種按路徑長度遞增次序產(chǎn)生最短路徑的算法，即迪杰斯特拉(Dijkstra)算法。,1 基本思想 從圖的給定源點(diǎn)到其它各個(gè)頂點(diǎn)之間客觀上應(yīng)存在一條最短路徑，在這組最短路徑中，按其長度的遞增次序，依次求出到不同頂點(diǎn)的最短路徑和路徑長度。 即按長度遞增的次序生成各頂點(diǎn)的最短路徑，即先求出長度最小的一條最短路徑，然后求出長度第二小的最短路徑，依此類推，直到求出長度最長的最短路徑。,2020/8/27,66,2 算法思想說

27、明 設(shè)給定源點(diǎn)為Vs，S為已求得最短路徑的終點(diǎn)集，開始時(shí)令S=Vs 。當(dāng)求得第一條最短路徑(Vs ，Vi)后，S為Vs，Vi 。根據(jù)以下結(jié)論可求下一條最短路徑。 設(shè)下一條最短路徑終點(diǎn)為Vj ，則Vj只有： 源點(diǎn)到終點(diǎn)有直接的??； 從Vs 出發(fā)到Vj 的這條最短路徑所經(jīng)過的所有中間頂點(diǎn)必定在S中。即只有這條最短路徑的最后一條弧才是從S內(nèi)某個(gè)頂點(diǎn)連接到S外的頂點(diǎn)Vj 。,若定義一個(gè)數(shù)組distn，其每個(gè)disti分量保存從Vs 出發(fā)中間只經(jīng)過集合S中的頂點(diǎn)而到達(dá)Vi的所有路徑中長度最小的路徑長度值，則下一條最短路徑的終點(diǎn)Vj必定是不在S中且值最小的頂點(diǎn)，即： disti=Min distk| Vk

28、V-S 利用上述公式就可以依次找出下一條最短路徑。,3 算法步驟 令S=Vs ，用帶權(quán)的鄰接矩陣表示有向圖，對圖中每個(gè)頂點(diǎn)Vi按以下原則置初值：,2020/8/27,69, 選擇一個(gè)頂點(diǎn)Vj ，使得： distj=Min distk| VkV-S Vj就是求得的下一條最短路徑終點(diǎn)，將Vj 并入到S中，即S=SVj 。 對V-S中的每個(gè)頂點(diǎn)Vk ，修改distk，方法是： 若distj+Wjkdistk，則修改為： distk=distj+Wjk (VkV-S ) 重復(fù)，直到S=V為止。,表7-3 求最短路徑時(shí)數(shù)組dist和pre的各分量的變化情況,7.7.2 每一對頂點(diǎn)間的最短路徑,用Dijk

29、stra算法也可以求得有向圖G=(V，E)中每一對頂點(diǎn)間的最短路徑。方法是：每次以一個(gè)不同的頂點(diǎn)為源點(diǎn)重復(fù)Dijkstra算法便可求得每一對頂點(diǎn)間的最短路徑，時(shí)間復(fù)雜度是O(n3) 。 弗羅伊德(Floyd)提出了另一個(gè)算法，其時(shí)間復(fù)雜度仍是O(n3) ， 但算法形式更為簡明，步驟更為簡單，數(shù)據(jù)結(jié)構(gòu)仍然是基于圖的鄰接矩陣。,1 算法思想 設(shè)頂點(diǎn)集S(初值為空)，用數(shù)組A的每個(gè)元素Aij保存從Vi只經(jīng)過S中的頂點(diǎn)到達(dá)Vj的最短路徑長度，其思想是： 初始時(shí)令S= ， Aij的賦初值方式是：,2020/8/27,75, 將圖中一個(gè)頂點(diǎn)Vk 加入到S中，修改Aij的值，修改方法是： Aij=MinAij , (Aik+Akj) 原因： 從Vj只經(jīng)過S中的頂點(diǎn)(Vk)到達(dá)Vj的路徑長度可能比原來不經(jīng)過Vk的路徑更短。 重復(fù)，直到G的所有頂點(diǎn)都加入到S中為止。,表7-4給出了利用Floyd算法求圖7-26的帶權(quán)有向圖的任意一對頂點(diǎn)間最短路徑的過程。,根據(jù)上述過程中Pathij數(shù)組，得出： V0到V1 ：最短路徑是 0, 1 ，路徑長度是2 ； V0到V2 ：