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

1、本章出題特點(diǎn)本章出題特點(diǎn) 在歷年統(tǒng)考里,大多以客觀題不勞方式出現(xiàn),詳細(xì)如下:年份年份客觀客觀主觀主觀20091(2分分)1(10分分)20192(4分分)20191(2分分)1(8分分)20194(8分分)知識(shí)點(diǎn)歸納圖圖運(yùn)用運(yùn)用遍歷方式遍歷方式存儲(chǔ)構(gòu)造存儲(chǔ)構(gòu)造關(guān)鍵途徑關(guān)鍵途徑最小生成樹最小生成樹廣度優(yōu)先廣度優(yōu)先深度優(yōu)先深度優(yōu)先鄰接表鄰接表最短途徑最短途徑拓?fù)渑判蛲負(fù)渑判蜞徑泳仃囙徑泳仃嚫靖拍罡靖拍盍私饬私庹莆照莆照莆照莆照莆铡⑦\(yùn)用掌握、運(yùn)用根本概念根本概念一、圖的概念和相關(guān)術(shù)語一、圖的概念和相關(guān)術(shù)語圖的定義圖的定義 圖圖(Graph)G由兩個(gè)集合由兩個(gè)集合V(Vertex)和和E(Edge

2、)組成組成,記為記為G=(V,E),其中其中V是頂點(diǎn)的有限集合是頂點(diǎn)的有限集合,記記為為V(G),E是銜接是銜接V中兩個(gè)不同頂點(diǎn)中兩個(gè)不同頂點(diǎn)(頂點(diǎn)對(duì)頂點(diǎn)對(duì))的邊的邊的有限集合的有限集合,記為記為E(G)。 頂點(diǎn)集合為空的圖稱為空?qǐng)D。頂點(diǎn)集合為空的圖稱為空?qǐng)D。 E(G)為空時(shí)為空時(shí),圖中只需頂點(diǎn)而沒有邊。圖中只需頂點(diǎn)而沒有邊。圖的根本術(shù)語圖的根本術(shù)語 1. 端點(diǎn)和鄰接點(diǎn)端點(diǎn)和鄰接點(diǎn) 在一個(gè)無向圖中在一個(gè)無向圖中,假設(shè)存在假設(shè)存在一條邊一條邊(vi,vj),那么稱那么稱vi和和vj為此為此邊的兩個(gè)端點(diǎn)邊的兩個(gè)端點(diǎn),并稱它們互為鄰并稱它們互為鄰接點(diǎn)。接點(diǎn)。 在一個(gè)有向圖中在一個(gè)有向圖中,假設(shè)存在假

3、設(shè)存在一條邊一條邊,那么稱此邊是頂那么稱此邊是頂點(diǎn)點(diǎn)vi的一條出邊的一條出邊,同時(shí)也是頂點(diǎn)同時(shí)也是頂點(diǎn)vj的一條入邊；稱的一條入邊；稱vi和和vj分別為此分別為此邊的起始端點(diǎn)邊的起始端點(diǎn)(簡(jiǎn)稱為起點(diǎn)簡(jiǎn)稱為起點(diǎn))和終和終止端點(diǎn)止端點(diǎn)(簡(jiǎn)稱終點(diǎn)簡(jiǎn)稱終點(diǎn))；稱；稱vi和和vj互互為鄰接點(diǎn)。為鄰接點(diǎn)。13024(a)13024(b)2. 途徑和途徑長度途徑和途徑長度 在一個(gè)圖在一個(gè)圖G=(V,E)中中,從頂點(diǎn)從頂點(diǎn)vi到頂?shù)巾旤c(diǎn)點(diǎn) v j 的 一 條 途 徑 是 一 個(gè) 頂 點(diǎn) 序 列的 一 條 途 徑 是 一 個(gè) 頂 點(diǎn) 序 列(vi,vi1,vi2,vim,vj),假設(shè)此圖假設(shè)此圖G是無向是無向圖

4、圖,那么邊那么邊(vi,vi1),(vi1,vi2),(vim-1,vim),(vim,vj)屬于屬于E(G)；假設(shè)此圖是；假設(shè)此圖是有向圖有向圖,那么那么,屬于屬于E(G)。 途徑長度是指一條途徑上經(jīng)過的邊途徑長度是指一條途徑上經(jīng)過的邊的數(shù)目。假設(shè)一條途徑上除開場(chǎng)點(diǎn)和終的數(shù)目。假設(shè)一條途徑上除開場(chǎng)點(diǎn)和終了點(diǎn)可以一樣外了點(diǎn)可以一樣外,其他頂點(diǎn)均不一樣其他頂點(diǎn)均不一樣,那那么稱此途徑為簡(jiǎn)單途徑。例如么稱此途徑為簡(jiǎn)單途徑。例如,有圖有圖中中,(v0,v2,v1)就是一條簡(jiǎn)單途徑就是一條簡(jiǎn)單途徑,其長度其長度為為2。2103 3. 連通、連通圖和連通分量連通、連通圖和連通分量 在無向圖在無向圖G中中

5、,假設(shè)從頂點(diǎn)假設(shè)從頂點(diǎn)vi到頂點(diǎn)到頂點(diǎn)vj有途徑有途徑,那么稱那么稱vi和和vj是連通的。是連通的。 假設(shè)圖假設(shè)圖G中恣意兩個(gè)頂點(diǎn)中恣意兩個(gè)頂點(diǎn)都連通都連通,那么稱那么稱G為連通圖為連通圖,否那否那么稱為非連通圖。么稱為非連通圖。 無向圖無向圖G中的極大連通子中的極大連通子圖稱為圖稱為G的連通分量。顯然的連通分量。顯然,任任何連通圖的連通分量只需一個(gè)何連通圖的連通分量只需一個(gè),即本身即本身,而非連通圖有多個(gè)連通而非連通圖有多個(gè)連通分量。分量。1023102(b)(a)3“極大的含義：指的是對(duì)極大的含義：指的是對(duì)子圖再添加圖子圖再添加圖G G中的其它頂中的其它頂點(diǎn)，子圖就不再連通。點(diǎn)，子圖就不再

6、連通。 4. 頂點(diǎn)的度、入度和出度頂點(diǎn)的度、入度和出度 在無向圖中在無向圖中,頂點(diǎn)所具有的邊的數(shù)目頂點(diǎn)所具有的邊的數(shù)目稱為該頂點(diǎn)的度。稱為該頂點(diǎn)的度。 在有向圖中在有向圖中,以頂點(diǎn)以頂點(diǎn)vi為終點(diǎn)的入邊為終點(diǎn)的入邊的數(shù)目的數(shù)目,稱為該頂點(diǎn)的入度。以頂點(diǎn)稱為該頂點(diǎn)的入度。以頂點(diǎn)vi為為始點(diǎn)的出邊的數(shù)目始點(diǎn)的出邊的數(shù)目,稱為該頂點(diǎn)的出度。稱為該頂點(diǎn)的出度。一個(gè)頂點(diǎn)的入度與出度的和為該頂點(diǎn)的一個(gè)頂點(diǎn)的入度與出度的和為該頂點(diǎn)的度。度。 假設(shè)一個(gè)圖中有假設(shè)一個(gè)圖中有n個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和e條邊條邊,每每個(gè)頂點(diǎn)的度為個(gè)頂點(diǎn)的度為di(1in),那么有：那么有： n1iid21e13024(a)13024(b)

