數(shù)據(jù)結(jié)構(gòu)第三講.ppt

1、1,第三講 圖,2,本章出題特點(diǎn),在歷年統(tǒng)考里,大多以客觀題不勞形式出現(xiàn),具體如下,3,知識(shí)點(diǎn)歸納,了解,掌握,掌握,掌握、應(yīng)用,基本概念,4,一、圖的概念和相關(guān)術(shù)語(yǔ),圖的定義 圖(Graph)G由兩個(gè)集合V(Vertex)和E(Edge)組成,記為G=(V,E),其中V是頂點(diǎn)的有限集合,記為V(G),E是連接V中兩個(gè)不同頂點(diǎn)(頂點(diǎn)對(duì))的邊的有限集合,記為E(G)。 頂點(diǎn)集合為空的圖稱為空?qǐng)D。 E(G)為空時(shí),圖中只有頂點(diǎn)而沒(méi)有邊,5,圖的基本術(shù)語(yǔ) 1. 端點(diǎn)和鄰接點(diǎn) 在一個(gè)無(wú)向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個(gè)端點(diǎn),并稱它們互為鄰接點(diǎn)。 在一個(gè)有向圖中,若存在一條邊

2、,則稱此邊是頂點(diǎn)vi的一條出邊,同時(shí)也是頂點(diǎn)vj的一條入邊；稱vi和vj分別為此邊的起始端點(diǎn)(簡(jiǎn)稱為起點(diǎn))和終止端點(diǎn)(簡(jiǎn)稱終點(diǎn))；稱vi和vj互為鄰接點(diǎn),6,2. 路徑和路徑長(zhǎng)度 在一個(gè)圖G=(V,E)中,從頂點(diǎn)vi到頂點(diǎn)vj的一條路徑是一個(gè)頂點(diǎn)序列(vi,vi1,vi2,vim,vj),若此圖G是無(wú)向圖,則邊(vi,vi1),(vi1,vi2),(vim-1,vim),(vim,vj)屬于E(G)；若此圖是有向圖,則,屬于E(G)。 路徑長(zhǎng)度是指一條路徑上經(jīng)過(guò)的邊的數(shù)目。若一條路徑上除開(kāi)始點(diǎn)和結(jié)束點(diǎn)可以相同外,其余頂點(diǎn)均不相同,則稱此路徑為簡(jiǎn)單路徑。例如,有圖中,(v0,v2,v1)就是一條

3、簡(jiǎn)單路徑,其長(zhǎng)度為2,2,7,3. 連通、連通圖和連通分量 在無(wú)向圖G中,若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱vi和vj是連通的。 若圖G中任意兩個(gè)頂點(diǎn)都連通,則稱G為連通圖,否則稱為非連通圖。 無(wú)向圖G中的極大連通子圖稱為G的連通分量。顯然,任何連通圖的連通分量只有一個(gè),即本身,而非連通圖有多個(gè)連通分量,1,0,2,3,1,0,2,b,a,3,極大”的含義：指的是對(duì)子圖再增加圖G中的其它頂點(diǎn)，子圖就不再連通,8,4. 頂點(diǎn)的度、入度和出度 在無(wú)向圖中,頂點(diǎn)所具有的邊的數(shù)目稱為該頂點(diǎn)的度。 在有向圖中,以頂點(diǎn)vi為終點(diǎn)的入邊的數(shù)目,稱為該頂點(diǎn)的入度。以頂點(diǎn)vi為始點(diǎn)的出邊的數(shù)目,稱為該頂點(diǎn)的出度

4、。一個(gè)頂點(diǎn)的入度與出度的和為該頂點(diǎn)的度。 若一個(gè)圖中有n個(gè)頂點(diǎn)和e條邊,每個(gè)頂點(diǎn)的度為di(1in),則有,9,5. 完全圖 若無(wú)向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著一條邊,有向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著方向相反的兩條邊,則稱此圖為完全圖。 顯然,完全無(wú)向圖包含有n(n-1)/2條邊,完全有向圖包含有n(n-1)條邊。 例如,圖(a)所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全無(wú)向圖,共有6條邊。圖(b)所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全有向圖,共有12條邊,b,10,6. 子圖 設(shè)有兩個(gè)圖G=(V,E)和G=(V,E),若V是V的子集,即VV,且E是E的子集,即EE,則稱G是G的子圖。例如圖(b)是圖(a)的

