數(shù)據(jù)結(jié)構(gòu)（從概念到算法）課件

第6章圖01020304目錄CONTENTS05圖的基本概念圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷圖的生成樹(shù)問(wèn)題圖的最短路徑問(wèn)題06有向無(wú)環(huán)圖的應(yīng)用07應(yīng)用實(shí)例08本章小結(jié)01PART圖的基本概念6.1.1圖的定義與基本術(shù)語(yǔ)一個(gè)圖G

可以定義為集合V

和VR

構(gòu)成的二元組，記為G=(V,VR)。其中

V

是具有相同特征數(shù)據(jù)元素的非空集合，在圖中數(shù)據(jù)元素通常稱為頂點(diǎn)（Vertex），因此

V

稱為頂點(diǎn)集；VR

是頂點(diǎn)之間的關(guān)系集。有向圖（Directed

Graph）。如果頂點(diǎn)間的關(guān)系是有序?qū)?，且可表示?lt;a,b>∈VR，則該有序?qū)Ρ硎緩捻旤c(diǎn)

a

到頂點(diǎn)

b

有一條?。ˋrc）。這里

a是弧的初始點(diǎn)，簡(jiǎn)稱弧尾；b是弧的終端點(diǎn)，簡(jiǎn)稱弧頭。此時(shí)，由頂點(diǎn)集合和弧集合組成的圖稱為有向圖。例如，當(dāng)V={v1,v2,v3,v4,v5}，VR={<v1,v2>,<v1,v4>,<v2,v4>,<v3,v1>,<v3,v5>,<v4,v3>,<v5,v4>}，則頂點(diǎn)集合V、關(guān)系集合VR構(gòu)成有向圖G1=(V,VR)，如圖

（a）所示。圖的基本概念6.1.1圖的定義與基本術(shù)語(yǔ)無(wú)向圖（Undirected

Graph）。如果頂點(diǎn)間的關(guān)系是無(wú)序?qū)?，且可表示?a,b)∈VR，則該無(wú)序?qū)Ρ硎卷旤c(diǎn)

a

與頂點(diǎn)

b

的一條邊（Edge）。此時(shí)，由頂點(diǎn)集合和邊的集合組成的圖稱為無(wú)向圖。圖（b）所示為無(wú)向圖G2。在無(wú)向圖中，如果頂點(diǎn)

vi和

vj有邊，就稱

vi和

vj互為鄰接頂點(diǎn)（Adjacent）；該邊依附于頂點(diǎn)vi和vj，或者說(shuō)該邊與vi和vj相關(guān)聯(lián)。圖的基本概念6.1.1圖的定義與基本術(shù)語(yǔ)完全圖（Completed

Graph）。習(xí)慣上，用

n

表示頂點(diǎn)的數(shù)量，e

表示邊或弧的數(shù)量。對(duì)一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖，e的取值范圍為0～n(n-1)/2。如果任意兩個(gè)頂點(diǎn)間都有邊，則e可以達(dá)到最大值，一共有n(n-1)/2條邊，這樣的無(wú)向圖稱為完全圖。有向完全圖。對(duì)一個(gè)有n個(gè)頂點(diǎn)的有向圖，e的取值范圍為0～n(n-1)。如果有向圖中的任意兩個(gè)頂點(diǎn)vi和

vj之間有弧（從

vi到

vj有弧，同時(shí)從vj到

vi也有弧），則一共有n(n-1)條弧，這樣的有向圖稱為有向完全圖。如果圖中的邊或弧的數(shù)量很少，例如e<nlogn，稱這類圖為稀疏圖，否則稱為稠密圖。圖的基本概念6.1.1圖的定義與基本術(shù)語(yǔ)有向網(wǎng)、無(wú)向網(wǎng)。有時(shí)，在邊或弧上標(biāo)注權(quán)值可以表示頂點(diǎn)間的距離、時(shí)間或費(fèi)用等各種開(kāi)銷，稱這樣的圖為網(wǎng)（Network）。稱帶權(quán)值的有向圖為有向網(wǎng)，稱帶權(quán)值的無(wú)向圖為無(wú)向網(wǎng)，如下圖所示。這樣總共就有了4種類型的圖：有向圖、有向網(wǎng)、無(wú)向圖和無(wú)向網(wǎng)。圖的基本概念6.1.1圖的定義與基本術(shù)語(yǔ)頂點(diǎn)的度（Degree）。與頂點(diǎn)

v

相關(guān)聯(lián)邊或弧的數(shù)量稱為頂點(diǎn)

v

的度，記為

TD(v)或

D(v)。求頂點(diǎn)的度需要區(qū)分無(wú)向圖與有向圖。在一個(gè)無(wú)向圖中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)量稱為頂點(diǎn)的度，無(wú)向圖某個(gè)頂點(diǎn)的度表示該頂點(diǎn)的鄰接頂點(diǎn)數(shù)量。在一個(gè)有向圖中，一個(gè)頂點(diǎn)v的度是由出度（Outdegree）和入度（Indegree）組成的，分別記為OD(v)和ID(v)。頂點(diǎn)v的出度等于以v作為弧尾的弧的數(shù)量，入度等于以v作為弧頭的弧的數(shù)量。子圖（Subgraph）。對(duì)于兩個(gè)圖

G=(V,VR)和

G'=(V

',VR')，如果

V

'í

V

且

VR'í

VR，則稱

G'是

G的一個(gè)子圖。圖的基本概念6.1.1圖的定義與基本術(shù)語(yǔ)路徑（Path）。頂點(diǎn)vi到vj有路徑是指存在頂點(diǎn)序列vi,vi1,vi2,…,vik,vj，其中(vi,vi1)、(vi1,vi2)……(vik,vj)是圖的邊或<vi,vi1>、<vi1,vi2>……<vik,vj>是圖的弧。稱第一個(gè)和最后一個(gè)頂點(diǎn)相同的路徑為回路或環(huán)（Cycle）；無(wú)重復(fù)頂點(diǎn)的路徑為簡(jiǎn)單路徑。對(duì)于無(wú)向圖，如果頂點(diǎn)

vi到

vj有路徑，則頂點(diǎn)vi和vj是連通的。路徑長(zhǎng)度（Path

Length）。對(duì)于有向圖和無(wú)向圖，路徑長(zhǎng)度是指路徑上包含的邊或弧的條數(shù)；對(duì)于有向網(wǎng)和無(wú)向網(wǎng)，路徑長(zhǎng)度是指路徑上包含的邊或弧上的權(quán)值之和。連通圖（Connected

Graph）。對(duì)于無(wú)向圖，如果任意兩個(gè)頂點(diǎn)

vi到

vj都有路徑，即頂點(diǎn)

vi