7、 5. 完全圖完全圖 假設(shè)無向圖中的每?jī)蓚€(gè)頂點(diǎn)之間假設(shè)無向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著一條邊都存在著一條邊,有向圖中的每?jī)蓚€(gè)頂有向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著方向相反的兩條邊點(diǎn)之間都存在著方向相反的兩條邊,那那么稱此圖為完全圖。么稱此圖為完全圖。 顯然顯然,完全無向圖包含有完全無向圖包含有n(n-1)/2條條邊邊,完全有向圖包含有完全有向圖包含有n(n-1)條邊。條邊。 例如例如,圖圖(a)所示的圖是一個(gè)具有所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全無向圖個(gè)頂點(diǎn)的完全無向圖,共有共有6條邊。圖條邊。圖(b)所示的圖是一個(gè)具有所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全有個(gè)頂點(diǎn)的完全有向圖向圖,共有共有12條邊。條邊

8、。 (b)10231023(a) 6. 子圖子圖 設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖G=(V,E)和和G=(V,E),假設(shè)假設(shè)V是是V的子集的子集,即即VV,且且E是是E的子集的子集,即即EE,那么稱那么稱G是是G的子的子圖。例如圖圖。例如圖(b)是圖是圖(a)的子圖的子圖,而圖而圖(c)不是圖不是圖(b)的子圖。的子圖。(a)1302413024(b)13024(c) 7. 回路或環(huán)回路或環(huán) 假設(shè)一條途徑上的開場(chǎng)點(diǎn)與終假設(shè)一條途徑上的開場(chǎng)點(diǎn)與終了點(diǎn)為同一個(gè)頂點(diǎn)了點(diǎn)為同一個(gè)頂點(diǎn),那么此途徑被稱那么此途徑被稱為回路或環(huán)。開場(chǎng)點(diǎn)與終了點(diǎn)一樣為回路或環(huán)。開場(chǎng)點(diǎn)與終了點(diǎn)一樣的簡(jiǎn)單途徑被稱為簡(jiǎn)單回路或簡(jiǎn)單的簡(jiǎn)單途徑被

9、稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。環(huán)。 例如例如,右圖中右圖中,(v0,v2,v1,v0)就是就是一條簡(jiǎn)單回路一條簡(jiǎn)單回路,其長度為其長度為3。1023 8. 強(qiáng)連通圖和強(qiáng)連通分量強(qiáng)連通圖和強(qiáng)連通分量 在有向圖在有向圖G中中,假設(shè)從頂點(diǎn)假設(shè)從頂點(diǎn)vi到頂點(diǎn)到頂點(diǎn)vj有途徑有途徑,那么稱從那么稱從vi到到vj是連通的。是連通的。 假設(shè)圖假設(shè)圖G中的恣意兩個(gè)頂點(diǎn)中的恣意兩個(gè)頂點(diǎn)vi和和vj都連通都連通,即從即從vi到到vj和從和從vj到到vi都存在途徑都存在途徑,那么稱圖那么稱圖G是強(qiáng)連是強(qiáng)連通圖。例如通圖。例如,右邊兩個(gè)圖都是強(qiáng)連右邊兩個(gè)圖都是強(qiáng)連通圖。通圖。 有向圖有向圖G中的極大強(qiáng)連通子中的極大強(qiáng)連通子

10、圖稱為圖稱為G的強(qiáng)連通分量。顯然的強(qiáng)連通分量。顯然,強(qiáng)強(qiáng)連通圖只需一個(gè)強(qiáng)連通分量連通圖只需一個(gè)強(qiáng)連通分量,即本即本身身,非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。1023102(b)(a) 例 有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)的情況)。 1 2 3 n n-1 練習(xí)題： 假設(shè)一個(gè)非連通無向圖有10條 邊，請(qǐng)問，該圖至少有多少 個(gè)頂點(diǎn)？答：要保證圖非連通，那么至少需求兩個(gè)連通分量，可讓一個(gè)分量里只需一個(gè)頂點(diǎn)，另一個(gè)分量為一個(gè)完全

11、圖。5個(gè)頂點(diǎn)的無向完全圖共有10個(gè)頂點(diǎn)，所以致少需求6個(gè)頂點(diǎn)。真題演練真題演練1假設(shè)無向圖假設(shè)無向圖G=V，E中含有中含有7個(gè)頂個(gè)頂點(diǎn)，要保證點(diǎn)，要保證G在任何情況下都是連通的，那在任何情況下都是連通的，那么需求的邊數(shù)最少為么需求的邊數(shù)最少為 A、6 B、15 C、16 D、212一個(gè)無向圖有一個(gè)無向圖有16條邊，假設(shè)度為條邊，假設(shè)度為4的頂?shù)捻旤c(diǎn)有點(diǎn)有3個(gè)，度為個(gè)，度為4的頂點(diǎn)有的頂點(diǎn)有3個(gè)，其他頂點(diǎn)的個(gè)，其他頂點(diǎn)的度數(shù)均小于度數(shù)均小于3，那么該圖至少有，那么該圖至少有 個(gè)頂個(gè)頂點(diǎn)。點(diǎn)。 A、10 B、11 C、12 D、13二、圖的存儲(chǔ)構(gòu)造二、圖的存儲(chǔ)構(gòu)造鄰接矩陣存儲(chǔ)方法鄰接矩陣存儲(chǔ)方法

12、鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)設(shè)G=(V,E)是具有是具有n(n0)個(gè)頂點(diǎn)的圖個(gè)頂點(diǎn)的圖,頂點(diǎn)的順頂點(diǎn)的順序依次為序依次為(v0,v1,vn-1),那么那么G的鄰接矩陣的鄰接矩陣A是是n階方陣階方陣,其定義如下：其定義如下： (1) 假設(shè)假設(shè)G是無向圖是無向圖,那么：那么： Aij= 1:假設(shè)假設(shè)(vi,vj)E(G) 0:其他其他 (2) 假設(shè)假設(shè)G是有向圖是有向圖,那么：那么： Aij= 1:假設(shè)假設(shè)E(G) 0:其他其他 1 3 0 2 4 1 3 0 2 4 (a) (b) 01101101111101001101110101A 0100

13、1000001100001100010102A(3) 假設(shè)假設(shè)G是帶權(quán)無向圖是帶權(quán)無向圖,那么：那么： Aij= wij :假設(shè)假設(shè)vivj且且(vi,vj)E(G) :其他其他(a) 帶權(quán)無向圖帶權(quán)無向圖 354126abcde3(b) 鄰接矩陣鄰接矩陣 6 2 6 2 6 3 4 32 3 1 4 3 5 4 3 5 3 5 3 5 (b) 鄰接矩陣鄰接矩陣 6 2 6 2 3 3 3 1 3 1 4 5 4 5 (a) 帶權(quán)有向圖帶權(quán)有向圖 354126abcde3(4) 假設(shè)假設(shè)G是帶權(quán)有向圖是帶權(quán)有向圖,那么：那么： Aij= wij :假設(shè)假設(shè)vivj且且E(G) :其他其他思索題

14、：思索題：對(duì)于有對(duì)于有n個(gè)頂點(diǎn)個(gè)頂點(diǎn)e條邊的無向圖，鄰接矩陣表示時(shí)有多條邊的無向圖，鄰接矩陣表示時(shí)有多少個(gè)元素，多少個(gè)非少個(gè)元素，多少個(gè)非0元素？元素？對(duì)于有對(duì)于有n個(gè)頂點(diǎn)個(gè)頂點(diǎn)e條邊的有向圖，鄰接矩陣表示時(shí)有多條邊的有向圖，鄰接矩陣表示時(shí)有多少個(gè)元素，多少個(gè)非少個(gè)元素，多少個(gè)非0元素？元素？鄰接矩陣的特點(diǎn)如下：鄰接矩陣的特點(diǎn)如下： (1) 圖的鄰接矩陣表示是獨(dú)一的。圖的鄰接矩陣表示是獨(dú)一的。 (2) 無向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。因此無向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。因此,按照按照緊縮存儲(chǔ)的思想緊縮存儲(chǔ)的思想,在詳細(xì)存放鄰接矩陣時(shí)只需存放上在詳細(xì)存放鄰接矩陣時(shí)只需存放上(或下或下)三