5、子圖,而圖(c)不是圖(b)的子圖,11,7. 回路或環(huán) 若一條路徑上的開(kāi)始點(diǎn)與結(jié)束點(diǎn)為同一個(gè)頂點(diǎn),則此路徑被稱為回路或環(huán)。開(kāi)始點(diǎn)與結(jié)束點(diǎn)相同的簡(jiǎn)單路徑被稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。 例如,右圖中,(v0,v2,v1,v0)就是一條簡(jiǎn)單回路,其長(zhǎng)度為3,1,0,2,3,12,8. 強(qiáng)連通圖和強(qiáng)連通分量 在有向圖G中,若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱從vi到vj是連通的。 若圖G中的任意兩個(gè)頂點(diǎn)vi和vj都連通,即從vi到vj和從vj到vi都存在路徑,則稱圖G是強(qiáng)連通圖。例如,右邊兩個(gè)圖都是強(qiáng)連通圖。 有向圖G中的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。顯然,強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量,即本身,非強(qiáng)連通圖

6、有多個(gè)強(qiáng)連通分量,1,0,2,3,1,0,2,b,a,13,例 有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多需要多少條邊？最少需要多 少條邊,答：有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有n(n-1)條邊(構(gòu)成一個(gè)有向完全圖的情況)；最少有n條邊(n個(gè)頂點(diǎn)依次首尾相接構(gòu)成一個(gè)環(huán)的情況,14,練習(xí)題： 若一個(gè)非連通無(wú)向圖有10條 邊，請(qǐng)問(wèn)，該圖至少有多少 個(gè)頂點(diǎn),答：要保證圖非連通，則至少需要兩個(gè)連通分量，可讓一個(gè)分量里只有一個(gè)頂點(diǎn)，另一個(gè)分量為一個(gè)完全圖。5個(gè)頂點(diǎn)的無(wú)向完全圖共有10個(gè)頂點(diǎn)，所以至少需要6個(gè)頂點(diǎn),15,真題演練,1）若無(wú)向圖G=（V，E）中含有7個(gè)頂點(diǎn)，要保證G在任何情況下都是連通的，則需要的邊數(shù)最少為

7、（ ） A、6 B、15 C、16 D、21 （2）一個(gè)無(wú)向圖有16條邊，若度為4的頂點(diǎn)有3個(gè)，度為4的頂點(diǎn)有3個(gè)，其余頂點(diǎn)的度數(shù)均小于3，則該圖至少有（ ）個(gè)頂點(diǎn)。 A、10 B、11 C、12 D、13,16,二、圖的存儲(chǔ)結(jié)構(gòu),鄰接矩陣存儲(chǔ)方法 鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n(n0)個(gè)頂點(diǎn)的圖,頂點(diǎn)的順序依次為(v0,v1,vn-1),則G的鄰接矩陣A是n階方陣,其定義如下： (1) 如果G是無(wú)向圖,則： Aij= 1:若(vi,vj)E(G) 0:其他 (2) 如果G是有向圖,則： Aij= 1:若E(G) 0:其他,17,18,3) 如果G是帶權(quán)無(wú)向圖,

8、則： Aij= wij :若vivj且(vi,vj)E(G) :其他,19,4) 如果G是帶權(quán)有向圖,則： Aij= wij :若vivj且E(G) :其他,20,思考題： 對(duì)于有n個(gè)頂點(diǎn)e條邊的無(wú)向圖，鄰接矩陣表示時(shí)有多少個(gè)元素，多少個(gè)非0元素？ 對(duì)于有n個(gè)頂點(diǎn)e條邊的有向圖，鄰接矩陣表示時(shí)有多少個(gè)元素，多少個(gè)非0元素,21,鄰接矩陣的特點(diǎn)如下： (1) 圖的鄰接矩陣表示是唯一的。 (2) 無(wú)向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。因此,按照壓縮存儲(chǔ)的思想,在具體存放鄰接矩陣時(shí)只需存放上(或下)三角形陣的元素即可。 (3) 不帶權(quán)的有向圖的鄰接矩陣一般來(lái)說(shuō)是一個(gè)稀疏矩陣,因此,當(dāng)圖的頂點(diǎn)較多時(shí),可