和vj是連通的，則稱該圖為連通圖。圖的基本概念6.1.1圖的定義與基本術(shù)語(yǔ)連通分量（ConnectedComponent）。連通分量是指無(wú)向圖中的極大連通子圖。連通圖的連通分量就是其自己，非連通圖會(huì)有多個(gè)連通分量。強(qiáng)連通圖（Strongly

Connected

Graph）。對(duì)于有向圖，如果任意兩個(gè)頂點(diǎn)

vi和

vj都滿足

vi到

vj有路徑，同時(shí)頂點(diǎn)vj到vi也有路徑，則稱該有向圖為強(qiáng)連通圖。強(qiáng)連通分量（Strongly

Connected

Components）。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。強(qiáng)連通圖的強(qiáng)連通分量就是其自己，非強(qiáng)連通圖會(huì)有多個(gè)強(qiáng)連通分量。生成樹(shù)、生成森林。一個(gè)連通圖的極小連通子圖稱為生成樹(shù)（SpanTree），生成樹(shù)是一個(gè)包含圖的n個(gè)頂點(diǎn)和n-1條邊的連通子圖，這里n為圖的頂點(diǎn)數(shù)。如果是非連通圖，則每個(gè)連通分量可以得到一棵連通分量的生成樹(shù)，合在一起就是該

非連通圖的生成森林。圖的基本概念6.1.2圖的操作定義02PART圖的存儲(chǔ)結(jié)構(gòu)6.2.1鄰接矩陣首先介紹的是數(shù)組表示法，即用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)的信息和頂點(diǎn)之間的關(guān)系。用來(lái)存放圖中n

個(gè)頂點(diǎn)的數(shù)組稱為頂點(diǎn)數(shù)組。我們可將圖中頂點(diǎn)按任意順序保存到頂點(diǎn)數(shù)組中，這樣按存放次序每個(gè)頂點(diǎn)就對(duì)應(yīng)一個(gè)位置序號(hào)（簡(jiǎn)稱位序），依次為0～n-1；接著用一個(gè)n×n的二維數(shù)組（稱為鄰接矩陣）來(lái)表示頂點(diǎn)間的關(guān)系，用1

表示頂點(diǎn)間有關(guān)系、0

表示沒(méi)有關(guān)系，如果頂點(diǎn)序號(hào)為

i

的頂點(diǎn)（用

vi表示）和頂點(diǎn)序號(hào)為

j

的頂點(diǎn)（用

vj表示）（0≤i，j≤n-1，i≠j）有關(guān)系，則鄰接矩陣的第i行第j列為1，否則為0。習(xí)慣上，稱數(shù)組表示法為鄰接矩陣表示法（簡(jiǎn)稱鄰接矩陣）。下圖所示為有向圖G1和無(wú)向圖G2的鄰接矩陣。圖的存儲(chǔ)結(jié)構(gòu)6.2.1鄰接矩陣對(duì)于有向網(wǎng)和無(wú)向網(wǎng)而言，需要在鄰接矩陣中加上關(guān)系的權(quán)值。如果兩個(gè)頂點(diǎn)間有鄰接關(guān)系，就用權(quán)值代替原來(lái)的1，否則就用∞代替0。有向網(wǎng)或無(wú)向網(wǎng)的鄰接矩陣也稱為代價(jià)矩陣。下圖所示為有向網(wǎng)G3和無(wú)向網(wǎng)G4的鄰接矩陣。

圖的存儲(chǔ)結(jié)構(gòu)6.2.1鄰接矩陣

下面為圖數(shù)組表示法的數(shù)據(jù)類型MGraph。圖的存儲(chǔ)結(jié)構(gòu)6.2.2鄰接表圖的第二種存儲(chǔ)結(jié)構(gòu)是鄰接表。這是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)組合而成的存儲(chǔ)結(jié)構(gòu)，其通過(guò)頭結(jié)點(diǎn)數(shù)組保存所有的頂點(diǎn)信息，用單鏈表保存頂點(diǎn)之間的關(guān)系。對(duì)于一個(gè)無(wú)向圖G，首先需要一個(gè)頭結(jié)點(diǎn)數(shù)組來(lái)保存所有頂點(diǎn)，這樣每個(gè)頂點(diǎn)都對(duì)應(yīng)一個(gè)0～n-1范圍內(nèi)的位置序號(hào)，這里n表示頂點(diǎn)數(shù)。頭結(jié)點(diǎn)數(shù)組中的每個(gè)元素（頭結(jié)點(diǎn)）包含兩個(gè)部分：一個(gè)是頂點(diǎn)的值；另一個(gè)是單鏈表的頭指針，該頭指針指向一個(gè)由所有鄰接頂點(diǎn)的序號(hào)構(gòu)成的單鏈表，每個(gè)單鏈表的表結(jié)點(diǎn)代表一條依附于該頂點(diǎn)的邊。對(duì)于一個(gè)有向圖G，如果頂點(diǎn)vi到頂點(diǎn)vj有一條弧，則第i個(gè)單鏈表中就會(huì)有一個(gè)表結(jié)點(diǎn)，表結(jié)點(diǎn)的值為j，也就是以這條弧的弧頭頂點(diǎn)序號(hào)作為表結(jié)點(diǎn)的值，所以一條弧對(duì)應(yīng)一個(gè)表結(jié)點(diǎn)。右圖為有向圖G1和無(wú)向圖G2的鄰接表表示法存儲(chǔ)示意圖。圖的存儲(chǔ)結(jié)構(gòu)6.2.2鄰接表對(duì)于有向網(wǎng)和無(wú)向網(wǎng)，由于表結(jié)點(diǎn)表示邊或弧，因此需要對(duì)表結(jié)點(diǎn)擴(kuò)充一個(gè)屬性域，表結(jié)點(diǎn)至少包含頂點(diǎn)序號(hào)、權(quán)值和下一表結(jié)點(diǎn)指針3個(gè)屬性，由此構(gòu)成網(wǎng)的鄰接表。對(duì)于有向圖和有向網(wǎng)，除了鄰接表外，還可以使用逆鄰接表作為存儲(chǔ)結(jié)構(gòu)。即如果頂點(diǎn)

vi到頂點(diǎn)

vj有一條弧，則第

j

個(gè)頂點(diǎn)對(duì)應(yīng)的單鏈表中就會(huì)有一個(gè)表結(jié)點(diǎn)，表結(jié)點(diǎn)的值為