15、角形陣的元素即可。三角形陣的元素即可。 (3) 不帶權(quán)的有向圖的鄰接矩陣普通來說是一個(gè)稀疏矩不帶權(quán)的有向圖的鄰接矩陣普通來說是一個(gè)稀疏矩陣陣,因此因此,當(dāng)圖的頂點(diǎn)較多時(shí)當(dāng)圖的頂點(diǎn)較多時(shí),可以采用三元組表的方法存儲(chǔ)可以采用三元組表的方法存儲(chǔ)鄰接矩陣。鄰接矩陣。 (4) 對(duì)于無向圖對(duì)于無向圖,鄰接矩陣的第鄰接矩陣的第i行行(或第或第i列列)非零元素非零元素(或或非非元素元素)的個(gè)數(shù)正好是第的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)個(gè)頂點(diǎn)vi的度。的度。 (5) 對(duì)于有向圖對(duì)于有向圖,鄰接矩陣的第鄰接矩陣的第i行行(或第或第i列列)非零元素非零元素(或非或非元素元素)的個(gè)數(shù)正好是第的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)個(gè)頂點(diǎn)vi的出度

16、的出度(或入度或入度)。 (6) 用鄰接矩陣方法存儲(chǔ)圖用鄰接矩陣方法存儲(chǔ)圖,很容易確定圖中恣意兩個(gè)頂點(diǎn)很容易確定圖中恣意兩個(gè)頂點(diǎn)之間能否有邊相連。但是之間能否有邊相連。但是,要確定圖中有多少條邊要確定圖中有多少條邊,那么必需按那么必需按行、按列對(duì)每個(gè)元素進(jìn)展檢測(cè)行、按列對(duì)每個(gè)元素進(jìn)展檢測(cè),所破費(fèi)的時(shí)間代價(jià)很大。這是所破費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣存儲(chǔ)圖的局限性。用鄰接矩陣存儲(chǔ)圖的局限性。8.2.2 鄰接表存儲(chǔ)方法鄰接表存儲(chǔ)方法 圖的鄰接表存儲(chǔ)方法是一種順序分配與鏈?zhǔn)綀D的鄰接表存儲(chǔ)方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)方法。在鄰接表中分配相結(jié)合的存儲(chǔ)方法。在鄰接表中,對(duì)圖中每個(gè)對(duì)圖中每個(gè)頂

17、點(diǎn)建立一個(gè)單鏈表頂點(diǎn)建立一個(gè)單鏈表,第第i個(gè)單鏈表中的結(jié)點(diǎn)表示依個(gè)單鏈表中的結(jié)點(diǎn)表示依靠于頂點(diǎn)靠于頂點(diǎn)vi的邊的邊(對(duì)有向圖是以頂點(diǎn)對(duì)有向圖是以頂點(diǎn)vi為尾的弧為尾的弧)。每個(gè)單鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn)。每個(gè)單鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn)。 其中其中,表結(jié)點(diǎn)由三個(gè)域組成表結(jié)點(diǎn)由三個(gè)域組成,adjvex指示與頂點(diǎn)指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置鄰接的點(diǎn)在圖中的位置,nextarc指示下一條邊或弧的指示下一條邊或弧的結(jié)點(diǎn)結(jié)點(diǎn),info存儲(chǔ)與邊或弧相關(guān)的信息存儲(chǔ)與邊或弧相關(guān)的信息,如權(quán)值等。如權(quán)值等。 表頭結(jié)點(diǎn)由兩個(gè)域組成表頭結(jié)點(diǎn)由兩個(gè)域組成,data存儲(chǔ)頂點(diǎn)存儲(chǔ)頂點(diǎn)vi的稱號(hào)或的稱號(hào)或其他信息其他信息,

18、firstarc指向鏈表中第一個(gè)結(jié)點(diǎn)。指向鏈表中第一個(gè)結(jié)點(diǎn)。 advexnextarcinfodata表頭節(jié)點(diǎn)表節(jié)點(diǎn)014 MAX_VEX-12 02 2 01234v1v2 v3 v4 v5 3 04 (b) 逆鄰接表逆鄰接表(a) 有向圖有向圖v1v2v3v4v5MAX_VEX-113 2 3 01234(a) 正鄰接表正鄰接表v1v2 v3 v4 v5 思索題：思索題：對(duì)于有對(duì)于有n個(gè)頂點(diǎn)個(gè)頂點(diǎn)e條邊的無向圖，鄰接表表示時(shí)條邊的無向圖，鄰接表表示時(shí)有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn)？有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn)？對(duì)于有對(duì)于有n個(gè)頂點(diǎn)個(gè)頂點(diǎn)e條邊的有向圖，鄰接表表示時(shí)條邊的有向圖，鄰接表表示

19、時(shí)有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn)？有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn)？鄰接表的特點(diǎn)如下：鄰接表的特點(diǎn)如下： (1) 鄰接表表示不獨(dú)一。這是由于在每個(gè)頂點(diǎn)對(duì)應(yīng)的單鏈表鄰接表表示不獨(dú)一。這是由于在每個(gè)頂點(diǎn)對(duì)應(yīng)的單鏈表中中,各邊結(jié)點(diǎn)的鏈接次序可以是恣意的各邊結(jié)點(diǎn)的鏈接次序可以是恣意的,取決于建立鄰接表的算法取決于建立鄰接表的算法以及邊的輸入次序。以及邊的輸入次序。 (2) 對(duì)于有對(duì)于有n個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和e條邊的無向圖條邊的無向圖,其鄰接表有其鄰接表有n個(gè)頂點(diǎn)結(jié)個(gè)頂點(diǎn)結(jié)點(diǎn)和點(diǎn)和2e個(gè)邊結(jié)點(diǎn)。顯然個(gè)邊結(jié)點(diǎn)。顯然,在總的邊數(shù)小于在總的邊數(shù)小于n(n-1)/2的情況下的情況下,鄰接鄰接表比鄰接矩陣要節(jié)省空間。表

20、比鄰接矩陣要節(jié)省空間。 (3) 對(duì)于無向圖對(duì)于無向圖,鄰接表的頂點(diǎn)鄰接表的頂點(diǎn)vi對(duì)應(yīng)的第對(duì)應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目正好是頂點(diǎn)目正好是頂點(diǎn)vi的度。的度。 (4) 對(duì)于有向圖對(duì)于有向圖,鄰接表的頂點(diǎn)鄰接表的頂點(diǎn)vi對(duì)應(yīng)的第對(duì)應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目?jī)H僅是目?jī)H僅是vi的出度。其入度為鄰接表中一切的出度。其入度為鄰接表中一切adjvex域值為域值為i的邊的邊結(jié)點(diǎn)數(shù)目。結(jié)點(diǎn)數(shù)目。真題演練真題演練1無向圖的鄰接矩陣是一個(gè)無向圖的鄰接矩陣是一個(gè) A、對(duì)稱矩陣、對(duì)稱矩陣 B、零矩陣、零矩陣 C、上三角矩陣、上三角矩陣 D、非對(duì)稱矩陣、非對(duì)稱矩陣2關(guān)于圖的存儲(chǔ)表達(dá)中，正確