9、以采用三元組表的方法存儲(chǔ)鄰接矩陣。 (4) 對(duì)于無(wú)向圖,鄰接矩陣的第i行(或第i列)非零元素(或非元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)vi的度,22,5) 對(duì)于有向圖,鄰接矩陣的第i行(或第i列)非零元素(或非元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)vi的出度(或入度)。 (6) 用鄰接矩陣方法存儲(chǔ)圖,很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連。但是,要確定圖中有多少條邊,則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測(cè),所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣存儲(chǔ)圖的局限性,23,8.2.2 鄰接表存儲(chǔ)方法 圖的鄰接表存儲(chǔ)方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)方法。在鄰接表中,對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表,第i個(gè)單鏈表中的結(jié)點(diǎn)

10、表示依附于頂點(diǎn)vi的邊(對(duì)有向圖是以頂點(diǎn)vi為尾的弧)。每個(gè)單鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn),24,其中,表結(jié)點(diǎn)由三個(gè)域組成,adjvex指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置,nextarc指示下一條邊或弧的結(jié)點(diǎn),info存儲(chǔ)與邊或弧相關(guān)的信息,如權(quán)值等。 表頭結(jié)點(diǎn)由兩個(gè)域組成,data存儲(chǔ)頂點(diǎn)vi的名稱或其他信息,firstarc指向鏈表中第一個(gè)結(jié)點(diǎn),表頭節(jié)點(diǎn),表節(jié)點(diǎn),25,MAX_VEX-1,26,思考題： 對(duì)于有n個(gè)頂點(diǎn)e條邊的無(wú)向圖，鄰接表表示時(shí)有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn)？ 對(duì)于有n個(gè)頂點(diǎn)e條邊的有向圖，鄰接表表示時(shí)有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn),27,鄰接表的特點(diǎn)如下： (1) 鄰接表表示

11、不唯一。這是因?yàn)樵诿總€(gè)頂點(diǎn)對(duì)應(yīng)的單鏈表中,各邊結(jié)點(diǎn)的鏈接次序可以是任意的,取決于建立鄰接表的算法以及邊的輸入次序。 (2) 對(duì)于有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,其鄰接表有n個(gè)頂點(diǎn)結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)。顯然,在總的邊數(shù)小于n(n-1)/2的情況下,鄰接表比鄰接矩陣要節(jié)省空間。 (3) 對(duì)于無(wú)向圖,鄰接表的頂點(diǎn)vi對(duì)應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目正好是頂點(diǎn)vi的度。 (4) 對(duì)于有向圖,鄰接表的頂點(diǎn)vi對(duì)應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目?jī)H僅是vi的出度。其入度為鄰接表中所有adjvex域值為i的邊結(jié)點(diǎn)數(shù)目,28,真題演練,1）無(wú)向圖的鄰接矩陣是一個(gè) （ ） A、對(duì)稱矩陣 B、零矩陣 C、上三角矩陣 D、非對(duì)稱矩陣

12、 （2）關(guān)于圖的存儲(chǔ)敘述中，正確的是（ ） A、用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān) B、用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)個(gè)數(shù)無(wú)關(guān) C、用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān) D、用鄰接表法存儲(chǔ)圖，占用的占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)個(gè)數(shù)無(wú)關(guān),29,三、圖的遍歷,圖的遍歷算法有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)結(jié)構(gòu)是(正)鄰接鏈表,從給定圖中任意指定的頂點(diǎn)(稱為初始點(diǎn))出發(fā),按照某種搜索方法沿著圖的邊訪問(wèn)圖中的所有頂點(diǎn),使每個(gè)頂點(diǎn)僅被訪問(wèn)一次,這個(gè)過(guò)程稱為圖的遍歷。 如果給定圖是

13、連通的無(wú)向圖或者是強(qiáng)連通的有向圖,則遍歷過(guò)程一次就能完成,并可按訪問(wèn)的先后順序得到由該圖所有頂點(diǎn)組成的一個(gè)序列,30,DFS序列,2,1,0,3,4,部分合法的DFS序列： 2 3 0 1 4；2 1 0 4 3；2 4 3 0 1,不合法的DFS序列舉例： 2 0 1 3 4,31,部分合法的BFS序列： 2 1 3 4 0;2 3 1 4 0;2 4 1 3 0,不合法的BFS序列舉例： 2 1 0 3 4 ；2 3 0 4 1,但是，若對(duì)上圖采用上面的鄰接表存儲(chǔ),假設(shè)初始頂點(diǎn)編號(hào)v=2, 進(jìn)行廣度優(yōu)先遍歷的話，序列就是唯一的了。此時(shí)的遍歷序列如下,BFS序列,2,1,3,4,0,32,真