i（即弧尾頂點(diǎn)的序號(hào)作為表結(jié)點(diǎn)的值）。下圖為有向網(wǎng)G3的鄰接表和有向圖G1的逆鄰接表。圖的存儲(chǔ)結(jié)構(gòu)6.2.2鄰接表下面給出鄰接表中的表結(jié)點(diǎn)、頭結(jié)點(diǎn)數(shù)組數(shù)據(jù)類型的定義，并進(jìn)一步組合出鄰接表的類型定義。圖的存儲(chǔ)結(jié)構(gòu)6.2.3十字鏈表圖的第三種存儲(chǔ)結(jié)構(gòu)是十字鏈表，這是針對(duì)有向圖設(shè)計(jì)的一種存儲(chǔ)結(jié)構(gòu)?？梢詫⑵淇闯墒青徑颖砼c逆鄰接表的一種結(jié)合。十字鏈表中，用一個(gè)弧結(jié)點(diǎn)表示一條弧。如果vi到vj有弧，則在弧結(jié)點(diǎn)中包括弧尾vi和弧頭vj這兩個(gè)頂點(diǎn)的位置序號(hào)i和j，同時(shí)對(duì)應(yīng)也包含兩個(gè)鏈表指針：一個(gè)指向下一條以vi作為弧尾的弧結(jié)點(diǎn)；另一個(gè)指向下一條以vj作為弧頭的弧結(jié)點(diǎn)。同時(shí)，通過(guò)頂點(diǎn)結(jié)點(diǎn)數(shù)組保存有向圖的頂點(diǎn)信息，每一個(gè)頂點(diǎn)結(jié)點(diǎn)由3個(gè)域組成：一個(gè)是data域，它用來(lái)保存頂點(diǎn)的信息；另外兩個(gè)是單鏈表的頭指針域firstin和firstout，分別指向以該頂點(diǎn)作為弧頭的第一條弧的弧結(jié)點(diǎn)、以該頂點(diǎn)作為弧尾的第一條弧的弧結(jié)點(diǎn)。圖的存儲(chǔ)結(jié)構(gòu)6.2.3十字鏈表下圖所示為有向圖G8及其十字鏈表存儲(chǔ)結(jié)構(gòu)示意圖。以十字鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，弧的增減需要在兩個(gè)單鏈表中同時(shí)進(jìn)行弧結(jié)點(diǎn)的增、刪操作。在十字鏈表中求一個(gè)頂點(diǎn)的度時(shí)，根據(jù)該頂點(diǎn)的firstin這條鏈統(tǒng)計(jì)弧結(jié)點(diǎn)個(gè)數(shù)得到入度，根據(jù)firstout這條鏈統(tǒng)計(jì)弧結(jié)點(diǎn)個(gè)數(shù)得到出度。圖的存儲(chǔ)結(jié)構(gòu)6.2.4鄰接多重表在鄰接多重表中，一條邊只需要一個(gè)表結(jié)點(diǎn)保存。類似于十字鏈表，如果某條邊關(guān)聯(lián)到頂點(diǎn)vi～vj，則對(duì)應(yīng)表結(jié)點(diǎn)中包括這兩個(gè)頂點(diǎn)的序號(hào)i和j，同時(shí)相應(yīng)地也包含兩個(gè)鏈表指針：一個(gè)指向下一個(gè)關(guān)聯(lián)到頂點(diǎn)vi

的邊的表結(jié)點(diǎn)，另一個(gè)指向下一個(gè)關(guān)聯(lián)到頂點(diǎn)vj

的邊的表結(jié)點(diǎn)。為了方便搜索，為表結(jié)點(diǎn)可以增加一個(gè)標(biāo)志域mark。下面給出了按照上述方法所生成無(wú)向圖G2的鄰接多重表。03PART圖的遍歷6.3.1圖的深度優(yōu)先遍歷圖的遍歷是指按照某種規(guī)則對(duì)圖的每一個(gè)頂點(diǎn)訪問(wèn)一次，且僅訪問(wèn)一次。圖通常有兩種遍歷方法，即深度優(yōu)先遍歷與廣度優(yōu)先遍歷。深度優(yōu)先遍歷的思想：類似于樹(shù)的先根遍歷算法，假定從圖中的某個(gè)頂點(diǎn)v1出發(fā)，首先訪問(wèn)出發(fā)點(diǎn)v1，然后選擇一個(gè)未被訪問(wèn)過(guò)的鄰接點(diǎn)v2，以v2作為新的出發(fā)點(diǎn)繼續(xù)深度優(yōu)先搜索，直到所有與v1相連通的頂點(diǎn)（或有向圖中由v1出發(fā)可以到達(dá)的頂點(diǎn)）被訪問(wèn)。如果圖中還有未被訪問(wèn)的頂點(diǎn)，再選擇一個(gè)頂點(diǎn)作為起點(diǎn)進(jìn)行深度優(yōu)先搜索，直至所有圖的頂點(diǎn)被訪問(wèn)。圖的遍歷6.3.1圖的深度優(yōu)先遍歷圖（a）所示為無(wú)向圖G9；從頂點(diǎn)A出發(fā)，遍歷該圖的過(guò)程如圖（b）所示。首先訪問(wèn)A，標(biāo)注一個(gè)數(shù)字序號(hào)①，表示已經(jīng)訪問(wèn)過(guò)該頂點(diǎn)；接著選擇A的一個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)C作為出發(fā)點(diǎn)，訪問(wèn)C，標(biāo)注數(shù)字序號(hào)②；再選擇C的一個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)H作為出發(fā)點(diǎn)，訪問(wèn)H，標(biāo)注數(shù)字序號(hào)③；這時(shí)H

相鄰頂點(diǎn)都訪問(wèn)過(guò)了，順著虛線箭頭方向原路回退到C，C

的4

個(gè)鄰接頂點(diǎn)中還有D

和G沒(méi)有訪問(wèn)，選擇一個(gè)頂點(diǎn)，例如以D

作為新的出發(fā)點(diǎn)，訪問(wèn)D，標(biāo)注數(shù)字序號(hào)④；（a）無(wú)向圖

G9

（b）深度優(yōu)先遍歷圖的遍歷6.3.1圖的深度優(yōu)先遍歷接著到G，訪問(wèn)G，標(biāo)注數(shù)字序號(hào)⑤；G

相鄰頂點(diǎn)都訪問(wèn)過(guò)了，順著虛線箭頭方向回退到D，D

相鄰頂點(diǎn)都訪問(wèn)過(guò)了，順著虛線箭頭方向回退到C，C

相鄰頂點(diǎn)也都訪問(wèn)過(guò)了，順著虛線箭頭方向回退到出發(fā)點(diǎn)A；繼續(xù)選擇A的一個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)B

作為出發(fā)點(diǎn)，以同樣的處理方式依次訪問(wèn)B,E,F

和I，到I

后，I

相鄰頂點(diǎn)都訪問(wèn)過(guò)了，又需要依次回退到F,E,B,A，再一次又回退到起點(diǎn)A，這樣A

的所有鄰接頂點(diǎn)都已訪問(wèn)，并且圖的所有頂點(diǎn)都訪問(wèn)過(guò)了，所以遍歷結(jié)束，得到的遍歷序列為：AàCàHàDàGàBàEàFàI（a）無(wú)向圖

G9