21、的選項(xiàng)是關(guān)于圖的存儲(chǔ)表達(dá)中，正確的選項(xiàng)是 A、用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)、用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān)數(shù)有關(guān)，而與邊數(shù)無關(guān)B、用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)、用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)個(gè)數(shù)無關(guān)有關(guān)，而與頂點(diǎn)個(gè)數(shù)無關(guān)C、用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)數(shù)、用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān)有關(guān)，而與邊數(shù)無關(guān)D、用鄰接表法存儲(chǔ)圖，占用的占用的存儲(chǔ)空間大小只與圖、用鄰接表法存儲(chǔ)圖，占用的占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)個(gè)數(shù)無關(guān)中

22、邊數(shù)有關(guān)，而與頂點(diǎn)個(gè)數(shù)無關(guān)三、圖的遍歷三、圖的遍歷 圖的遍歷算法有深度優(yōu)先搜索算法和廣度優(yōu)先圖的遍歷算法有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)構(gòu)造是搜索算法。采用的數(shù)據(jù)構(gòu)造是(正正)鄰接鏈表。鄰接鏈表。 從給定圖中恣意指定的頂點(diǎn)從給定圖中恣意指定的頂點(diǎn)(稱為初始點(diǎn)稱為初始點(diǎn))出發(fā)出發(fā),按照按照某種搜索方法沿著圖的邊訪問圖中的一切頂點(diǎn)某種搜索方法沿著圖的邊訪問圖中的一切頂點(diǎn),使每個(gè)頂使每個(gè)頂點(diǎn)僅被訪問一次點(diǎn)僅被訪問一次,這個(gè)過程稱為圖的遍歷。這個(gè)過程稱為圖的遍歷。 假設(shè)給定圖是連通的無向圖或者是強(qiáng)連通的有向圖假設(shè)給定圖是連通的無向圖或者是強(qiáng)連通的有向圖,那么遍歷過程一次就能完成那么遍歷

23、過程一次就能完成,并可按訪問的先后順序得到并可按訪問的先后順序得到由該圖一切頂點(diǎn)組成的一個(gè)序列。由該圖一切頂點(diǎn)組成的一個(gè)序列。 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v0 v1 v2 v3 v4 DFS序列：序列：21034 1 3 0 2 4 部分合法的部分合法的DFSDFS序列：序列：2 3 0 1 42 3 0 1 4；2 1 0 4 32 1 0 4 3；2 4 3 0 12 4 3 0 1不合法的不合法的DFSDFS序列舉例：序列舉例：2 0 1 3 42 0 1 3 4 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3

24、 4 2 3 4 v0 v1 v2 v3 v4 1 3 0 2 4 部分合法的部分合法的BFSBFS序列：序列：2 1 3 4 0;2 3 1 4 0;2 4 1 3 02 1 3 4 0;2 3 1 4 0;2 4 1 3 0不合法的不合法的BFSBFS序列舉例：序列舉例：2 1 0 3 4 2 1 0 3 4 ；2 3 0 4 12 3 0 4 1但是，假設(shè)對(duì)上圖采用上面的鄰接表存儲(chǔ)但是，假設(shè)對(duì)上圖采用上面的鄰接表存儲(chǔ),假設(shè)假設(shè)初始頂點(diǎn)編號(hào)初始頂點(diǎn)編號(hào)v=2, 進(jìn)展廣度優(yōu)先遍歷的話，序進(jìn)展廣度優(yōu)先遍歷的話，序列就是獨(dú)一的了。此時(shí)的遍歷序列如下：列就是獨(dú)一的了。此時(shí)的遍歷序列如下：BFS序列

25、：序列：21340真題演練真題演練 (1)有有N個(gè)頂點(diǎn)、個(gè)頂點(diǎn)、E條邊且用鄰接表存儲(chǔ)的有向圖條邊且用鄰接表存儲(chǔ)的有向圖進(jìn)展廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是進(jìn)展廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是 A、ON B、OE C、ON+E D、ON*E (2)假設(shè)從無向圖的任一頂點(diǎn)出發(fā)進(jìn)展一次深度優(yōu)假設(shè)從無向圖的任一頂點(diǎn)出發(fā)進(jìn)展一次深度優(yōu)先遍歷即可訪問一切頂點(diǎn)，那么該圖一定是先遍歷即可訪問一切頂點(diǎn)，那么該圖一定是 A. 完全圖完全圖 B. 連通圖連通圖 C.有回路有回路 D.一棵樹一棵樹四、圖的運(yùn)用四、圖的運(yùn)用最小生成樹最小生成樹拓?fù)渑判蛲負(fù)渑判蜃疃掏緩阶疃掏緩疥P(guān)鍵途徑關(guān)鍵途徑最小生成樹生成樹的概念生成樹的

26、概念 一個(gè)連通圖的生成樹是一個(gè)極小連通子圖一個(gè)連通圖的生成樹是一個(gè)極小連通子圖,它含有它含有圖中全部頂點(diǎn)圖中全部頂點(diǎn),但只需構(gòu)成一棵樹的但只需構(gòu)成一棵樹的(n-1)條邊。條邊。 命題：假設(shè)在一棵生成樹上添加一條邊命題：假設(shè)在一棵生成樹上添加一條邊,必定構(gòu)成必定構(gòu)成一個(gè)環(huán)。一個(gè)環(huán)。由于這條邊使得它依靠的那兩個(gè)頂點(diǎn)之間有了第由于這條邊使得它依靠的那兩個(gè)頂點(diǎn)之間有了第二條途徑。一棵有二條途徑。一棵有n個(gè)頂點(diǎn)的生成樹個(gè)頂點(diǎn)的生成樹(連通無回路圖連通無回路圖)有有且僅有且僅有(n-1)條邊條邊,假設(shè)一個(gè)圖有假設(shè)一個(gè)圖有n個(gè)頂點(diǎn)和小于個(gè)頂點(diǎn)和小于(n-1)條條邊邊,那么是非連通圖。假設(shè)它多于那么是非連通圖

27、。假設(shè)它多于(n-1)條邊條邊,那么一定有那么一定有回路?；芈?。 但是但是,有有(n-1)條邊的圖不一定都是生成樹。條邊的圖不一定都是生成樹。 由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；由由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。這樣的廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。這樣的生成樹是由遍歷時(shí)訪問過的生成樹是由遍歷時(shí)訪問過的n個(gè)頂點(diǎn)和遍歷時(shí)閱歷的個(gè)頂點(diǎn)和遍歷時(shí)閱歷的n-1條條邊組成。邊組成。 對(duì)于非連通圖對(duì)于非連通圖,每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過的邊一同構(gòu)成一棵生成樹的邊一同構(gòu)成一棵生成樹,各

28、個(gè)連通分量的生成樹組成非連各個(gè)連通分量的生成樹組成非連通圖的生成森林。通圖的生成森林。 0 1 2 3 4 1 0 1 0 0 3 2 3 1 2 4 3 4 2 3 4 v0 v1 v2 v3 v4 1 3 0 2 4 從從1 1號(hào)頂點(diǎn)開場(chǎng)的深度優(yōu)先號(hào)頂點(diǎn)開場(chǎng)的深度優(yōu)先遍歷序列：遍歷序列：1 0 3 2 41 0 3 2 4從從1 1號(hào)頂點(diǎn)開場(chǎng)的深度優(yōu)先號(hào)頂點(diǎn)開場(chǎng)的深度優(yōu)先遍歷序列：遍歷序列：1 0 2 3 41 0 2 3 4 1 3 0 2 4 1 3 0 2 4 普里姆算法普里姆算法 普里姆普里姆(Prim)算法是一種構(gòu)造性算法。算法是一種構(gòu)造性算法。 假設(shè)假設(shè)G=(V,E)是一個(gè)具有