14、題演練,1)有N個(gè)頂點(diǎn)、E條邊且用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是 （ ） A、O（N） B、O（E） C、O（N+E） D、O（N*E） (2)如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先遍歷即可訪問(wèn)所有頂點(diǎn)，則該圖一定是（ ） A. 完全圖 B. 連通圖 C.有回路 D.一棵樹(shù),33,四、圖的應(yīng)用,最小生成樹(shù) 拓?fù)渑判?最短路徑 關(guān)鍵路徑,34,最小生成樹(shù),生成樹(shù)的概念 一個(gè)連通圖的生成樹(shù)是一個(gè)極小連通子圖,它含有圖中全部頂點(diǎn),但只有構(gòu)成一棵樹(shù)的(n-1)條邊。 命題：如果在一棵生成樹(shù)上添加一條邊,必定構(gòu)成一個(gè)環(huán)。 因?yàn)檫@條邊使得它依附的那兩個(gè)頂點(diǎn)之間有了第二條路徑。一

15、棵有n個(gè)頂點(diǎn)的生成樹(shù)(連通無(wú)回路圖)有且僅有(n-1)條邊,如果一個(gè)圖有n個(gè)頂點(diǎn)和小于(n-1)條邊,則是非連通圖。如果它多于(n-1)條邊,則一定有回路。 但是,有(n-1)條邊的圖不一定都是生成樹(shù),35,由深度優(yōu)先遍歷得到的生成樹(shù)稱為深度優(yōu)先生成樹(shù)；由廣度優(yōu)先遍歷得到的生成樹(shù)稱為廣度優(yōu)先生成樹(shù)。這樣的生成樹(shù)是由遍歷時(shí)訪問(wèn)過(guò)的n個(gè)頂點(diǎn)和遍歷時(shí)經(jīng)歷的n-1條邊組成。 對(duì)于非連通圖,每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過(guò)的邊一起構(gòu)成一棵生成樹(shù),各個(gè)連通分量的生成樹(shù)組成非連通圖的生成森林,36,從1號(hào)頂點(diǎn)開(kāi)始的深度優(yōu)先 遍歷序列：1 0 3 2 4,從1號(hào)頂點(diǎn)開(kāi)始的深度優(yōu)先 遍歷序列：1 0 2 3

16、4,37,普里姆算法 普里姆(Prim)算法是一種構(gòu)造性算法。 假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖,T=(U,TE)是G的最小生成樹(shù),其中U是T的頂點(diǎn)集,TE是T的邊集,則由G構(gòu)造最小生成樹(shù)T的步驟如下,38,1) 初始化U=v。v到其他頂點(diǎn)的所有邊為候選邊； (2) 重復(fù)以下步驟n-1次,使得其他n-1個(gè)頂點(diǎn)被加入到U中： 從候選邊中挑選權(quán)值最小的邊輸出,設(shè)該邊在V-U中的頂點(diǎn)是k,將k加入U(xiǎn)中,刪除和k關(guān)聯(lián)的邊； 考察當(dāng)前V-U中的所有頂點(diǎn)vi,修改候選邊：若(vk,vi)的權(quán)值小于原來(lái)和vi關(guān)聯(lián)的候選邊,則用(vk,vi)取代后者作為候選邊,普里姆算法過(guò)程,39,0,1