（b）深度優(yōu)先遍歷圖的遍歷6.3.2圖的廣度優(yōu)先遍歷廣度優(yōu)先遍歷的思想：類似于樹(shù)的按層遍歷算法，假定從圖中的某個(gè)頂點(diǎn)v出發(fā)，首先訪問(wèn)出發(fā)頂點(diǎn)v，然后依次訪問(wèn)v的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，并記住這個(gè)訪問(wèn)次序；在后續(xù)訪問(wèn)過(guò)程中，使得“先被訪問(wèn)過(guò)的頂點(diǎn)的鄰接頂點(diǎn)”先于“后被訪問(wèn)過(guò)的頂點(diǎn)的鄰接頂點(diǎn)”被訪問(wèn)，直到所有與v相連通的頂點(diǎn)被訪問(wèn)。如果圖中還有未被訪問(wèn)的頂點(diǎn)，再選擇一個(gè)頂點(diǎn)作為起點(diǎn)進(jìn)行廣度優(yōu)先搜索，直至所有圖的頂點(diǎn)被訪問(wèn)。圖的遍歷6.3.2圖的廣度優(yōu)先遍歷右圖（a）表示為對(duì)無(wú)向圖G9的廣度優(yōu)先遍歷。首先從頂點(diǎn)A出發(fā)，訪問(wèn)A，標(biāo)注數(shù)字序號(hào)①，接著依次訪問(wèn)A的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)C,G,D,E和B，并依次標(biāo)注數(shù)字序號(hào)②～⑥；再按這個(gè)次序，訪問(wèn)C的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)

H

并標(biāo)注數(shù)字序號(hào)⑦、訪問(wèn)E的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)F并標(biāo)注數(shù)字序號(hào)⑧，最后訪問(wèn)到I并標(biāo)注數(shù)字序號(hào)⑨，它的所有相鄰點(diǎn)都被訪問(wèn)過(guò)了，遍歷結(jié)束，得到的遍歷序列為：AàCàGàDàEàBàHàFàI（a）

對(duì)無(wú)向圖

G9

的廣度優(yōu)先遍歷圖的遍歷6.3.3圖的連通性對(duì)于一個(gè)無(wú)向圖，從某頂點(diǎn)出發(fā)，進(jìn)行一次遍歷（深度優(yōu)先遍歷或廣度優(yōu)先遍歷），能訪問(wèn)到的所有頂點(diǎn)，再加上無(wú)向圖中這些頂點(diǎn)間的所有邊，即能得到包含這個(gè)頂點(diǎn)的連通分量。有向圖的強(qiáng)連通分量也可以借助圖的遍歷算法得到。任選一個(gè)頂點(diǎn)v，從頂點(diǎn)v出發(fā)，順著弧的方向訪問(wèn)到所有可達(dá)的頂點(diǎn)組成集合Vout；再?gòu)倪@個(gè)頂點(diǎn)v出發(fā)，逆著弧的方向遍歷，得到頂點(diǎn)集合Vin；如果這兩個(gè)頂點(diǎn)集合Vout和Vin相等，且包含圖的全部頂點(diǎn)，該有向圖就是一個(gè)強(qiáng)連通圖，否則求它們的交集Vs。交集Vs中的任意兩個(gè)頂點(diǎn)都是互相可到達(dá)的。于是，頂點(diǎn)集合Vs加上集合內(nèi)各頂點(diǎn)的所有弧得到一個(gè)強(qiáng)連通分量。將這個(gè)強(qiáng)連通分量從原圖中去掉，對(duì)剩下的再重復(fù)上述操作，這樣即可求出所有的強(qiáng)連通分量。04PART圖的生成樹(shù)問(wèn)題6.4.1生成樹(shù)與最小生成樹(shù)下面重點(diǎn)介紹連通網(wǎng)最小生成樹(shù)的概念。在此之前，先用一個(gè)例子說(shuō)明它的具體應(yīng)用背景。假設(shè)有n個(gè)城市要建立一個(gè)通信網(wǎng)。實(shí)際上，要連通n個(gè)城市，可以只用n-1條線路，每條線路直接連接兩個(gè)城市。沒(méi)有直接線路連接的兩個(gè)城市之間的通信可以通過(guò)其他城市進(jìn)行中繼。這時(shí)需要考慮的問(wèn)題是，如何建立這個(gè)通信網(wǎng)，從而使經(jīng)費(fèi)最省，即如何確定n-1條線路以使得總的費(fèi)用最低，同時(shí)任意兩個(gè)城市之間可以相互通信。我們可以把城市看成頂點(diǎn)，線路當(dāng)成帶權(quán)值的邊。用n-1條線路連接n個(gè)城市的方法有多種，每一種可以看成一棵生成樹(shù)，上述的問(wèn)題就成了求解一個(gè)生成樹(shù)以使總費(fèi)用最低，也就是各邊權(quán)值之和具有最小值。這樣的生成樹(shù)，我們稱為最小代價(jià)生成樹(shù)，簡(jiǎn)稱最小生成樹(shù)（MinimumSpanning

Tree）。圖的生成樹(shù)問(wèn)題6.4.1生成樹(shù)與最小生成樹(shù)下圖所示為無(wú)向圖G10及其所有生成樹(shù)，其中G10-1和G10-4的各邊權(quán)值之和都是31，具有最小值，所以G10-1和G10-4都是最小生成樹(shù)?？梢?jiàn)，最小生成樹(shù)不一定唯一。圖的生成樹(shù)問(wèn)題6.4.1生成樹(shù)與最小生成樹(shù)有多種算法可以用來(lái)求無(wú)向連通網(wǎng)最小生成樹(shù)，它們大多會(huì)用到如下MST性質(zhì)。假設(shè)G=(V,E)是一個(gè)連通網(wǎng)，U是V的一個(gè)非空子集，這樣圖中所有頂點(diǎn)構(gòu)成的集合被分為兩個(gè)集合：U和V-U。若(u,v)是一條具有最小權(quán)值（代價(jià)）的邊，其中u∈U，v∈V-U，則必存在一棵包含邊(u,v)的最小生成樹(shù)。圖的生成樹(shù)問(wèn)題6.4.1生成樹(shù)與最小生成樹(shù)可以用反證法證明MST性質(zhì)。假定G的所有最小生成樹(shù)都不包含邊(u,v)，任意給出一棵G的最小生成樹(shù)T，由于生成樹(shù)是連通圖，則集合U和集合V-U之間至少有一條邊?，F(xiàn)將邊(u,v)加入最小生成樹(shù)中形成一個(gè)包含邊(u,v)的回路，這時(shí)在當(dāng)前最小生成樹(shù)T中必然存在一條邊(u‘,v’)，滿足u‘∈U，v’∈V-U，且在集合U中u和u‘是連通的，在V-U中v和v’是連通的，否則不可能形成回路，如右圖所示，這樣將邊(u',v')去掉，得到另一棵生成樹(shù)T'。由于(u,v)的權(quán)值不大于(u',v')，因此T'是一棵包含邊(u,v)的，各邊權(quán)值之和不大于T的生成樹(shù)，與假設(shè)矛盾。圖的生成樹(shù)問(wèn)題6.4.2最小生成樹(shù)Prim算法Prim算法思想：給定一個(gè)無(wú)向連通網(wǎng)G=(V,E)，求最小生成樹(shù)T=(U,TE)。初始化時(shí)，從某個(gè)頂點(diǎn)u0開(kāi)始，即頂點(diǎn)集合U只包含一個(gè)頂點(diǎn)u0，邊的集合TE為空集。在所有一端屬于頂點(diǎn)集合U，另外一端屬于頂點(diǎn)集合V-U