29、是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向個(gè)頂點(diǎn)的帶權(quán)連通無向圖圖,T=(U,TE)是是G的最小生成樹的最小生成樹,其中其中U是是T的頂點(diǎn)集的頂點(diǎn)集,TE是是T的邊集的邊集,那么由那么由G構(gòu)造最小生成樹構(gòu)造最小生成樹T的步驟如下：的步驟如下： (1) 初始化初始化U=v。v到其他頂點(diǎn)的一切邊為候選邊；到其他頂點(diǎn)的一切邊為候選邊； (2) 反復(fù)以下步驟反復(fù)以下步驟n-1次次,使得其他使得其他n-1個(gè)頂點(diǎn)被參與到個(gè)頂點(diǎn)被參與到U中：中： 從候選邊中挑選權(quán)值最小的邊輸出從候選邊中挑選權(quán)值最小的邊輸出,設(shè)該邊在設(shè)該邊在V-U中的中的頂點(diǎn)是頂點(diǎn)是k,將將k參與參與U中中,刪除和刪除和k關(guān)聯(lián)的邊；關(guān)聯(lián)的邊； 調(diào)查當(dāng)

30、前調(diào)查當(dāng)前V-U中的一切頂點(diǎn)中的一切頂點(diǎn)vi,修正候選邊：假設(shè)修正候選邊：假設(shè)(vk,vi)的權(quán)值小于原來和的權(quán)值小于原來和vi關(guān)聯(lián)的候選邊關(guān)聯(lián)的候選邊,那么用那么用(vk,vi)取代后者作為取代后者作為候選邊。候選邊。普里姆算法過程：普里姆算法過程：vkUVUkiUVUv01234651951418271682131270432165148531621 012 34 56closestlowcost1918140000000001648412403337213 025 000U V-U(i, closesti)iU，closestiVU候選邊候選邊 ：8.4.5 克魯斯卡爾算法克魯斯卡爾算法

31、 克魯斯卡爾克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增次算法是一種按權(quán)值的遞增次序選擇適宜的邊來構(gòu)造最小生成樹的方法。假設(shè)序選擇適宜的邊來構(gòu)造最小生成樹的方法。假設(shè)G=(V,E)是一個(gè)具有是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向個(gè)頂點(diǎn)的帶權(quán)連通無向圖圖,T=(U,TE)是是G的最小生成樹。的最小生成樹。 (1) 置置U的初值等于的初值等于V(即包含有即包含有G中的全部頂點(diǎn)中的全部頂點(diǎn)),TE的初的初值為空集值為空集(即圖即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量)。 (2) 將圖將圖G中的邊按權(quán)值從小到大的順序依次選取：假設(shè)中的邊按權(quán)值從小到大的順序依次選?。杭僭O(shè)選取的邊未使生

32、成樹選取的邊未使生成樹T構(gòu)成回路構(gòu)成回路,那么參與那么參與TE；否那么舍棄；否那么舍棄,直到直到TE中包含中包含(n-1)條邊為止。條邊為止。035214516354652025314NOViVjW10212352314342545035612572358016924610456600331100001901234655141827168213127真題演練真題演練例：以下關(guān)于最小生成樹的表達(dá)中，正確的例：以下關(guān)于最小生成樹的表達(dá)中，正確的選項(xiàng)是選項(xiàng)是 A、最小生成樹的代價(jià)是獨(dú)一的、最小生成樹的代價(jià)是獨(dú)一的B、一切權(quán)值最小的邊一定會(huì)出如今一切的、一切權(quán)值最小的邊一定會(huì)出如今一切的最小生成樹中最

33、小生成樹中C、運(yùn)用普里姆算法從不同頂點(diǎn)開場(chǎng)得到的、運(yùn)用普里姆算法從不同頂點(diǎn)開場(chǎng)得到的最小生成樹一定一樣最小生成樹一定一樣D、運(yùn)用普里姆算法和克魯斯卡爾算法得到、運(yùn)用普里姆算法和克魯斯卡爾算法得到的最小生成樹一定一樣的最小生成樹一定一樣真題演練真題演練知無向網(wǎng)的鄰接矩陣如下圖，要求：知無向網(wǎng)的鄰接矩陣如下圖，要求：1畫出該圖；畫出該圖；2按照克魯斯卡爾算法給出該網(wǎng)的最按照克魯斯卡爾算法給出該網(wǎng)的最小生成樹的過程。小生成樹的過程。 4 3 4 5 6 9 3 5 5 6 6 5 7 6 5 4 9 7 3 4 3 6 3 2 5 2 6 6 4 6 1該無向網(wǎng)如以下圖所示該無向網(wǎng)如以下圖所示0 V

34、11 V22 V33 V44 V55 V66 V77 V8V1V3V8V2V4V5V7V63654623 67953465(2)生成過程如下：生成過程如下：V1V3V8V2V4V5V7V6V1V3V8V2V4V5V7V62V1V3V8V2V4V5V7V623V1V3V8V2V4V5V7V6233V1V3V8V2V4V5V7V62334V1V3V8V2V4V5V7V6233442V1V3V8V2V4V5V7V633445V1V3V8V2V4V5V7V6334455最短途徑最短途徑 對(duì)于帶權(quán)的圖對(duì)于帶權(quán)的圖,思索途徑上各邊上的權(quán)值思索途徑上各邊上的權(quán)值,那么那么通常把一條途徑上所經(jīng)邊的權(quán)值之和定義

35、為該途通常把一條途徑上所經(jīng)邊的權(quán)值之和定義為該途徑的途徑長度或稱帶權(quán)途徑長度。徑的途徑長度或稱帶權(quán)途徑長度。 從源點(diǎn)到終點(diǎn)能夠不止一條途徑從源點(diǎn)到終點(diǎn)能夠不止一條途徑,把帶權(quán)途徑把帶權(quán)途徑長度最短的那條途徑稱為最短途徑長度最短的那條途徑稱為最短途徑,其途徑長度其途徑長度(權(quán)值之和權(quán)值之和)稱為最短途徑長度或者最短間隔。稱為最短途徑長度或者最短間隔。從一個(gè)頂點(diǎn)到其他各頂點(diǎn)的最短途徑從一個(gè)頂點(diǎn)到其他各頂點(diǎn)的最短途徑 問題：給定一個(gè)帶權(quán)有向圖問題：給定一個(gè)帶權(quán)有向圖G與源點(diǎn)與源點(diǎn)v,求從求從v到到G中其他頂點(diǎn)的最短途徑中其他頂點(diǎn)的最短途徑,并限定各邊上的權(quán)值并限定各邊上的權(quán)值大于或等于大于或等于0。

36、 采用狄克斯特拉采用狄克斯特拉(Dijkstra)算法求解算法求解 根本思想是：設(shè)根本思想是：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖是一個(gè)帶權(quán)有向圖, 把圖中頂點(diǎn)集合把圖中頂點(diǎn)集合V分成兩組：分成兩組： 第一組為已求出最短途徑的頂點(diǎn)集合第一組為已求出最短途徑的頂點(diǎn)集合(用用S表示表示,初始時(shí)初始時(shí)S中只中只需一個(gè)源點(diǎn)需一個(gè)源點(diǎn),以后每求得一條最短途徑以后每求得一條最短途徑v,vk,就將就將vk參與到集合參與到集合S中中,直到全部頂點(diǎn)都參與到直到全部頂點(diǎn)都參與到S中中,算法就終了了算法就終了了) 第二組為其他未確定最短途徑的頂點(diǎn)集合第二組為其他未確定最短途徑的頂點(diǎn)集合(用用U表示表示)。 按最短途徑長