17、,2,3,4,6,5,19,5,14,18,27,16,8,21,3,12,7,0,4,3,2,1,6,5,14,8,5,3,16,21,19,18,14,0,0,0,0,0,0,0,0,0,16,4,8,4,12,4,0,3,3,3,7,21,3,0,2,5,0,0,0,U V-U,i, closesti) iU，closestiVU,候選邊,40,8.4.5 克魯斯卡爾算法 克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增次序選擇合適的邊來(lái)構(gòu)造最小生成樹(shù)的方法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖,T=(U,TE)是G的最小生成樹(shù),1) 置U的初值等于V(即包含有G中的全

18、部頂點(diǎn)),TE的初值為空集(即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量)。 (2) 將圖G中的邊按權(quán)值從小到大的順序依次選取：若選取的邊未使生成樹(shù)T形成回路,則加入TE；否則舍棄,直到TE中包含(n-1)條邊為止,41,0,3,5,2,1,4,5,1,6,3,5,4,6,5,2,0,2,5,3,1,4,6,0,0,3,3,1,1,0,0,0,0,42,43,真題演練,例：下列關(guān)于最小生成樹(shù)的敘述中，正確的是 （ ） A、最小生成樹(shù)的代價(jià)是唯一的 B、所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹(shù)中 C、使用普里姆算法從不同頂點(diǎn)開(kāi)始得到的最小生成樹(shù)一定相同 D、使用普里姆算法和克魯斯卡爾算法得到的最小生成樹(shù)

19、一定相同,44,真題演練,已知無(wú)向網(wǎng)的鄰接矩陣如圖所示，要求： （1）畫出該圖； （2）按照克魯斯卡爾算法給出該網(wǎng)的最小生成樹(shù)的過(guò)程,45,1）該無(wú)向網(wǎng)如下圖所示,46,2)生成過(guò)程如下,2,47,最短路徑,對(duì)于帶權(quán)的圖,考慮路徑上各邊上的權(quán)值,則通常把一條路徑上所經(jīng)邊的權(quán)值之和定義為該路徑的路徑長(zhǎng)度或稱帶權(quán)路徑長(zhǎng)度。 從源點(diǎn)到終點(diǎn)可能不止一條路徑,把帶權(quán)路徑長(zhǎng)度最短的那條路徑稱為最短路徑,其路徑長(zhǎng)度(權(quán)值之和)稱為最短路徑長(zhǎng)度或者最短距離,48,從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑 問(wèn)題：給定一個(gè)帶權(quán)有向圖G與源點(diǎn)v,求從v到G中其他頂點(diǎn)的最短路徑,并限定各邊上的權(quán)值大于或等于0,49,采用狄克

20、斯特拉(Dijkstra)算法求解 基本思想是：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖, 把圖中頂點(diǎn)集合V分成兩組： 第一組為已求出最短路徑的頂點(diǎn)集合(用S表示,初始時(shí)S中只有一個(gè)源點(diǎn),以后每求得一條最短路徑v,vk,就將vk加入到集合S中,直到全部頂點(diǎn)都加入到S中,算法就結(jié)束了) 第二組為其余未確定最短路徑的頂點(diǎn)集合(用U表示,50,按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中,總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。 此外,每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離,S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度,U中的頂點(diǎn)的距離從v到此頂點(diǎn)只包括S中

21、的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度,51,1) 初始時(shí),S只包含源點(diǎn),即S=v,v的距離為0。U包含除v外的其他頂點(diǎn),U中頂點(diǎn)u距離為邊上的權(quán)(若v與u有邊)或(若u不是v的出邊鄰接點(diǎn))。即圖的鄰接矩陣中v所在的行元素值。 (2) 從U中選取一個(gè)距離v最小的頂點(diǎn)k,把k加入S中(該選定的距離就是v到k的最短路徑長(zhǎng)度)。 (3) 以k為新考慮的中間點(diǎn),修改U中各頂點(diǎn)的距離：若從源點(diǎn)v到頂點(diǎn)u(uU)的距離(經(jīng)過(guò)頂點(diǎn)k)比原來(lái)距離(不經(jīng)過(guò)頂點(diǎn)k)短,則修改頂點(diǎn)u的距離值,修改后的距離值為頂點(diǎn)k的距離加上邊上的權(quán)。 (4) 重復(fù)步驟(2)和(3)直到所有頂點(diǎn)都包含在S中,狄克斯特拉算法的過(guò)程,52,