的邊的集合中，找一條最小權(quán)值的邊(u,v)，這里u∈U，v∈V-U，將頂點(diǎn)v

加到集合U

中，將邊(u,v)加到TE

中，這樣重復(fù)n-1

次，U

中有了n

個(gè)頂點(diǎn)，TE

中有了n-1

條邊，即可以得到一個(gè)最小生成樹(shù)。由于可能存在多條具有最小權(quán)值的邊，選擇邊的次序不同，會(huì)得到不同形態(tài)的最小生成樹(shù)。此算法的時(shí)間復(fù)雜度為O(n2)。Prim算法適用于對(duì)稠密圖的連通網(wǎng)求最小生成樹(shù)的情況圖的生成樹(shù)問(wèn)題6.4.2最小生成樹(shù)Prim算法圖（a）～圖（f）為用Prim算法求解連通網(wǎng)G11最小生成樹(shù)的過(guò)程。其中，實(shí)線圓圈表示U中的頂點(diǎn)；實(shí)線邊表示TE中的邊；虛線圓圈表示V-U中的頂點(diǎn)；虛線邊表示V-U中各頂點(diǎn)與U中頂點(diǎn)的最小權(quán)值邊以及在U中依附的頂點(diǎn)，如果沒(méi)有虛線邊，表示該V-U中的頂點(diǎn)和U中的頂點(diǎn)沒(méi)有邊。圖的生成樹(shù)問(wèn)題6.4.2最小生成樹(shù)Prim算法假定從頂點(diǎn)A

出發(fā)，U

中包含頂點(diǎn)A，V-U

中的頂點(diǎn)D

和F

與U

中頂點(diǎn)A

沒(méi)有邊，B、E

和C這3

個(gè)頂點(diǎn)與A的邊權(quán)值依次為8、2和6，如（a）所示；選擇最小權(quán)值邊(A,E)加到TE

中，同時(shí)將頂點(diǎn)E

加到U

中，檢查V-U

中剩下各頂點(diǎn)與E

的邊的權(quán)值是否比原來(lái)最小權(quán)值邊小，如果是則修改最小權(quán)值的邊。此例中，V-U中的4個(gè)頂點(diǎn)與U中的最小權(quán)值邊都被修改了，依附頂點(diǎn)都是E，得到結(jié)果如（b）所示。圖的生成樹(shù)問(wèn)題6.4.2最小生成樹(shù)Prim算法再將最小權(quán)值（虛線）邊(C,E)加到TE中，同時(shí)將頂點(diǎn)C加到U中，檢查V-U中的頂點(diǎn)與C的邊的權(quán)值是否比原來(lái)最小權(quán)值邊要小，如果是則修改最小權(quán)值的邊，頂點(diǎn)F與U中頂點(diǎn)的最小權(quán)值邊被修改(C,F)，權(quán)值為7，依附頂點(diǎn)為C，得到結(jié)果如圖（c）所示。圖的生成樹(shù)問(wèn)題6.4.2最小生成樹(shù)Prim算法繼續(xù)將最小權(quán)值（虛線）邊(B,E)加到TE中，將頂點(diǎn)B加到U中，此次V-U中沒(méi)有要修改最小權(quán)值的邊，得到結(jié)果如（d）所示。圖的生成樹(shù)問(wèn)題6.4.2最小生成樹(shù)Prim算法此時(shí)最小權(quán)值（虛線）邊有(D,E)和(C,F)兩條，任選擇其中一條邊(D,E)加到TE中，同時(shí)將頂點(diǎn)D加到U中，V-U中還剩下唯一的頂點(diǎn)F，最小權(quán)值的邊被修改成(D,F)，得到結(jié)果如圖（e）所示。最后得到的最小生成樹(shù)如（f）所示，如果在（d）中選擇邊(C,F)，就會(huì)得到另一棵如（g）所示的最小生成樹(shù)。圖的生成樹(shù)問(wèn)題6.4.3最小生成樹(shù)Kruskal算法克魯斯卡爾（Kruskal）算法適用于對(duì)稀疏圖的連通網(wǎng)求最小生成樹(shù)的情況。假定一個(gè)無(wú)向連通網(wǎng)為G=(V,E)，其最小生成樹(shù)為T=(V,TE)。初始化時(shí)，T的頂點(diǎn)集合包含G中的全部頂點(diǎn)，TE為空集，這時(shí)T中各個(gè)頂點(diǎn)自成一個(gè)連通分量。在無(wú)向連通網(wǎng)G中按權(quán)值從小到大選擇邊(u,v)，如果u、v在不同的連通分量中，則該邊加到生成樹(shù)T中不會(huì)形成回路，成功將邊(u,v)加到TE中，u和v所屬的連通分量合并成一個(gè)，否則舍棄該邊。依此操作，直到成功地加上n-1條邊到TE中為止。或者說(shuō)，當(dāng)T中的所有頂點(diǎn)連接成一個(gè)連通分量時(shí)，就求解到了一棵最小生成樹(shù)。其中，該算法的時(shí)間復(fù)雜度為O(eloge)。圖的生成樹(shù)問(wèn)題6.4.3最小生成樹(shù)Kruskal算法下圖所示的連通網(wǎng)G12初始時(shí)是由所有頂點(diǎn)組成的一個(gè)圖。按權(quán)值從小到大依次選擇邊，首先依次選擇邊(A,E)、(E,C)添加到TE

中，由于邊的兩個(gè)頂點(diǎn)都在不同連通分量中，沒(méi)有形成回路，因此成功地被添加到TE

中，如圖（a）和圖（b）所示；再選擇最小權(quán)值的邊(A,C)時(shí)，因?yàn)檫叺膬蓚€(gè)頂點(diǎn)A

和C

在同一連通分量中，形成一個(gè)回路，故舍棄此邊；圖的生成樹(shù)問(wèn)題6.4.3最小生成樹(shù)Kruskal算法選擇下一條邊(B,E)，沒(méi)有形成回路，成功地被添加到TE

中，如圖（c）所示；接著成功地將(D,F)添加到TE