37、度的遞增次序依次把第二組的頂點(diǎn)參與按最短途徑長度的遞增次序依次把第二組的頂點(diǎn)參與S中。在參與的過程中中。在參與的過程中,總堅(jiān)持從源點(diǎn)總堅(jiān)持從源點(diǎn)v到到S中各頂點(diǎn)的最短中各頂點(diǎn)的最短途徑長度不大于從源點(diǎn)途徑長度不大于從源點(diǎn)v到到U中任何頂點(diǎn)的最短途徑長度。中任何頂點(diǎn)的最短途徑長度。 此外此外,每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)間隔每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)間隔,S中的頂點(diǎn)的間隔就是從中的頂點(diǎn)的間隔就是從v到此頂點(diǎn)的最短途徑長度到此頂點(diǎn)的最短途徑長度,U中的頂點(diǎn)的間隔從中的頂點(diǎn)的間隔從v到此頂點(diǎn)到此頂點(diǎn)只包括只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短途徑長度。中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短途徑長度。 (1) 初始時(shí)初始時(shí),S只包含源

38、點(diǎn)只包含源點(diǎn),即即S=v,v的間隔為的間隔為0。U包含除包含除v外的外的其他頂點(diǎn)其他頂點(diǎn),U中頂點(diǎn)中頂點(diǎn)u間隔為邊上的權(quán)間隔為邊上的權(quán)(假設(shè)假設(shè)v與與u有邊有邊)或或(假假設(shè)設(shè)u不是不是v的出邊鄰接點(diǎn)的出邊鄰接點(diǎn))。即圖的鄰接矩陣中。即圖的鄰接矩陣中v所在的行元素值。所在的行元素值。 (2) 從從U中選取一個(gè)間隔中選取一個(gè)間隔v最小的頂點(diǎn)最小的頂點(diǎn)k,把把k參與參與S中中(該選定的該選定的間隔就是間隔就是v到到k的最短途徑長度的最短途徑長度)。 (3) 以以k為新思索的中間點(diǎn)為新思索的中間點(diǎn),修正修正U中各頂點(diǎn)的間隔：假設(shè)從源中各頂點(diǎn)的間隔：假設(shè)從源點(diǎn)點(diǎn)v到頂點(diǎn)到頂點(diǎn)u(uU)的間隔的間隔(經(jīng)

39、過頂點(diǎn)經(jīng)過頂點(diǎn)k)比原來間隔比原來間隔(不經(jīng)過頂點(diǎn)不經(jīng)過頂點(diǎn)k)短短,那么修正頂點(diǎn)那么修正頂點(diǎn)u的間隔值的間隔值,修正后的間隔值為頂點(diǎn)修正后的間隔值為頂點(diǎn)k的間隔加上的間隔加上邊邊上的權(quán)。上的權(quán)。 (4) 反復(fù)步驟反復(fù)步驟(2)和和(3)直到一切頂點(diǎn)都包含在直到一切頂點(diǎn)都包含在S中。中。狄克斯特拉算法的過程狄克斯特拉算法的過程 v j k cvk wkj cvj 頂點(diǎn)頂點(diǎn)V到到j(luò)的最小間隔的最小間隔MIN(cvk+wkj,cvj) 1 4 0 2 6 3 5 8 1 6 6 4 2 5 6 6 1 4 7 S U dist 0 1 2 3 4 5 60 1,2,3,4,5,6 0,4,6,6,

40、 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,170,1,2,3,5,4 6 0,4,5,6,10,9,160,1,2,3,5,4,6 0,4,5,6,10,9,16 path 0 1 2 3 4 5 60,0,0,0,-1,-1,-1 0,0,1,0, 1,-1,-10,0,1,0, 1, 2,-10,0,1,0, 1, 2,-10,0,1,0, 5, 2, 50,0,1,0, 5, 2, 40,0,1,0, 5, 2,

41、4438164256147660123456distpath004660000040115 59691017115251016416562018.5.3 每對(duì)頂點(diǎn)之間的最短途徑每對(duì)頂點(diǎn)之間的最短途徑 問題：對(duì)于一個(gè)各邊權(quán)值均大于零的有向圖問題：對(duì)于一個(gè)各邊權(quán)值均大于零的有向圖,對(duì)對(duì)每一對(duì)頂點(diǎn)每一對(duì)頂點(diǎn)vivj,求出求出vi與與vj之間的最短途徑和最短之間的最短途徑和最短途徑長度。途徑長度。 可以經(jīng)過以每個(gè)頂點(diǎn)作為源點(diǎn)循環(huán)求出每對(duì)頂點(diǎn)可以經(jīng)過以每個(gè)頂點(diǎn)作為源點(diǎn)循環(huán)求出每對(duì)頂點(diǎn)之間的最短途徑。除此之外之間的最短途徑。除此之外,弗洛伊德弗洛伊德(Floyd)算法也算法也可用于求兩頂點(diǎn)之間最短途徑?？?/p>

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

43、=costij。當(dāng)求從頂點(diǎn)。當(dāng)求從頂點(diǎn)vi到頂點(diǎn)到頂點(diǎn)vj的途的途徑上所經(jīng)過的頂點(diǎn)編號(hào)不大于徑上所經(jīng)過的頂點(diǎn)編號(hào)不大于k+1的最短途徑長度時(shí)的最短途徑長度時(shí),要分兩種要分兩種情況思索：情況思索： 一種情況是該途徑不經(jīng)過頂點(diǎn)編號(hào)為一種情況是該途徑不經(jīng)過頂點(diǎn)編號(hào)為k+1的頂點(diǎn)的頂點(diǎn),此時(shí)該途此時(shí)該途徑長度與從頂點(diǎn)徑長度與從頂點(diǎn)vi到頂點(diǎn)到頂點(diǎn)vj的途徑上所經(jīng)過的頂點(diǎn)編號(hào)不大于的途徑上所經(jīng)過的頂點(diǎn)編號(hào)不大于k的最短途徑長度一樣；的最短途徑長度一樣； 另一種情況是從頂點(diǎn)另一種情況是從頂點(diǎn)vi到頂點(diǎn)到頂點(diǎn)vj的最短途徑上經(jīng)過編號(hào)為的最短途徑上經(jīng)過編號(hào)為k+1的頂點(diǎn)。的頂點(diǎn)。 i j k+1 Aki,k+

44、1 Akk+1,j Aki,j Ak+1i,j=MIN(Aki,j,Aki,k+1+Akk+1,j) 那么那么,該途徑可分為兩段該途徑可分為兩段: (1) 從頂點(diǎn)從頂點(diǎn)vi到頂點(diǎn)到頂點(diǎn)vk+1的最短途徑的最短途徑; (2) 從頂點(diǎn)從頂點(diǎn)vk+1到頂點(diǎn)到頂點(diǎn)vj的最短途徑。的最短途徑。 此時(shí)最短途徑長度等于這兩段途徑長度之和。這兩種情此時(shí)最短途徑長度等于這兩段途徑長度之和。這兩種情況中的較小值況中的較小值,就是所要求的從頂點(diǎn)就是所要求的從頂點(diǎn)vi到頂點(diǎn)到頂點(diǎn)vj的途徑上所經(jīng)的途徑上所經(jīng)過的頂點(diǎn)編號(hào)不大于過的頂點(diǎn)編號(hào)不大于k+1的最短途徑。的最短途徑。 弗洛伊德思想可用如下的表達(dá)式來描畫：弗洛伊德