22、頂點(diǎn)V到j(luò)的最小距離MIN(cvk+wkj,cvj,53,S U dist 0 1 2 3 4 5 6 0 1,2,3,4,5,6 0,4,6,6, 0,1 2,3,4,5,6 0,4,5,6,11, 0,1,2 3,4,5,6 0,4,5,6,11,9, 0,1,2,3 4,5,6 0,4,5,6,11,9, 0,1,2,3,5 4,6 0,4,5,6,10,9,17 0,1,2,3,5,4 6 0,4,5,6,10,9,16 0,1,2,3,5,4,6 0,4,5,6,10,9,16,path 0 1 2 3 4 5 6 0,0,0,0,-1,-1,-1 0,0,1,0, 1,-1,-1

23、0,0,1,0, 1, 2,-1 0,0,1,0, 1, 2,-1 0,0,1,0, 5, 2, 5 0,0,1,0, 5, 2, 4 0,0,1,0, 5, 2, 4,54,4,3,8,1,6,4,2,5,6,1,4,7,6,6,0,0,4,6,6,0,0,0,0,0,4,0,11,5,5,9,6,9,10,17,1,1,5,2,5,10,16,4,16,5,6,2,0,1,55,8.5.3 每對(duì)頂點(diǎn)之間的最短路徑 問(wèn)題：對(duì)于一個(gè)各邊權(quán)值均大于零的有向圖,對(duì)每一對(duì)頂點(diǎn)vivj,求出vi與vj之間的最短路徑和最短路徑長(zhǎng)度。 可以通過(guò)以每個(gè)頂點(diǎn)作為源點(diǎn)循環(huán)求出每對(duì)頂點(diǎn)之間的最短路徑。除此之外,弗

24、洛伊德(Floyd)算法也可用于求兩頂點(diǎn)之間最短路徑,56,假設(shè)有向圖G=(V,E)采用鄰接矩陣cost存儲(chǔ),另外設(shè)置一個(gè)二維數(shù)組A用于存放當(dāng)前頂點(diǎn)之間的最短路徑長(zhǎng)度,分量Aij表示當(dāng)前頂點(diǎn)vi到頂點(diǎn)vj的最短路徑長(zhǎng)度。 弗洛伊德算法的基本思想是遞推產(chǎn)生一個(gè)矩陣序列A0,A1,Ak,An,其中Akij表示從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度,57,初始時(shí),有A-1ij=costij。當(dāng)求從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k+1的最短路徑長(zhǎng)度時(shí),要分兩種情況考慮： 一種情況是該路徑不經(jīng)過(guò)頂點(diǎn)編號(hào)為k+1的頂點(diǎn),此時(shí)該路徑長(zhǎng)度與從頂點(diǎn)vi到頂點(diǎn)vj的路

25、徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度相同； 另一種情況是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑上經(jīng)過(guò)編號(hào)為k+1的頂點(diǎn),58,Ak+1i,j=MIN(Aki,j,Aki,k+1+Akk+1,j,59,那么,該路徑可分為兩段: (1) 從頂點(diǎn)vi到頂點(diǎn)vk+1的最短路徑; (2) 從頂點(diǎn)vk+1到頂點(diǎn)vj的最短路徑。 此時(shí)最短路徑長(zhǎng)度等于這兩段路徑長(zhǎng)度之和。這兩種情況中的較小值,就是所要求的從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k+1的最短路徑,60,弗洛伊德思想可用如下的表達(dá)式來(lái)描述： A-1ij=costij Ak+1ij=MIN Akij, Akik+1+Akk+1j (0kn-

26、1,61,采用弗洛伊德算法求解過(guò)程,0,1,2,3,5,3,2,7,3,1,2,4,62,考慮頂點(diǎn)v0,A0ij表示由vi到vj,經(jīng)由頂點(diǎn)v0的最短路徑。 v2-v0-v1：不改變。 v2-v0-v3：不改變,63,考慮頂點(diǎn)v1,A1ij表示由vi到vj,經(jīng)由頂點(diǎn)v1的最短路徑。 v0-v1-v2,路徑長(zhǎng)度為9,將A02改為9。 path02改為1,64,考慮頂點(diǎn)v2,A2ij表示由vi到vj,經(jīng)由頂點(diǎn)v2的最短路徑。 v3-v2-v0,長(zhǎng)度為4,將A30改為4； v3-v2-v1,長(zhǎng)度為4,將A31改為4。 v1-v2-v0,長(zhǎng)度為7,將A10改為7。 將path30、path31和path

27、10均改為2。因此,有,65,考慮頂點(diǎn)v3,A3ij表示由vi到vj,經(jīng)由頂點(diǎn)v3的最短路徑。 v0-v3-v2：長(zhǎng)度為8,A02改為8； v1-v3-v2-v0,長(zhǎng)度為6,A10改為6； v1-v3-v2,長(zhǎng)度為3, A12改為3。 將path02、path10后path12均改為3,66,從0到0路徑為：0,0路徑長(zhǎng)度為：0 從0到1路徑為：0,1路徑長(zhǎng)度為：5 從0到2路徑為：0,3,2路徑長(zhǎng)度為：8 從0到3路徑為：0,3路徑長(zhǎng)度為：7 從1到0路徑為：1,3,2,0路徑長(zhǎng)度為：6 從1到1路徑為：1,1路徑長(zhǎng)度為：0 從1到2路徑為：1,3,2 路徑長(zhǎng)度為：3 從1到3路徑為：1,3

28、路徑長(zhǎng)度為：2,A,Path,67,從2到0路徑為：2,0路徑長(zhǎng)度為：3 從2到1路徑為：2,1路徑長(zhǎng)度為：3 從2到2路徑為：2,2路徑長(zhǎng)度為：0 從2到3路徑為：2,3路徑長(zhǎng)度為：2 從3到0路徑為：3,2,0 路徑長(zhǎng)度為：4 從3到1路徑為：3,2,1 路徑長(zhǎng)度為：4 從3到2路徑為：3,2路徑長(zhǎng)度為：1 從3到3路徑為：3,3路徑長(zhǎng)度為：0,68,拓樸排序,設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖,V中頂點(diǎn)序列v1,v2,vn稱為一個(gè)拓?fù)湫蛄?當(dāng)且僅當(dāng)該頂點(diǎn)序列滿足下列條件： 若是圖中的邊(即從頂點(diǎn)vi到vj有一條路徑),則在序列中頂點(diǎn)vi必須排在頂點(diǎn)vj之前。 在一個(gè)有向圖中找一個(gè)

29、拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判?69,1) 從有向圖中選擇一個(gè)沒(méi)有前驅(qū)(即入度為0)的頂點(diǎn)并且輸出它。 (2) 從網(wǎng)中刪去該頂點(diǎn),并且刪去從該頂點(diǎn)發(fā)出的全部有向邊。 (3) 重復(fù)上述兩步,直到剩余的網(wǎng)中不再存在沒(méi)有前驅(qū)的頂點(diǎn)為止,拓?fù)渑判虿襟E,70,0,0,1,2,4,5,3,4,1,2,5,3,全部可能的拓?fù)渑判蛐蛄校?041253 041523 045123 450123 401253 405123 401523,71,關(guān)鍵路徑,若用帶權(quán)有向圖(DAG)描述工程的預(yù)計(jì)進(jìn)度,以頂點(diǎn)表示事件,有向邊表示活動(dòng),邊e的權(quán)c(e)表示完成活動(dòng)e所需的時(shí)間(比如天數(shù)),或者說(shuō)活動(dòng)e持續(xù)時(shí)間。 圖中入度為0