中，如圖（d）所示；此時(shí)，(D,E)和(C,F)權(quán)值相同，當(dāng)選擇(D,E)這條邊時(shí)，得到一棵圖（e）所示最小生成樹(shù)，否則得到圖（f）所示最小生成樹(shù)。顯然，選擇權(quán)值最小的邊時(shí)，如果有多個(gè)備選項(xiàng)，可能會(huì)導(dǎo)致得到不同最小生成樹(shù)。05PART圖的最短路徑問(wèn)題6.5.1單源最短路徑Dijkstra算法單源最短路徑的求解，即在一個(gè)有向網(wǎng)G=(V,E)中，給定一個(gè)頂點(diǎn)vs（vs∈V，0≤s≤n-1）作為源點(diǎn)，求源點(diǎn)到G中其他各頂點(diǎn)的最短路徑。下圖列出了有向網(wǎng)G13及其以v0作為源點(diǎn)到其他所有頂點(diǎn)的最短路徑和長(zhǎng)度。圖的最短路徑問(wèn)題6.5.1單源最短路徑Dijkstra算法單源最短路徑求解算法是由迪杰斯特拉（Dijkstra）提出的，按路徑長(zhǎng)度遞增次序逐條求出源點(diǎn)到其他所有頂點(diǎn)的最短路徑。算法中，使用3個(gè)大小為n的輔助數(shù)組，最短路徑數(shù)組D記錄當(dāng)前從源點(diǎn)到G中各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度；盡管路徑上會(huì)有多個(gè)頂點(diǎn)，但不必都直接記錄，只需用前驅(qū)頂點(diǎn)數(shù)組P記錄當(dāng)前最短路徑中終點(diǎn)的前驅(qū)（倒數(shù)第二個(gè)）頂點(diǎn)的序號(hào)，也就是最短路徑是從源點(diǎn)出發(fā)，到達(dá)這個(gè)前驅(qū)頂點(diǎn)后再到終點(diǎn)；數(shù)組final是一個(gè)標(biāo)志數(shù)組，元素值取TRUE或FALSE，表示對(duì)應(yīng)頂點(diǎn)的最短路徑是否已經(jīng)求得。圖的最短路徑問(wèn)題6.5.1單源最短路徑Dijkstra算法假定以鄰接矩陣作為有向網(wǎng)的存儲(chǔ)結(jié)構(gòu)，Dijkstra最短路徑算法執(zhí)行過(guò)程如下。（1）初始化操作，將G的鄰接矩陣第s行的n個(gè)權(quán)值賦予數(shù)組D，數(shù)組P中的全部元素值初始化為s，final[s]置為TRUE，其他元素都置為FALSE。（2）選擇滿足下面條件的下一條最短路徑終點(diǎn)vj。D[j]=min{D[i]|final[i]=

FALSE,D[i]1

∞}一旦選擇好終點(diǎn)vj后，將final[j]置為TRUE，并對(duì)D進(jìn)行更新處理。D[k]=min{D[k],D[j]+

G.arcs[j][k]}vk?V-

SD[k]的值被更新，就置P[k]為j。重復(fù)步驟（2）n-1次，求出源點(diǎn)到所有頂點(diǎn)的最短路徑。算法首先完成初始化操作，需要對(duì)3個(gè)長(zhǎng)度為n的數(shù)組賦初值，所以時(shí)間開(kāi)銷為O(n)；接著要完成選擇n-1次終點(diǎn)的操作，每次需要對(duì)鄰接矩陣中的一行進(jìn)行遍歷，所以時(shí)間開(kāi)銷為O(n2)，綜合得到算法的時(shí)間復(fù)雜度為O(n2)圖的最短路徑問(wèn)題6.5.1單源最短路徑Dijkstra算法圖的最短路徑問(wèn)題6.5.2各頂點(diǎn)間最短路徑Floyd算法在有向網(wǎng)G中，如何求任意兩個(gè)頂點(diǎn)之間的最短路徑呢？一種方法是依次選擇G中的頂點(diǎn)作為源點(diǎn)，反復(fù)調(diào)用Dijkstra算法求解，一共調(diào)用n次，所以算法的時(shí)間復(fù)雜度為O(n3)。另一種是弗洛伊德（Floyd）算法，其形式非常簡(jiǎn)潔，但算法的時(shí)間復(fù)雜度也是O(n3)。弗洛伊德算法思想是：根據(jù)有向網(wǎng)

G

的鄰接矩陣（也稱為代價(jià)矩陣），復(fù)制構(gòu)造出一個(gè)

n×n的矩陣D(-1)，如果由vi到vj有弧，則vi到vj

有一條長(zhǎng)度為D(-1)[i][j]的路徑(vi

,vj)，但它不一定是vi到vj的最短路徑，還需要進(jìn)行還需要進(jìn)行n次測(cè)試。首先考慮路徑(vi,v0,vj)是否存在，如果存在就將其與(vi,vj)比較路徑長(zhǎng)度，取較小者來(lái)代替(vi,vj)的路徑長(zhǎng)度，并賦予D(0)[i][j]；對(duì)G的每一對(duì)頂點(diǎn)都做這樣以v0作為中間頂點(diǎn)的試探后得到矩陣D(0)，則D(0)[i][j]表示從vi到vj的中間頂點(diǎn)序號(hào)不大于0的最短路徑長(zhǎng)度。圖的最短路徑問(wèn)題6.5.2各頂點(diǎn)間最短路徑Floyd算法接著對(duì)矩陣D(0)再用v1來(lái)試探，考慮路徑(vi,…,v1,…,vj)，此時(shí)(vi,…,v1)和(v1,…,vj)都是中間頂點(diǎn)序號(hào)不超過(guò)0的最短路徑，對(duì)應(yīng)最短路徑長(zhǎng)度為D(0)

[i][1]和

D(0)

[1][j]，取D(0)

[i][1]+D(0)

[1][j]與D(0)[i][j]的較小值，將其值賦予給D(1)[i][j]，則D(1)[i][j]表示從vi到vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑長(zhǎng)度。依此類推，一般情況下，對(duì)矩陣D(k-1)

用vk來(lái)試探，考慮路徑(vi,…,vk,…,vj)，此時(shí)(vi,…,vk)和(vk,…,vj)都是中間頂點(diǎn)序號(hào)不超過(guò)k-1的最短路徑，對(duì)應(yīng)最短路徑長(zhǎng)度為D(k-1)

[i][k]和D(k-1)

[k]

[j]，取D(k-1)

[i][k]+D(k-1)

[k]

[j]與D(k-1)[i][j]的較小值，將其值賦予給D(k)[i][j]，則D(k)[i][j]表示從vi到vj的中間頂點(diǎn)序號(hào)不大于k的最短路徑長(zhǎng)度。這個(gè)由G的鄰接矩陣到矩陣D(n-1)的過(guò)程可表示為：D(-1)[i][j]=

G.arcs[i][j]D(k)[i][j]=min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}