45、思想可用如下的表達(dá)式來描畫： A-1ij=costij Ak+1ij=MIN Akij, Akik+1+Akk+1j (0kn-1)012033240750 0120332407501A1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1Path采用弗洛伊德算法求解過程采用弗洛伊德算法求解過程 012353273124 思索頂點(diǎn)思索頂點(diǎn)v0,A0ij表示由表示由vi到到vj,經(jīng)由頂點(diǎn)經(jīng)由頂點(diǎn)v0的最短途徑。的最短途徑。v2-v0-v1：不改動(dòng)。：不改動(dòng)。v2-v0-v3：不改動(dòng)。：不改動(dòng)。0120332407500A1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-

46、0Path012353273124 思索頂點(diǎn)思索頂點(diǎn)v1,A1ij表示由表示由vi到到vj,經(jīng)由頂點(diǎn)經(jīng)由頂點(diǎn)v1的最短途徑。的最短途徑。v0-v1-v2,途徑長度為途徑長度為9,將將A02改為改為9。path02改為改為1。 01203324079501A1-1-1-1-1-1-1-1-1-1-1-1-1-11-1-1Path012353273124 思索頂點(diǎn)思索頂點(diǎn)v2,A2ij表示由表示由vi到到vj,經(jīng)由頂點(diǎn)經(jīng)由頂點(diǎn)v2的最短途徑。的最短途徑。v3-v2-v0,長度為長度為4,將將A30改為改為4；v3-v2-v1,長度為長度為4,將將A31改為改為4。v1-v2-v0,長度為長度為7,

47、將將A10改為改為7。將將path30、path31和和path10均改為均改為2。因此。因此,有：有： 01442033240779502A1-1-221-1-1-1-1-1-1-21-11-1-2Path012353273124 思索頂點(diǎn)思索頂點(diǎn)v3,A3ij表示由表示由vi到到vj,經(jīng)由頂點(diǎn)經(jīng)由頂點(diǎn)v3的最短途徑。的最短途徑。 v0-v3-v2：長度為：長度為8,A02改為改為8； v1-v3-v2-v0,長度為長度為6,A10改為改為6； v1-v3-v2,長度為長度為3, A12改為改為3。將將path02、path10后后path12均改為均改為3。 014420332306785

48、03A1-1-221-1-1-1-1-31-31-31-1-3Path0123532731240144203323067850從從0到到0途徑為：途徑為：0,0途徑長度為：途徑長度為：0從從0到到1途徑為：途徑為：0,1途徑長度為：途徑長度為：5從從0到到2途徑為：途徑為：0,3,2途徑長度為：途徑長度為：8從從0到到3途徑為：途徑為：0,3途徑長度為：途徑長度為：7從從1到到0途徑為：途徑為：1,3,2,0途徑長度為：途徑長度為：6從從1到到1途徑為：途徑為：1,1途徑長度為：途徑長度為：0從從1到到2途徑為：途徑為：1,3,2 途徑長度為：途徑長度為：3從從1到到3途徑為：途徑為：1,3途

49、徑長度為：途徑長度為：21-1-221-1-1-1-1-31-31-31-1-A=Path=從從2到到0途徑為：途徑為：2,0途徑長度為：途徑長度為：3從從2到到1途徑為：途徑為：2,1途徑長度為：途徑長度為：3從從2到到2途徑為：途徑為：2,2途徑長度為：途徑長度為：0從從2到到3途徑為：途徑為：2,3途徑長度為：途徑長度為：2從從3到到0途徑為：途徑為：3,2,0 途徑長度為：途徑長度為：4從從3到到1途徑為：途徑為：3,2,1 途徑長度為：途徑長度為：4從從3到到2途徑為：途徑為：3,2途徑長度為：途徑長度為：1從從3到到3途徑為：途徑為：3,3途徑長度為：途徑長度為：0拓樸排序拓樸排序

50、設(shè)設(shè)G=(V,E)是一個(gè)具有是一個(gè)具有n個(gè)頂點(diǎn)的有向圖個(gè)頂點(diǎn)的有向圖,V中頂點(diǎn)序列中頂點(diǎn)序列v1,v2,vn稱為一個(gè)拓?fù)湫蛄蟹Q為一個(gè)拓?fù)湫蛄?當(dāng)且僅當(dāng)該頂點(diǎn)序列滿當(dāng)且僅當(dāng)該頂點(diǎn)序列滿足以下條件：足以下條件： 假設(shè)假設(shè)是圖中的邊是圖中的邊(即從頂點(diǎn)即從頂點(diǎn)vi到到vj有一條途有一條途徑徑),那么在序列中頂點(diǎn)那么在序列中頂點(diǎn)vi必需排在頂點(diǎn)必需排在頂點(diǎn)vj之前。之前。 在一個(gè)有向圖中找一個(gè)拓?fù)湫蛄械倪^程稱為拓?fù)湓谝粋€(gè)有向圖中找一個(gè)拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。排序?(1) 從有向圖中選擇一個(gè)沒有前驅(qū)從有向圖中選擇一個(gè)沒有前驅(qū)(即入度為即入度為0)的頂點(diǎn)的頂點(diǎn)并且輸出它。并且輸出它。 (2) 從網(wǎng)中

51、刪去該頂點(diǎn)從網(wǎng)中刪去該頂點(diǎn),并且刪去從該頂點(diǎn)發(fā)出的全部并且刪去從該頂點(diǎn)發(fā)出的全部有向邊。有向邊。 (3) 反復(fù)上述兩步反復(fù)上述兩步,直到剩余的網(wǎng)中不再存在沒有前驅(qū)直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點(diǎn)為止。的頂點(diǎn)為止。拓?fù)渑判虿襟E拓?fù)渑判虿襟E0 0 12 4 5 3 0 12 4 5 3 41253全部能夠的拓?fù)渑判蛐蛄校?41253 041523 045123450123 401253 405123 401523關(guān)鍵途徑關(guān)鍵途徑 假設(shè)用帶權(quán)有向圖假設(shè)用帶權(quán)有向圖(DAG)描畫工程的估計(jì)進(jìn)度描畫工程的估計(jì)進(jìn)度,以以頂點(diǎn)表示事件頂點(diǎn)表示事件,有向邊表示活動(dòng)有向邊表示活動(dòng),邊邊e的權(quán)的權(quán)c(e)表示

52、完成活表示完成活動(dòng)動(dòng)e所需的時(shí)間所需的時(shí)間(比如天數(shù)比如天數(shù)),或者說活動(dòng)或者說活動(dòng)e繼續(xù)時(shí)間。繼續(xù)時(shí)間。 圖中入度為圖中入度為0的頂點(diǎn)源點(diǎn)的開場(chǎng)事件的頂點(diǎn)源點(diǎn)的開場(chǎng)事件(如開工儀如開工儀式式),出度為出度為0的頂點(diǎn)匯點(diǎn)表示工程終了事件。那么稱的頂點(diǎn)匯點(diǎn)表示工程終了事件。那么稱這樣的有向圖為這樣的有向圖為AOE網(wǎng)網(wǎng)(Activity On Edge)。 v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2 一個(gè)一個(gè)AOE網(wǎng)網(wǎng)源點(diǎn)源點(diǎn)匯點(diǎn)匯點(diǎn) 幾個(gè)定義： (1) 事件v的最早可發(fā)生時(shí)間：假設(shè)事件x是源點(diǎn)