30、的頂點(diǎn)（源點(diǎn)）的開(kāi)始事件(如開(kāi)工儀式),出度為0的頂點(diǎn)（匯點(diǎn)）表示工程結(jié)束事件。則稱這樣的有向圖為AOE網(wǎng)(Activity On Edge,72,源點(diǎn),匯點(diǎn),73,幾個(gè)定義： (1) 事件v的最早可發(fā)生時(shí)間：假設(shè)事件x是源點(diǎn),事件y為匯點(diǎn),并規(guī)定事件x的發(fā)生時(shí)間為0。定義圖中任一事件v的最早(event early)可發(fā)生時(shí)間ve(v)等于x到v所有路徑長(zhǎng)度的最大值,即,ve(v),上式中的MAX是對(duì)x到v的所有路徑p取最大值,c(p)表示路徑p的長(zhǎng)度(路徑上邊長(zhǎng)之和) ,即,c(p),完成整個(gè)工程所需的最少時(shí)間,等于事件y的最早可發(fā)生時(shí)間ve(y,74,源點(diǎn),匯點(diǎn),75,整個(gè)工程完成的最短

31、時(shí)間指的是：從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度，具有最大長(zhǎng)度的路徑叫關(guān)鍵路徑,關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。 注意：在一個(gè)AOE網(wǎng)中，可以有不止一條的關(guān)鍵路徑,源點(diǎn),匯點(diǎn),76,2) 事件v的最遲可發(fā)生時(shí)間：定義在不影響整個(gè)工程進(jìn)度的前提下,事件v必須發(fā)生的時(shí)間稱為v的最遲(event late)可發(fā)生時(shí)間,記作vl(v)。vl(v)應(yīng)等于ve(y)與v到y(tǒng)的最長(zhǎng)路徑長(zhǎng)度之差(y是匯點(diǎn)),即,vl(v)=ve(y),3) 關(guān)鍵活動(dòng):若活動(dòng)v滿足ve(v)+c(ai)=vl(w),則稱活動(dòng)ai為關(guān)鍵活動(dòng)，ai=。 對(duì)關(guān)鍵活動(dòng)來(lái)說(shuō),不存在富余時(shí)間。顯然,關(guān)鍵