0≤k≤n-1圖的最短路徑問(wèn)題6.5.2各頂點(diǎn)間最短路徑Floyd算法下面給出各頂點(diǎn)間最短路徑Floyd算法。06PART6.6.1拓?fù)渑判蛞粋€(gè)無(wú)環(huán)的有向圖稱為有向無(wú)環(huán)圖（DirectedAcyclicGraph)，簡(jiǎn)稱DAG圖。圖（a）中是一個(gè)DAG圖，而圖（b）中有回路ACDBA，所以該圖不是DAG圖。有向無(wú)環(huán)圖的應(yīng)用6.6.1拓?fù)渑判蛟谝粋€(gè)有向圖中，如果頂點(diǎn)vi到vj有路徑，則稱vi是vj的前驅(qū)，vj是vi的后繼，即vi和vj有前驅(qū)和后繼關(guān)系。在一個(gè)有向圖中，并不是每對(duì)頂點(diǎn)都具有前驅(qū)和后繼關(guān)系，即頂點(diǎn)間是一種偏序關(guān)系。拓?fù)渑判蚴侵附o出有向圖的一個(gè)頂點(diǎn)線性序列，該序列中任意兩個(gè)頂點(diǎn)都有前驅(qū)和后繼關(guān)系，所以該頂點(diǎn)序列是有前驅(qū)和后繼關(guān)系的一個(gè)全序，但要求在這個(gè)頂點(diǎn)的線性序列中保持有向圖中原有頂點(diǎn)間的前驅(qū)和后繼關(guān)系。符合這樣性質(zhì)的頂點(diǎn)線性序列稱為有向圖的拓?fù)渑判?。如果在一個(gè)有向圖中存在回路，回路中頂點(diǎn)間的前驅(qū)和后繼關(guān)系是對(duì)稱的，所以不可能有拓?fù)渑判?，否則總有一種前驅(qū)和后繼關(guān)系不滿足；只有DAG圖才可能給出頂點(diǎn)的拓?fù)渑判蛐蛄?。有向無(wú)環(huán)圖的應(yīng)用6.6.1拓?fù)渑判蛞杂?jì)算機(jī)科學(xué)與技術(shù)專業(yè)若干門必修課程的學(xué)習(xí)為例，每門課程的學(xué)習(xí)都必須在其先修課程完成之后才能開(kāi)始。例如，“數(shù)據(jù)結(jié)構(gòu)”必須在“高級(jí)語(yǔ)言程序設(shè)計(jì)”和“離散數(shù)學(xué)”之后，如下表所示。有向無(wú)環(huán)圖的應(yīng)用課程編號(hào)課程名稱先修課程C1高級(jí)語(yǔ)言程序設(shè)計(jì)無(wú)C2高等數(shù)學(xué)無(wú)C3普通物理C2C4離散數(shù)學(xué)C1C5數(shù)據(jù)結(jié)構(gòu)C1,C4C6匯編語(yǔ)言C1C7計(jì)算機(jī)原理C3C8操作系統(tǒng)原理C5,C6,C7C9編譯原理C5,C66.6.1拓?fù)渑判蜻@種先后順序可以用下圖來(lái)直觀地表示。其中，頂點(diǎn)表示課程；弧表示先決條件，如課程C1

是課程C4的先修課程，則課程C1到課程C4就有一條弧。這種以頂點(diǎn)表示活動(dòng)、以弧表示活動(dòng)之間優(yōu)先關(guān)系的DAG

圖，稱為AOV（Activity

On

Vertex）網(wǎng)。假定一個(gè)時(shí)間段內(nèi)只能學(xué)習(xí)一門課程，那么如何安排學(xué)習(xí)計(jì)劃以保證在學(xué)習(xí)任何一門課程時(shí)，其先修課程都已經(jīng)事先學(xué)習(xí)了。這實(shí)際上是一個(gè)拓?fù)渑判騿?wèn)題，我們可以給出所有課程的一個(gè)拓?fù)渑判?，按照此次序安排學(xué)習(xí)計(jì)劃。例如：(C1,C4,C5,C6,C9,C2,C3,C7,C8)(C1,C2,C3,C4,C5,C6,C7,C8,C9)有向無(wú)環(huán)圖的應(yīng)用6.6.1拓?fù)渑判蛳旅娣治鲆粋€(gè)AOV網(wǎng)進(jìn)行拓?fù)渑判虻乃惴??？紤]到活動(dòng)之間的依賴關(guān)系：如果活動(dòng)vi

到vj有一條有向邊，在拓?fù)渑判蛩玫降男蛄兄谢顒?dòng)vi一定在活動(dòng)vj之前。因此，該拓?fù)渑判蛩惴ㄋ枷胧侵貜?fù)下列操作。（1）在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)輸出（也就是選擇入度為0的頂點(diǎn)）。（2）從圖中刪除該頂點(diǎn)和所有以它為弧尾的?。ú⑾鄳?yīng)修改其他頂點(diǎn)的入度）。重復(fù)上述兩個(gè)步驟，直到所有的頂點(diǎn)被輸出。如果沒(méi)有輸出所有頂點(diǎn)，則表示有向圖中有回路。對(duì)于一個(gè)有n個(gè)頂點(diǎn)、e條邊的有向圖而言，分析各個(gè)頂點(diǎn)入度的算法時(shí)間效率為O(n+e)，使用棧保存入度為0的頂點(diǎn)，每個(gè)頂點(diǎn)都需要入棧、出棧1次，每條弧都需要完成入度減1操作一次，這樣最后綜合算法時(shí)間復(fù)雜度為O(n+e)。有向無(wú)環(huán)圖的應(yīng)用6.6.1拓?fù)渑判虬凑丈鲜龅牟僮鞑襟E，對(duì)圖（a）所示課程的AOV網(wǎng)進(jìn)行拓?fù)渑判?。首選能夠輸出的是C1和

C2，這里選擇是輸出

C1，刪除以

C1為弧尾的弧，得到圖（b）；再選擇輸出

C4，C4輸出后得到圖（c）；入度為

0

的頂點(diǎn)有

C2、C5和

C6，再選擇