53、,事件y為匯點(diǎn),并規(guī)定事件x的發(fā)生時(shí)間為0。定義圖中任一事件v的最早(event early)可發(fā)生時(shí)間ve(v)等于x到v一切途徑長度的最大值,即： ve(v)= )p( cMAXp 上式中的上式中的MAX是對(duì)是對(duì)x到到v的一切途徑的一切途徑p取最大值取最大值,c(p)表示途表示途徑徑p的長度的長度(途徑上邊長之和途徑上邊長之和) ,即：即：c(p)= )e ( cpe 完成整個(gè)工程所需的最少時(shí)間完成整個(gè)工程所需的最少時(shí)間,等于事件等于事件y的最早的最早可發(fā)生時(shí)間可發(fā)生時(shí)間ve(y)。 v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6

54、a10=11a12=5a8=4a11=2 源點(diǎn)源點(diǎn)匯點(diǎn)匯點(diǎn) 整個(gè)工程完成的最短時(shí)間指的是：從有向圖的源點(diǎn)到匯點(diǎn)的整個(gè)工程完成的最短時(shí)間指的是：從有向圖的源點(diǎn)到匯點(diǎn)的最長途徑的長度，具有最大長度的途徑叫關(guān)鍵途徑。最長途徑的長度，具有最大長度的途徑叫關(guān)鍵途徑。 “關(guān)鍵活動(dòng)指的是：該弧上的權(quán)值添加將使有向圖上的最關(guān)鍵活動(dòng)指的是：該弧上的權(quán)值添加將使有向圖上的最長途徑的長度添加。長途徑的長度添加。 留意：在一個(gè)留意：在一個(gè)AOEAOE網(wǎng)中，可以有不止一條的關(guān)鍵途徑。網(wǎng)中，可以有不止一條的關(guān)鍵途徑。 v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=

55、6a10=11a12=5a8=4a11=2 源點(diǎn)源點(diǎn)匯點(diǎn)匯點(diǎn) (2) 事件事件v的最遲可發(fā)生時(shí)間：定義在不影響整個(gè)工程進(jìn)度的最遲可發(fā)生時(shí)間：定義在不影響整個(gè)工程進(jìn)度的前提下的前提下,事件事件v必需發(fā)生的時(shí)間稱為必需發(fā)生的時(shí)間稱為v的最遲的最遲(event late)可發(fā)生可發(fā)生時(shí)間時(shí)間,記作記作vl(v)。vl(v)應(yīng)等于應(yīng)等于ve(y)與與v到到y(tǒng)的最長途徑長度之差的最長途徑長度之差(y是匯點(diǎn)是匯點(diǎn)),即：即： vl(v)=ve(y) - )p( cMAXp (3) 關(guān)鍵活動(dòng)關(guān)鍵活動(dòng):假設(shè)活動(dòng)假設(shè)活動(dòng)v滿足滿足ve(v)+c(ai)=vl(w),那么稱活動(dòng)那么稱活動(dòng)ai為關(guān)鍵活動(dòng)，為關(guān)鍵活動(dòng)

56、，ai=。 對(duì)關(guān)鍵活動(dòng)來說對(duì)關(guān)鍵活動(dòng)來說,不存在富余時(shí)間。顯然不存在富余時(shí)間。顯然,關(guān)鍵途徑上的活動(dòng)關(guān)鍵途徑上的活動(dòng)都是關(guān)鍵活動(dòng)。找出關(guān)鍵活動(dòng)的意義在于都是關(guān)鍵活動(dòng)。找出關(guān)鍵活動(dòng)的意義在于,可以適當(dāng)?shù)靥砑訉?duì)可以適當(dāng)?shù)靥砑訉?duì)關(guān)鍵活動(dòng)的投資關(guān)鍵活動(dòng)的投資(人力、物力等人力、物力等),相應(yīng)地減少對(duì)非關(guān)鍵活動(dòng)的投相應(yīng)地減少對(duì)非關(guān)鍵活動(dòng)的投資資,從而減少關(guān)鍵活動(dòng)的繼續(xù)時(shí)間從而減少關(guān)鍵活動(dòng)的繼續(xù)時(shí)間,縮短整個(gè)工程的工期?？s短整個(gè)工程的工期。 ve(v)最早開始時(shí)間ve(v)最遲開始時(shí)間v000v139v21010v31223v42222v51717v62031v72828v83333 只需計(jì)算出各項(xiàng)點(diǎn)的只

57、需計(jì)算出各項(xiàng)點(diǎn)的ve(v)和和vl(v)的值的值,就能找出一切的關(guān)就能找出一切的關(guān)鍵活動(dòng)。為了便于計(jì)算鍵活動(dòng)。為了便于計(jì)算,引入下面兩個(gè)遞推式引入下面兩個(gè)遞推式,其中其中,x和和y分別分別是源點(diǎn)和匯點(diǎn)。是源點(diǎn)和匯點(diǎn)。 ve(x)=0 ve(w)= wx上式中的上式中的MAX對(duì)一切射入對(duì)一切射入w的邊的邊取最大值。取最大值。 vl(y)=0 vl(v)= vy)w, v( c)v(veMAXvw, v邊的所有存在)w, v( c)w(vlMINww, v邊的所有存在 (1) 對(duì)于源點(diǎn)對(duì)于源點(diǎn)x,置置ve(x)=0； (2) 對(duì)對(duì)AOE網(wǎng)進(jìn)展拓?fù)渑判?。如發(fā)現(xiàn)回路網(wǎng)進(jìn)展拓?fù)渑判颉Ｈ绨l(fā)現(xiàn)回路,工程無法

58、進(jìn)展工程無法進(jìn)展,那么那么退出；否那么繼續(xù)下一步。退出；否那么繼續(xù)下一步。 (3) 按頂點(diǎn)的拓?fù)浯涡虬错旤c(diǎn)的拓?fù)浯涡?反復(fù)用式反復(fù)用式8.4,依次求其他各項(xiàng)點(diǎn)依次求其他各項(xiàng)點(diǎn)v的的ve(v)值。值。(實(shí)踐上實(shí)踐上,步驟步驟(2)和步驟和步驟(3)可以合在一同完成可以合在一同完成,即一邊對(duì)頂點(diǎn)即一邊對(duì)頂點(diǎn)進(jìn)展拓?fù)渑判蜻M(jìn)展拓?fù)渑判?一邊求出各點(diǎn)的一邊求出各點(diǎn)的ve(v)之值。之值。) (4) 對(duì)于匯點(diǎn)對(duì)于匯點(diǎn)y,置置vl(y)=ve(y)； 求AOE網(wǎng)的關(guān)鍵活動(dòng)的過程 (5) 按頂點(diǎn)拓?fù)浯涡蛑嫘虬错旤c(diǎn)拓?fù)浯涡蛑嫘?反復(fù)用式反復(fù)用式8.5,依次求其他各項(xiàng)點(diǎn)依次求其他各項(xiàng)點(diǎn)v的的vl(v)的值。即對(duì)的值。即對(duì)v射出的一切邊射出的一切邊,檢查能否滿足式檢查能否滿足式8.3,假設(shè)是假設(shè)是,那么輸出該邊的有關(guān)信息那么輸出該邊的有關(guān)信息,指明該邊所對(duì)應(yīng)的活動(dòng)是關(guān)鍵活動(dòng)。指明該邊所對(duì)應(yīng)的活動(dòng)是關(guān)鍵活動(dòng)。 (6) 活動(dòng)活動(dòng)ai的最早開場(chǎng)時(shí)間的最早開場(chǎng)時(shí)間e(i)是該活動(dòng)的起點(diǎn)所表示的事件最是該活動(dòng)的起點(diǎn)所表示的事件最早發(fā)