32、路徑上的活動(dòng)都是關(guān)鍵活動(dòng)。找出關(guān)鍵活動(dòng)的意義在于,可以適當(dāng)?shù)卦黾訉?duì)關(guān)鍵活動(dòng)的投資(人力、物力等),相應(yīng)地減少對(duì)非關(guān)鍵活動(dòng)的投資,從而減少關(guān)鍵活動(dòng)的持續(xù)時(shí)間,縮短整個(gè)工程的工期,77,78,只要計(jì)算出各項(xiàng)點(diǎn)的ve(v)和vl(v)的值,就能找出所有的關(guān)鍵活動(dòng)。為了便于計(jì)算,引入下面兩個(gè)遞推式,其中,x和y分別是源點(diǎn)和匯點(diǎn)。 ve(x)=0 ve(w)= wx 上式中的MAX對(duì)所有射入w的邊取最大值。 vl(y)=0 vl(v)= vy,79,1) 對(duì)于源點(diǎn)x,置ve(x)=0； (2) 對(duì)AOE網(wǎng)進(jìn)行拓?fù)渑判?。如發(fā)現(xiàn)回路,工程無(wú)法進(jìn)行,則退出；否則繼續(xù)下一步。 (3) 按頂點(diǎn)的拓?fù)浯涡?反復(fù)用式

33、8.4,依次求其余各項(xiàng)點(diǎn)v的ve(v)值。(實(shí)際上,步驟(2)和步驟(3)可以合在一起完成,即一邊對(duì)頂點(diǎn)進(jìn)行拓?fù)渑判?一邊求出各點(diǎn)的ve(v)之值。) (4) 對(duì)于匯點(diǎn)y,置vl(y)=ve(y,求AOE網(wǎng)的關(guān)鍵活動(dòng)的過(guò)程,80,5) 按頂點(diǎn)拓?fù)浯涡蛑嫘?反復(fù)用式8.5,依次求其余各項(xiàng)點(diǎn)v的vl(v)的值。即對(duì)v射出的所有邊,檢查是否滿足式8.3,若是,則輸出該邊的有關(guān)信息,指明該邊所對(duì)應(yīng)的活動(dòng)是關(guān)鍵活動(dòng)。 (6) 活動(dòng)ai的最早開(kāi)始時(shí)間e(i)是該活動(dòng)的起點(diǎn)所表示的事件最早發(fā)生時(shí)間。如果由邊表示活動(dòng)ai,則有e(i)=ve(j)。 (7) 活動(dòng)ai的最遲開(kāi)始時(shí)間l(i)是該活動(dòng)的終點(diǎn)所表示事件的最遲發(fā)生時(shí)間與該活動(dòng)的所需時(shí)間之差。如果用邊表示活動(dòng)ai,則有l(wèi)(i)=vl(k)-ai所需時(shí)間,81,8) 一個(gè)活動(dòng)ai的最遲開(kāi)始時(shí)間l(i)和其最早開(kāi)始時(shí)間e(i)的差額d(i)=l(i)-e(i)是該活動(dòng)完成的時(shí)間余量(富余時(shí)間)。它是在不增加完成整個(gè)工程所需的總時(shí)間的情況下,活動(dòng)ai可以拖延的時(shí)間。 (9) 當(dāng)一活動(dòng)的時(shí)間余量為零時(shí),說(shuō)明該活動(dòng)必須如期完成,否則就會(huì)拖延完成整個(gè)工程的進(jìn)度。所以我們稱l(i)-e(i)=0,即l(i)=e(i)的活動(dòng)ai是關(guān)鍵活動(dòng),82,計(jì)算各事件的ve