C2輸出。這樣按算法步驟重復(fù)處理，直到最后得到輸出序列為(C1,C4,C2,C3,C6,C5,C9,C7,C8)。有向無(wú)環(huán)圖的應(yīng)用6.6.2關(guān)鍵路徑如果在一個(gè)有向網(wǎng)中頂點(diǎn)表示事件、弧表示活動(dòng)，則稱有向網(wǎng)為AOE（ActivityOnEdge）網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的DAG圖（有向無(wú)環(huán)圖），權(quán)值代表活動(dòng)的持續(xù)時(shí)間。通常，我們可以用AOE網(wǎng)來(lái)估算一個(gè)工程的進(jìn)度。例如，下圖所示的一個(gè)工程有11個(gè)活動(dòng)、9個(gè)事件。其中，v1為工程的起點(diǎn)，也是唯一的入度為0的頂點(diǎn)，稱為源點(diǎn)；v9為工程的結(jié)束點(diǎn)，也是唯一的出度為0的頂點(diǎn)，稱為匯點(diǎn)。與AOE網(wǎng)對(duì)應(yīng)的問(wèn)題有以下兩個(gè)。（1）整個(gè)工程至少需要多長(zhǎng)時(shí)間完成?（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？有向無(wú)環(huán)圖的應(yīng)用6.6.2關(guān)鍵路徑由于部分活動(dòng)是可以并行進(jìn)行的，因此第一個(gè)問(wèn)題的答案是源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑，這里最長(zhǎng)路徑是指路徑上邊的權(quán)值之和具有最大值。最長(zhǎng)路徑也稱為關(guān)鍵路徑，關(guān)鍵路徑上的所有活動(dòng)稱為關(guān)鍵活動(dòng)。AOE網(wǎng)中，對(duì)任何一個(gè)活動(dòng)ak（對(duì)應(yīng)一條?。┛梢远x該活動(dòng)的最早開(kāi)始時(shí)間e(k)，以及最遲開(kāi)始時(shí)間l(k)。l(k)-e(k)稱為活動(dòng)余量，表示該活動(dòng)的進(jìn)行有對(duì)應(yīng)于這個(gè)活動(dòng)余量的延時(shí)，并且不影響整個(gè)工程的工期。如果活動(dòng)余量為0，則稱該活動(dòng)為關(guān)鍵活動(dòng)。顯然，關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)，某個(gè)關(guān)鍵活動(dòng)的提前完成可能會(huì)縮短整個(gè)工程的工期；反之，拖延則一定會(huì)延誤整個(gè)工程的工期。有向無(wú)環(huán)圖的應(yīng)用6.6.2關(guān)鍵路徑對(duì)于活動(dòng)ak，假定其對(duì)應(yīng)的弧為<vi,vj>，即該活動(dòng)ak是頂點(diǎn)vi到頂點(diǎn)vj的弧，其持續(xù)時(shí)間用dut<i,j>表示。為了求解出活動(dòng)的最早、最遲開(kāi)始時(shí)間，首先需要求解各頂點(diǎn)事件的最早、最遲發(fā)生時(shí)間，再根據(jù)頂點(diǎn)事件的最早、最遲發(fā)生時(shí)間來(lái)求解所有活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間。頂點(diǎn)vj事件的最早發(fā)生時(shí)間（用ve(j)表示）是源點(diǎn)v1到vj的最長(zhǎng)路徑，這是因?yàn)轫旤c(diǎn)vj事件要發(fā)生，前提必須是源點(diǎn)到該頂點(diǎn)的所有路徑上的活動(dòng)都已經(jīng)完成了。求解頂點(diǎn)事件的最早發(fā)生時(shí)間，可從源點(diǎn)v1開(kāi)始，朝匯點(diǎn)的方向，采用遞推的方法求出所有頂點(diǎn)事件的最早發(fā)生時(shí)間。首先置源點(diǎn)v1的最早發(fā)生時(shí)間ve(1)=0，對(duì)其他的所有頂點(diǎn)vj，有ve(j)=max{ve(i)+

dut<

i,j>}j=2,3,…,n在不允許工程拖延的情況下，匯點(diǎn)vn的最遲發(fā)生時(shí)間為vl(n)=ve(n)，同樣使用遞推方法，由匯點(diǎn)開(kāi)始，朝源點(diǎn)的方向，能求出所有頂點(diǎn)vi的最遲發(fā)生時(shí)間。遞推公式為：vl(i)=min{vl(j)-

dut<

i,j>}

i=n-1,…,1有向無(wú)環(huán)圖的應(yīng)用07PART6.7.1并查集并查集是一種用來(lái)管理元素分組情況的樹(shù)狀數(shù)據(jù)結(jié)構(gòu)，它用于處理一些不相交集合的合并及查詢問(wèn)題。并查集的基本思想是：將森林中的每棵樹(shù)表示成一個(gè)集合，每個(gè)元素對(duì)應(yīng)一個(gè)樹(shù)結(jié)點(diǎn)，通過(guò)樹(shù)的根結(jié)點(diǎn)唯一標(biāo)識(shí)一個(gè)集合，只要找到某個(gè)元素所在樹(shù)根結(jié)點(diǎn)就能確定該元素在哪個(gè)集合中。如果兩個(gè)元素的根結(jié)點(diǎn)相同，則在同一個(gè)集合中，否則不在同一個(gè)集合中。并查集有3

個(gè)基本操作：①查找，查找某個(gè)元素所屬的集合，即查找根結(jié)點(diǎn)的過(guò)程；②合并，將兩個(gè)集合合并在一起，即通過(guò)將一棵樹(shù)的根結(jié)點(diǎn)作為另外一棵樹(shù)根結(jié)點(diǎn)的孩子結(jié)點(diǎn)，完成集合的合并；③路徑壓縮，在查找過(guò)程中同時(shí)壓縮查找路徑以提高后續(xù)查找的效率。應(yīng)用實(shí)例6.7.1并查集下面通過(guò)一個(gè)例子來(lái)說(shuō)明并查集的應(yīng)用。問(wèn)題描述：有一個(gè)非常龐大的群體，現(xiàn)已知該群體成員親屬關(guān)系，要求判斷任意給出的兩個(gè)群體成員是否具有親戚關(guān)系。輸入：第1行有n、m和p3個(gè)整數(shù)，它們分別表示n個(gè)群體成員、m個(gè)親戚關(guān)系、詢問(wèn)p對(duì)親戚關(guān)系。接著有m行：每行兩個(gè)數(shù)Mi和Mj，1≤Mi，Mj≤n，分別表示Mi和Mj有親戚關(guān)系。接下來(lái)p行：每行兩個(gè)數(shù)Pi和Pj，1≤Pi，Pj≤n，詢問(wèn)Pi和Pj是否具有親戚關(guān)系。輸出：共

p

行，每行顯示“Yes”或“No”，表示第

i（1≤i≤p）個(gè)詢問(wèn)的答案為“有”或“沒(méi)有”親戚關(guān)系。應(yīng)用實(shí)例6.7.1并查集此問(wèn)題的求解不一定要建立圖數(shù)學(xué)模型，可以借用并查集這種數(shù)據(jù)結(jié)構(gòu)來(lái)高效地完成。將有親戚關(guān)系的成員看成一個(gè)集合，將一個(gè)集合中成員表示成一棵樹(shù)，這樣樹(shù)中的每一個(gè)結(jié)點(diǎn)代表一個(gè)成員，根結(jié)點(diǎn)可以作為集合的唯一標(biāo)識(shí)。（1）初始時(shí)，n個(gè)成員對(duì)應(yīng)