數(shù)據(jù)結(jié)構(gòu)第七章圖課件

圖的定義和術(shù)語(yǔ)圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷生成樹(shù)

最短路徑拓?fù)渑判?/p>

習(xí)題圖是一種較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間有線性關(guān)系，每一個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后續(xù)；在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，即每一個(gè)數(shù)據(jù)元素有一個(gè)直接前驅(qū)(雙親)和零個(gè)或多個(gè)直接后續(xù)(孩子)；而在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。由此，圖的應(yīng)用極為廣泛。例如，城市間的最短路徑，火車(chē)的聯(lián)票，交通網(wǎng)的計(jì)劃，戰(zhàn)場(chǎng)上的運(yùn)輸問(wèn)題，龐大的施工進(jìn)度圖等都是圖的應(yīng)用。

圖的定義和術(shù)語(yǔ)定義：圖(graph)：是一種數(shù)據(jù)結(jié)構(gòu)，由二個(gè)集合V和E組成，記作G=(V,E)。其中V是數(shù)據(jù)元素(頂點(diǎn))的非空有限集，E是V中二元關(guān)系(邊edge)的集合。樹(shù)是圖的特例，而線性表是樹(shù)的特例。術(shù)語(yǔ)：

有向圖：圖的每條邊都是有序頂點(diǎn)對(duì)(即邊是有方向)。

?。河邢驁D的邊。并將構(gòu)成該邊的有序頂點(diǎn)對(duì)用一對(duì)尖括號(hào)括起來(lái)。如<u,v>∈E，表示從頂點(diǎn)u到頂點(diǎn)v的一條弧，稱(chēng)u為弧尾或初始點(diǎn)，v為弧頭或終端點(diǎn)。并且說(shuō)v是與u相鄰的頂點(diǎn)，或v是u的鄰接點(diǎn)

例如，圖7.1(a)所示的為有向圖，它是由集合

V={v0,v1,v2,v3}E={<v0,v1>,<v0,v2>,<v2,v3>,<v3,v0>}

組成的。圖7.1(a)有向圖G1

無(wú)向圖：圖的每條邊是無(wú)方向的，有<u,v>∈E，必有<v,u>∈E。即用圓括號(hào)括起來(lái)

(u,v)∈E表示邊，并且，u和v互稱(chēng)為鄰接點(diǎn)

例如，圖7.1(b)為無(wú)向圖，它是由集合

V={v0,v1,v2,v3,v4}E={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)}

組成的。網(wǎng)絡(luò)：若圖中每條邊或弧都附加一個(gè)數(shù)值作為權(quán),帶權(quán)圖。子圖：若G1={V1,E1}，G2={V2,E2}是兩個(gè)圖，且V2被包含在V1中，E2被包含在E1中，則稱(chēng)圖G2是圖G1的子圖。度：無(wú)向圖中，頂點(diǎn)的度是依附于該頂點(diǎn)的邊數(shù)。有向圖中，該頂點(diǎn)入邊的數(shù)目叫入度，該頂點(diǎn)出邊的數(shù)目叫出度，該頂點(diǎn)的度就是入度+出度。圖中的頂點(diǎn)度數(shù)之和等于邊數(shù)的2倍。路徑：在有向圖(或無(wú)向圖)中，如果存在首尾相接并且無(wú)重復(fù)邊的邊序列<v0,v1>,<v1,v2>,…,<vn-2,vn-1>(或(v0,v1),(v1,v2),…,(vn-2,vn-1))，那么稱(chēng)這個(gè)序列是一條從頂點(diǎn)到v0到vn-1的一條路徑，記著(v0,v1,v2,…,vn-2,vn-1)。序列中的邊數(shù)稱(chēng)為路徑長(zhǎng)度。在有向圖中，路徑是有方向的；而在無(wú)向圖中，路徑無(wú)方向。簡(jiǎn)單路徑：在一條路徑中，若除起點(diǎn)和終點(diǎn)外，所有頂點(diǎn)彼此各不相同?；芈罚涸谝粭l路徑中，若起點(diǎn)和終點(diǎn)是同一頂點(diǎn)。簡(jiǎn)單回路：有簡(jiǎn)單路徑組成的回路稱(chēng)為簡(jiǎn)單回路。連通：在無(wú)向圖G中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑存在。連通圖：在無(wú)向圖G中，若任意二個(gè)頂點(diǎn)之間都是連通的.連通分量：在非連通的無(wú)向圖G中，極大連通子圖(在滿(mǎn)足連通條件下，盡可能多的包含G中的頂點(diǎn)和這些頂點(diǎn)之間的邊).如圖7.2中，圖G有三個(gè)連通分量。

(a)有向圖G(b)圖G的三個(gè)連通分量

強(qiáng)連通：在有向圖G中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑存在，并且從頂點(diǎn)vj到頂點(diǎn)vi也有路徑存在。強(qiáng)連通圖：在有向圖G中，若任意二個(gè)頂點(diǎn)之間都是強(qiáng)連通的。

強(qiáng)連通分量：在非強(qiáng)連通的有向圖G中，極大強(qiáng)連通子圖稱(chēng)為有向圖的強(qiáng)連通分量。如圖7.3中，有向圖G有兩個(gè)強(qiáng)連通分量。生成樹(shù)：在一個(gè)有n頂點(diǎn)的連通圖G中，存在一個(gè)極小的連通子圖G′，G′包含圖G的所有頂點(diǎn)，但只有n-1條邊，并且G′是連通的。(a)有向圖G(b)圖G的二個(gè)強(qiáng)連通分量

圖7.3有向圖及其強(qiáng)連通分量圖的存儲(chǔ)結(jié)構(gòu)常用的圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表、十字鏈表、多重鏈表等方法。本節(jié)介紹最為常用的鄰接矩陣和鄰接表方法。對(duì)圖的存儲(chǔ)結(jié)構(gòu)的選擇取決于具體的應(yīng)用。1、鄰接矩陣(1)存儲(chǔ)形式鄰接矩陣是用一個(gè)二維數(shù)組來(lái)表示圖中頂點(diǎn)間的相鄰關(guān)系的數(shù)據(jù)結(jié)構(gòu)。設(shè)圖G=(V,E)，有n≥1個(gè)頂點(diǎn)，則所對(duì)應(yīng)圖G的鄰接矩陣A是按如下定義的一個(gè)n×n的二維數(shù)組。若圖G是一個(gè)網(wǎng)絡(luò)，其鄰接矩陣

借助于鄰接矩陣很容易判定任意兩個(gè)頂點(diǎn)之間是否有邊(或弧)相連，并容易求得各個(gè)頂點(diǎn)的度，操作方便。

(2)鄰接矩陣法的特點(diǎn)：1.存儲(chǔ)空間：對(duì)于無(wú)向圖而言，它的鄰接矩陣是對(duì)稱(chēng)矩陣，所以可采用壓縮存儲(chǔ)法（下三角），其存儲(chǔ)空間只需n(n+1)/2。但對(duì)于有向圖而言，因?yàn)樗幕∈怯蟹较虻?，它的鄰接矩陣不一定是?duì)稱(chēng)矩陣，所以需要n2個(gè)存儲(chǔ)空間。2.便于運(yùn)算：采用鄰接矩陣表示法，便于判定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連，即根據(jù)A[i，j]=0或1來(lái)判斷。另外還便于求得各個(gè)頂點(diǎn)的度。2、鄰接表(1)存儲(chǔ)形式對(duì)一個(gè)有n個(gè)頂點(diǎn)圖的頂點(diǎn)進(jìn)行編號(hào)，頂點(diǎn)的編號(hào)從1到n。圖的鄰接表存儲(chǔ)結(jié)構(gòu)與樹(shù)的孩子表示法相同。將圖G中每個(gè)頂點(diǎn)vi的所有鄰接點(diǎn)用一個(gè)單鏈表(鄰接點(diǎn)鏈表)表示，在vi的鄰接點(diǎn)鏈表中存放vj(有(vi,vj)或<vi,vj>∈E)的編號(hào)，以及其它與該邊或弧相關(guān)的信息。一個(gè)圖有n個(gè)頂點(diǎn)就有n個(gè)鄰接點(diǎn)鏈表(度為0的頂點(diǎn)，所對(duì)應(yīng)的鄰接點(diǎn)鏈表為空表)。這n個(gè)鄰接點(diǎn)鏈表的頭指針又構(gòu)成一個(gè)線性表，用一個(gè)指針數(shù)組存儲(chǔ)該線性表，這樣就構(gòu)成了圖的鄰接表的存儲(chǔ)結(jié)構(gòu)。例如，在圖7.1中，G1和G2的的鄰接表如圖7.5所示，圖中下標(biāo)對(duì)應(yīng)頂點(diǎn)vi的編號(hào)。

(a)G1的鄰接表(b)G2的鄰接表圖7.5鄰接表存儲(chǔ)結(jié)構(gòu)

逆鄰接表：對(duì)于為網(wǎng)絡(luò)的圖G=(V,E)，在node結(jié)構(gòu)中可以添加一個(gè)權(quán)值域。而對(duì)于有向圖，圖7.5(a)所示為按G1出度建立的鄰接表，在該鄰接表中求每個(gè)頂點(diǎn)vi的出度和以vi為尾的弧方便，但若要求頂點(diǎn)的入度，必須遍歷整個(gè)鄰接表。所以，有時(shí)為了使求頂點(diǎn)vi的入度和以vi為頭的弧方便，可以建立該有向圖的逆鄰接表，即在vi的鄰接點(diǎn)鏈表中存放vj(有<vj,vi>∈E)的編號(hào)。如圖7.6所示為圖7.1(a)中G1的逆鄰接表。圖7.6G1的逆鄰接表生成無(wú)向帶權(quán)圖的鄰接表的算法：Constn:=圖頂點(diǎn)數(shù)；

e:=圖中邊數(shù)；Typeedge=^edgenode;edgenode=recordadj:1..n;weight:weighttypenext:edge;end;vexnode=recorddata:datatype;link:edge;end;dajlish=arrar[1..n]ofvexnode;Procedurecreate(varg:dajlish);Beginfori:=1tondobeginread(g[i].data);g[i].link:=nil;end;fork:=1toedobeginread(i,j,w);new(s);s^.adj:=j;s^.weight:=w;s^.next:=g[i].link;g[i].link:=s;End;End;

思考并實(shí)現(xiàn)：1、分別在無(wú)向圖和有向圖的鄰接表上統(tǒng)計(jì)各頂點(diǎn)的度（有向圖為入度和出度）。2、統(tǒng)計(jì)圖（有向圖和無(wú)向圖）的頂點(diǎn)度數(shù)和。2、邊集數(shù)組表示法v1v5v2v3v4254371邊數(shù)123456起點(diǎn)112234終點(diǎn)253545權(quán)4532177.3圖的遍歷與樹(shù)的遍歷相同，把按一定的規(guī)律沿著圖中的邊訪問(wèn)圖的每個(gè)頂點(diǎn)，并且使每一個(gè)頂點(diǎn)只被訪問(wèn)一次的過(guò)程稱(chēng)為圖的遍歷。因?yàn)樵趫D中任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系。為保證每一個(gè)頂點(diǎn)只被訪問(wèn)一次，必須對(duì)訪問(wèn)過(guò)的頂點(diǎn)進(jìn)行標(biāo)記，一般是用一個(gè)輔助數(shù)組visit[i]作為對(duì)頂點(diǎn)的標(biāo)記。當(dāng)頂點(diǎn)vi未被訪問(wèn)，visit[i]值為0；當(dāng)頂點(diǎn)vi已被訪問(wèn)，則visit[i]值為1。圖的遍歷方法通常有先深度遍歷和先廣度遍歷兩種。但經(jīng)常稱(chēng)這兩種遍歷為深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS。7.3.1深度優(yōu)先搜索DFS(DepthFirstSearch)

圖的深度優(yōu)先搜索是樹(shù)的先序遍歷的推廣，其定義(遞歸)如下：

(1)從圖G=(V,E)中選任意某個(gè)未訪問(wèn)過(guò)的頂點(diǎn)vi作為搜索的出發(fā)點(diǎn)。

(2)訪問(wèn)vi。

(3)以vi的每一個(gè)未被訪問(wèn)過(guò)的鄰接點(diǎn)w為出發(fā)點(diǎn)，深度優(yōu)先搜索圖G。

(4)直至圖G中所有與vi有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)。

(5)若圖G中尚有頂點(diǎn)未曾訪問(wèn)過(guò)，則轉(zhuǎn)到(1)；否則，搜索結(jié)束。其中實(shí)箭頭代表訪問(wèn)方向，虛箭頭代表回溯方向，箭頭旁邊的數(shù)字代表搜索順序，A為起始頂點(diǎn)。8ADGBEHCFI1236710114155149131216訪問(wèn)序列為：A、B、C、F、E、G、D、H、I。深度優(yōu)先搜索算法：Proceduredfs(i:1..n);{圖用鄰接表存儲(chǔ)，其他方式的存儲(chǔ)只需稍作修改，g[i]為表頭結(jié)點(diǎn)表}Beginwrite(g[i].v);{輸出是最為簡(jiǎn)單的訪問(wèn)方式}visited[i]:=true;p:=g[i].link;whilep<>nildobeginj:=p^.adj;{j為i的一個(gè)后繼}ifnotvisited[j]thendfs(j);{遞歸}p:=p^.next;{回溯}end;end/;7.3.2廣度優(yōu)先搜索BFS(BreadthFirstSearch)

圖的廣度優(yōu)先搜索與按層次遍歷樹(shù)相似，定義如下：

(1)從圖G=(V,E)中選任意某個(gè)未訪問(wèn)過(guò)的頂點(diǎn)vi作為搜索的出發(fā)點(diǎn)。

(2)訪問(wèn)vi。

(3)依次訪問(wèn)vi的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)。分別從這些鄰接點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索，直至圖中所有與vi有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)。

(4)若圖中尚有頂點(diǎn)未曾訪問(wèn)過(guò)，則轉(zhuǎn)到(1)；否則，搜索結(jié)束。ADGBEHCFI14657823訪問(wèn)序列為：A、B、E、D、C、G、F、H、I。廣度優(yōu)先搜索算法：Procedurebfs(i:1..n);{圖用鄰接表g表示}Begincreate(q);{建隊(duì)，置隊(duì)空}write(g[i].v);{訪問(wèn)vi}visited[i]:=true;{標(biāo)記已經(jīng)訪問(wèn)的結(jié)點(diǎn)}push(q,i);{進(jìn)隊(duì)列}whilenotempty(q)do{廣度優(yōu)先遍歷，直到隊(duì)列空為止，表示所有節(jié)點(diǎn)都被訪問(wèn)過(guò)了}begini:=pop(q);{取頂點(diǎn)，對(duì)首元素出隊(duì)}p:=g[i].link;{取邊表指針}whilep<>nildo{還有后繼頂點(diǎn)}beginifnotvisited[p^.adj]thenbeginwrite(g[p^.adj].v);{訪問(wèn)當(dāng)前頂點(diǎn)}visited[p^.adj]:=true;push(q,p^,adj);{當(dāng)前頂點(diǎn)入隊(duì)}end;p:=p^.next;{從邊表中取下一個(gè)鄰接邊}end;end;End;生成樹(shù)

1、概念生成樹(shù)是一個(gè)連通圖G的一個(gè)極小的連通子圖。包含圖G的所有頂點(diǎn)，但只有n-1條邊，并且是連通的。在生成樹(shù)中，不存在回路路徑，但若在生成樹(shù)中任意增加一條邊，則必構(gòu)成回路。一個(gè)連通圖的生成樹(shù)不是惟一的，例如，對(duì)一個(gè)連通圖進(jìn)行深度優(yōu)先，在搜索過(guò)程中經(jīng)過(guò)的邊和圖的頂點(diǎn)，構(gòu)成深度優(yōu)先生成樹(shù)；若進(jìn)行廣度優(yōu)先搜索，則構(gòu)成廣度優(yōu)先生成樹(shù)。非連通圖有若干個(gè)連通分量組成，每一個(gè)連通分量都存在生成樹(shù)，這樣就構(gòu)成生成森林。2、最小生成樹(shù)(最小支撐樹(shù))

若有一個(gè)連通的無(wú)向圖G，它有n個(gè)頂點(diǎn)，并且它的邊是有權(quán)值的。在圖G上構(gòu)造生成樹(shù)G’(n個(gè)頂點(diǎn)，n-1條邊，G’是連通的)，因?yàn)樯蓸?shù)的非惟一性，則有多個(gè)G’存在，而最小生成樹(shù)是n-1條邊的權(quán)值之和最小的G’。最小生成樹(shù)也是非惟一的，但圖G所有最小生成樹(shù)的n-1條邊的權(quán)值之和相同，并且為最小值。例如，用帶權(quán)的連通無(wú)向圖G表示n個(gè)城市之間的交通網(wǎng)，最小生成樹(shù)問(wèn)題是：如何確定n-1條線路連通這n個(gè)城市，并且代價(jià)最小。在帶權(quán)的連通無(wú)向圖G=(V,E)上，構(gòu)造最小生成樹(shù)有普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法，它們都是利用最小生成樹(shù)中簡(jiǎn)稱(chēng)為MST的性質(zhì)：U是頂點(diǎn)集V的一個(gè)非空子集，若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U，則必存在一棵包含邊(u,v)的最小生成樹(shù)。(1)普里姆(Prim)算法該算法是利用MST性質(zhì)，描述如下：

假設(shè)G=(V,E)是帶權(quán)的連通無(wú)向圖，從u0∈V開(kāi)始構(gòu)造G上最小生成樹(shù)G’=(U,TE)，初始U={u0}，TE=φ。重復(fù)以下步驟：在所有的u∈U(生成樹(shù)中的頂點(diǎn))，v∈V-U(尚不在生成樹(shù)中的頂點(diǎn))，且(u,v)∈E中找一條權(quán)值最小的邊(u0,v0)并入TE，同時(shí)v0并入U(xiǎn)，直至U=V時(shí)結(jié)束。此時(shí)，TE中包含n-1條邊，并使n個(gè)頂點(diǎn)連通，且權(quán)值之和最小。如圖7.8所示，其為在一個(gè)帶權(quán)的連通無(wú)向圖G中，構(gòu)造最小生成樹(shù)的過(guò)程。

為實(shí)現(xiàn)這個(gè)算法需要引入輔助數(shù)組closest[]和lowcost[]記錄從U到V-U的權(quán)值最小的邊。closest[i]=j(i∈V-U,j∈U)，表示頂點(diǎn)i到j(luò)的一條邊(j,i)，同時(shí)(j,i)是U到V-U中的頂點(diǎn)i權(quán)值最小的邊。(j,i)的權(quán)值存放在lowcost[i]中。

圖7.8普里姆算法構(gòu)造最小生成樹(shù)過(guò)程在圖7.8(c)中，U={0,2,5}，V-U={1,3,4}，對(duì)于U-V中的頂點(diǎn)1到U中的頂點(diǎn)的邊有：(0,1)=6，(2,1)=5，(5,1)=∞，所以，U到頂點(diǎn)1權(quán)值最小的邊是(2,1)=5，則closest[1]=2。同樣，可求出closest[3]=5，closest[4]=2。它們所對(duì)應(yīng)的lowcost數(shù)組分別是：lowcost[1]=(2,1)=5，lowcost[3]=(5,3)=2，lowcost[4]=(2,4)=6。圖7.9所示為圖7.8構(gòu)造最小生成樹(shù)過(guò)程中，輔助數(shù)組closest[]和lowcost[]的變化情況，在這里，對(duì)于頂點(diǎn)j∈U，其lowcost[j]=0。頂點(diǎn)編號(hào)：0、1、2、3……

若圖G=(V,E)采用鄰接矩陣表示，鄰接矩陣所對(duì)應(yīng)的二維數(shù)組是cost[MAX，MAX]。則普里姆算法如下：

(1)初始化(U={0}),closest[i]=0;lowcost[i]=cost[0,i];lowcost[0]=0；(i=0,2,…,n-1)。

(2)每次掃描數(shù)組lowcost[]，找出值最小且不為0的lowcost[k]，得到最小生成樹(shù)的一條邊(closest[k],k)，將其輸出；

(3)令lowcost[k]=0，將k并入U(xiǎn)中；

(4)修改數(shù)組closest[i]和lowcost[i]（lowcost[i]<>0及i∈V-U）；

(5)重復(fù)(2)、(3)、(4)，直到U=V（或循環(huán)n-1次）結(jié)束。下標(biāo)i

0

1

2

3

4

5

U

V-U

1closest[i]

0

0

0

0

0

0

{0}{1,2,3,4,5}Lowcost[i]

0

6

1

5∞∞2closest[i]

0

2

0

0

2

2

{0,2}

{1,3,4,5}lowcost[i]

0

5

0

5

6

43closest[i]

0

2

0

5

2

2

{0,2,5}

{1,3,4,}lowcost[i]

0

5

0

2

6

04closest[i]

0

2

0

5

2

2

{0,2,3,5}

{1,4}lowcost[i]

0

5

0

0

6

05closest[i]

0

2

0

5

1

2{0,1,2,3,5}

{4}lowcost[i]

0

0

0

0

3

06closest[i]

0

2

0

5

1

2{0,1,2,3,4,5}

фlowcost[i]

0

0

0

0

0

0圖7.9圖7.8構(gòu)造最小生成樹(shù)過(guò)程中輔助數(shù)組的值

Prim算法求最小生成樹(shù)：procedureprim(v0:integer);

var

lowcost,closest:array[1..maxn]ofinteger;

i,j,k,min:integer;

begin

fori:=1tondobegin{給lowcost[]和closest[]賦初值，此時(shí)U={v0}}

lowcost[i]:=cost[v0,i];{lowcost[i]存放的是頂點(diǎn)I到v0的權(quán)值}

closest[i]:=v0;{closest[i]存放的是v0}

end;

fori:=1ton-1dobegin{尋找離生成樹(shù)最近的未加入頂點(diǎn)k}

min:=maxlongint;

forj:=1tondo

if(lowcost[j]<min)and(lowcost[j]<>0)thenbegin

min:=lowcost[j];k:=j;end;

lowcost[k]:=0;{將頂點(diǎn)k加入生成樹(shù)}forj:=1tondo{修正各點(diǎn)的lowcost和closest值}

ifcost[k,j]<lwocost[j]thenbegin

lowcost[j]:=cost[k,j];

closest[j]:=k;

end;

end;

end;{prim}

(2)克魯斯卡爾(Kruskal)算法該算法是按邊權(quán)值遞增次序,構(gòu)造最小生成樹(shù)的算法。算法描述如下：設(shè)帶權(quán)的連通無(wú)向圖G=(V,E)，有n個(gè)頂點(diǎn)。最小生成樹(shù)的初始狀態(tài)為有n個(gè)頂點(diǎn)但無(wú)邊的非連通圖T=(V,φ)，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。

(1)將E中的邊按權(quán)值的遞增順序排序，選擇權(quán)值最小的邊，若與該邊相關(guān)的頂點(diǎn)落在T中不同連通分量上，則將其加入到T中；否則，將其舍棄。

(2)循環(huán)至所有頂點(diǎn)在同一連通分量上。如何識(shí)別一條邊所相關(guān)的頂點(diǎn)是否落在一個(gè)連通分量上？在此采用集合的方法，即將在一個(gè)連通分量上的所有頂點(diǎn)看成一個(gè)集合。當(dāng)從E中取得一條邊(xi,xj)后，若xi和xj在同一個(gè)集合u中，則將該邊舍棄；否則，則將該邊加入到T中，并將xj所在的集合v并入集合u。為此引入輔助數(shù)組sets[]。圖7.10克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程克魯斯卡爾(Kruskal)算法①初始化：圖G中的n個(gè)頂點(diǎn)，構(gòu)成n個(gè)連通分量。頂點(diǎn)xi對(duì)應(yīng)的連通分量用集合i表示，所以sets[i]=i，即表示第i個(gè)頂點(diǎn)在集合i中。②依次取出的E中的邊(按邊權(quán)值遞增順序)，設(shè)取出的邊(xi,xj)。

③判斷：若sets[i]=sets[j]，則表示xi和xj在同一個(gè)集合中，返回②；否則，xi和xj在不同集合中，則表示xi和xj落在不同連通分量上，轉(zhuǎn)到④。④將邊(xi,xj)并入T，同時(shí)將xj所在集合v(與xj連通的頂點(diǎn))并入xi所在集合u(與xi連通的頂點(diǎn))，即：由v=sets[j]和u=sets[i]，掃描輔助數(shù)組sets[]，若sets[k]=v，則將sets[k]=u。返回②。⑤重復(fù)②、③、④，取出n-1條邊。例如，圖7.10所示為依照克魯斯卡爾算法構(gòu)造一棵最小生成樹(shù)的過(guò)程。sets[]是輔助數(shù)組狀態(tài)?？唆斔箍?Kruskal)算法克魯斯卡爾(Kruskal)算法1、請(qǐng)用標(biāo)記數(shù)組方法和解決該問(wèn)題！2、請(qǐng)用有根樹(shù)的方法解決該問(wèn)題！3、比較兩種處理方法的優(yōu)劣。最短路徑采用圖結(jié)構(gòu)來(lái)表示實(shí)際交通圖，圖中頂點(diǎn)代表城市，邊表示城市之間的交通聯(lián)系，邊上的權(quán)為城市之間的距離，可能有這樣一種問(wèn)題存在。例如，A城到B城是否有通路；A城到B城的哪條通路代價(jià)最低(距離最短)。上述的問(wèn)題就是最短路徑問(wèn)題。這里討論的圖是帶權(quán)有向圖，并稱(chēng)路徑的起始點(diǎn)為源點(diǎn)，路徑的最后端點(diǎn)為終點(diǎn)。下面討論兩種最常見(jiàn)的最短路徑問(wèn)題，并給出最短路徑問(wèn)題的算法。1、求某源點(diǎn)到其余各頂點(diǎn)的最短路徑

定義：給定帶權(quán)值的有向圖G=(V,E)，E中每條弧<u,v>有非負(fù)的權(quán)。指定V中的一個(gè)頂點(diǎn)v作為源點(diǎn)，求從v出發(fā)到G中其余各頂點(diǎn)的最短路徑，被稱(chēng)為單源最短路徑問(wèn)題。

算法：采用迪杰斯特拉(Dijkstra)算法，解決單源最短路徑問(wèn)題。即按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑。圖G采用鄰接矩陣cost[]存儲(chǔ)。把G=(V,E)的頂點(diǎn)集合V劃分成U和V-U，U為從v出發(fā)，已確定最短路徑終點(diǎn)集合，初始狀態(tài)為{v}，V-U為尚未確定最短路徑頂點(diǎn)集合.定義一個(gè)輔助數(shù)組dist[j]：保存從源點(diǎn)v到vj的目前最短路徑長(zhǎng)度，初值為（v,vj）,若v到vj沒(méi)有邊，則權(quán)值為無(wú)窮大。以后每加入一個(gè)新的中間點(diǎn)vk時(shí)，要判斷dist[j]與dist[k]+cost[k,j]的大小，若后者更小，則dist[j]:=dist[k]+cost[k,j].

再定義一個(gè)數(shù)組s,s[j]=1表示節(jié)點(diǎn)vj已經(jīng)加入集合U,s[j]=0表示節(jié)點(diǎn)vj為待加入集合U的節(jié)點(diǎn)。初始時(shí)，除了源點(diǎn)s[v]=1,其它節(jié)點(diǎn)vi對(duì)應(yīng)的s[i]=0;

再定義一個(gè)數(shù)組path[i],用來(lái)表示從源點(diǎn)v到節(jié)點(diǎn)vi所經(jīng)過(guò)的最短路徑上的頂點(diǎn)序列或者邊序列。

算法描述如下：

(1)從S集合以外的頂點(diǎn)（待求出最短路徑的終點(diǎn)）所對(duì)應(yīng)的dist數(shù)組元素中，查找出值最小的元素dist[k],該元素值就是從源點(diǎn)v到vk的最短路徑長(zhǎng)度。Path[k]就是最短路徑上的頂點(diǎn)序列。

(2)將s[k]修改為1（即并入已經(jīng)確定了最短路徑的頂點(diǎn)集合）。

(3)以vk作為新考慮的中間點(diǎn)，對(duì)S[j]=0的所有vj點(diǎn)，比較dist[j]與dist[k]+cost[k,j]的大小，若后者大于前者，則將dist[j]:=dist[k]+dist[k,j],path[j]:=path[m]+j重復(fù)以上運(yùn)算n-2次（第一個(gè)節(jié)點(diǎn)和最和一個(gè)節(jié)點(diǎn)除外），即可在dist[i]數(shù)組中得到源點(diǎn)v到vi的最短路徑，在path數(shù)組中得到相應(yīng)的最短路徑。v1v2v3v4V5s10001Dist01049207Pathv1V1,v2V1,v3V1,v5,v4V1,v52154317107133428495v1v2v3v4V5s11111Dist01027207Pathv1V1,v2V1,v2,v3V1,v5,v4V1,v5v1v2v3v4V5s10000Dist01049∞7Pathv1V1,v2V1,v3V1,v5v1v2v3v4V5s11001Dist01027207Pathv1V1,v2V1,v2,v3V1,v5,v4V1,v5v1v2v3v4V5s11011Dist01027207Pathv1V1,v2V1,v2,v3V1,v5,v4V1,v5Dijkstra算法：Proceduredijkstra(cost,dist,path,i);{求源點(diǎn)vi到其余頂點(diǎn)的最短路徑，cost為圖的鄰接矩陣，dist和path為變量型參數(shù)，其中path基類(lèi)型為集合}Beginforj:=1tonbeginifj<>ithens[j]:=1;dist[j]:=cost[i,j];ifdist[j]<maxintthenpath[j]:=[i]+[j]elsepath[j]:=[];end;fork:=1ton-2dobeginw:=maxint;m:=i;forj:=1tondoif(s[j]=0)and(dist[j]<w)thenm:=j;w:=dist[j];end;ifm<>Ithens[m]:=1elseexit;{剩余重點(diǎn)的dist均為maxint時(shí)，無(wú)需計(jì)算下去}forj:=1tondo{對(duì)s[j]=0的元素的dist做必要修改}if(s[j]=0)and(dist[m]+cost[m,j])thenbegindist[j]:=dist[m]+cost[m,j];path[j]:=path[m]+[j];end;end;End;2、每對(duì)頂點(diǎn)之間的最短路徑對(duì)帶有權(quán)值的有向圖G=(V,E)中任意一對(duì)頂點(diǎn)(u,v)，求u到v的最短路徑，被稱(chēng)為每對(duì)頂點(diǎn)之間的最短路徑問(wèn)題。對(duì)該問(wèn)題的解決有兩種方法：其一，每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法。這樣，便可求得每對(duì)頂點(diǎn)之間的最短路徑?？倳r(shí)間復(fù)雜度為o(n3)。其二，采用弗洛伊德(Floyd)算法，這里主要討論該算法。對(duì)有向圖G，采用帶權(quán)鄰接矩陣cost[]存儲(chǔ)。同時(shí)定義一個(gè)二維數(shù)組A[N，N]，其每一個(gè)分量A[i，j]的值是頂點(diǎn)i到頂點(diǎn)j的最短路徑。弗洛伊德算法的基本思想是：

(1)初始時(shí)，對(duì)圖中任意兩個(gè)頂點(diǎn)vi和vj，如果從vi到vj存在弧，則從vi到vj存在一條長(zhǎng)度為cost[i，j]的路徑，但該路徑不一定是最短路徑，還需要進(jìn)行n次試探，即考慮從vi出發(fā)途經(jīng)vk(k=1,2,…,n)到達(dá)vj是否距離更短。初始化A[i，j]=cost[i，j]（沒(méi)有考慮途經(jīng)其它頂點(diǎn)）。

(2)對(duì)圖中任意兩個(gè)頂點(diǎn)vi和vj之間的路徑，考慮途經(jīng)vk的路徑(vi,vk,vj)是否存在。若存在，則比較途經(jīng)vk是否距離更短，即：比較A[i，k]+A[k，j]和A[i，j](前者為途經(jīng)vk的距離，而后者為沒(méi)有考慮途經(jīng)vk的距離)，較小者送A[i，j]。

(3)重復(fù)(2)，從vi出發(fā)，考慮途經(jīng)vk(k=1,2,3,…,n-1)到達(dá)vj的距離是否更短。

n次比較之后，輔助數(shù)組中的每一個(gè)分量A[i，j]中存放的值，是從vi出發(fā)，已考慮了途經(jīng)圖G中所有頂點(diǎn)，到達(dá)vj的最短路徑。算法時(shí)間復(fù)雜度O(n^3)Floyed(cost,A,p);Beginfori:=1tondoforj:=1tondobegina[I,j]:=cost[I,j];ifa[I,j]<maxintthenp[I,j]:=[i]+[j]elsep[I,j]:=[];end;fork:=1tondo{枚舉所有的中間點(diǎn)}fori:=1tondoforj:=1tondobeginif(i=k)or(j=k)or(i=j)thencontinue;ifa[I,k]+a[k,j]<a[I,j]thenbegina[I,j]:=a[I,k]+a[k,j];p[I,j]:=p[I,j]+p[k,j];end;end;End;具體實(shí)例請(qǐng)見(jiàn)書(shū)上184頁(yè)例題。拓?fù)渑判蛞粋€(gè)無(wú)回環(huán)的有向圖稱(chēng)為有向無(wú)環(huán)圖，簡(jiǎn)稱(chēng)為DAG圖，DAG圖在計(jì)算機(jī)系統(tǒng)，以及工程、管理、經(jīng)濟(jì)領(lǐng)域中有著重要的作用。檢查一個(gè)有向圖是否存在回環(huán)，可以采用拓?fù)渑判蚍椒ㄟM(jìn)行。7.6.1頂點(diǎn)活動(dòng)網(wǎng)(AOV網(wǎng))

實(shí)際應(yīng)用中，常用有向圖來(lái)描述工程的進(jìn)度、系統(tǒng)實(shí)施過(guò)程。工程可以分為若干個(gè)稱(chēng)為活動(dòng)(activity)的子工程，而且這些子工程之間通常有一定的先后關(guān)系。以頂點(diǎn)為活動(dòng)，以有向邊表示先后關(guān)系的有向圖，被稱(chēng)為AOV網(wǎng)。在AOV網(wǎng)中，若從頂點(diǎn)vi到頂點(diǎn)vj有一條有向路徑，則vi是vj的前驅(qū)；vj是vi的后續(xù)。若<vi,vj>是網(wǎng)中一條弧，則vi是vj的直接前驅(qū)；vj是vi的直接后續(xù)。在AOV網(wǎng)中，不應(yīng)該有回環(huán)出現(xiàn)，因?yàn)榇嬖诨丨h(huán)意味著某項(xiàng)活動(dòng)以自身的完成為先決條件。顯然，這是不合理的。所以，對(duì)給定的AOV網(wǎng)，必須檢測(cè)網(wǎng)中是否存在回環(huán)?；丨h(huán)檢測(cè)的方法是：對(duì)有向圖構(gòu)造其頂點(diǎn)拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)湫蛄兄校瑒tAOV必定不存在回環(huán)。課程編號(hào)課程名稱(chēng)先決條件

C1程序設(shè)計(jì)無(wú)

C2離散數(shù)學(xué)

C1

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

C1,C2

C4匯編語(yǔ)言

C1

C5算法分析

C3,C4

C6計(jì)算機(jī)體系結(jié)構(gòu)

C11

C7編譯方法

C5,C3

C8操作系統(tǒng)

C3,C6

C9高等數(shù)學(xué)

C10線性代數(shù)

C9

C11普通物理

C9

C12數(shù)值分析

C9,C10,C1圖7.12課程之間的優(yōu)先關(guān)系以及表示該關(guān)系的AOV網(wǎng)例如，一個(gè)計(jì)算機(jī)軟件專(zhuān)業(yè)的學(xué)生必須學(xué)習(xí)一系列基本課程(如圖7.12(a)所示)，構(gòu)成的AOV網(wǎng)中有如下兩個(gè)拓?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拓?fù)渑判驅(qū)σ粋€(gè)AOV網(wǎng)進(jìn)行拓?fù)渑判蜻^(guò)程，就是在一個(gè)只有部分頂點(diǎn)之間有先后關(guān)系的AOV網(wǎng)中，構(gòu)造一個(gè)任意頂點(diǎn)之間都有先后關(guān)系的線性序列。即：對(duì)任意vi和vj，若它們屬于該線性序列，則vi和vj之間必有先后關(guān)系，可能是vi是vj的(直接)前驅(qū)，也可能vj是vi的(直接)前驅(qū)。例如，圖7.12(b)中，C5和C3,C4,C7之間有先后關(guān)系，而得到的拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8表示C5和任意頂點(diǎn)之間的都有先后關(guān)系，C1,C2,C3,C4是C5的(直接)前驅(qū)，而C5是C7,C9,C10,C11,C6,C12,C8的(直接)前驅(qū)。得到該序列的過(guò)程稱(chēng)為拓?fù)渑判?。拓?fù)渑判虻姆椒ㄈ缦拢?/p>

(1)在AOV網(wǎng)中選擇一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn)，并將其輸出。

(2)從AOV網(wǎng)中刪除該頂點(diǎn)和所有以它為尾的弧。

(3)重復(fù)(1)和(2)，直至所有頂點(diǎn)都被輸出，或者當(dāng)前AOV網(wǎng)中不存在沒(méi)有前驅(qū)（存在有前驅(qū)）的頂點(diǎn)為止。前一種情況表示AOV網(wǎng)中無(wú)回環(huán)存在，而后一種情況則說(shuō)明AOV網(wǎng)中存在回環(huán)。圖7.13AOV網(wǎng)及其拓?fù)溆行蛐蛄挟a(chǎn)生的過(guò)程按上述方法對(duì)圖7.13(a)中所示的AOV網(wǎng)進(jìn)行拓?fù)渑判?，得到的拓?fù)湫蛄袨椋?/p>

v5-v0-v3-v2-v1-v4為了在計(jì)算機(jī)中實(shí)現(xiàn)上述操作，AOV網(wǎng)采用鄰接表作為存儲(chǔ)結(jié)構(gòu)。另外，在鄰接表的頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的數(shù)據(jù)域，入度為0的頂點(diǎn)即為沒(méi)有前驅(qū)的頂點(diǎn)。當(dāng)刪除一條邊后，與該邊相關(guān)聯(lián)的弧頭頂點(diǎn)的入度減1。圖7.14圖7.13(a)的AOV網(wǎng)所對(duì)應(yīng)的鄰接表圖7.13(a)的AOV網(wǎng)所對(duì)應(yīng)的鄰接表如圖7.14所示。用一個(gè)棧存放AOV網(wǎng)中入度為0的頂點(diǎn)。具體算法描述如下：

(1)將鄰接表中所有入度為0的頂點(diǎn)編號(hào)進(jìn)棧（可用入度域）。

(2)棧為空，轉(zhuǎn)到(3)。棧不為空，首先，棧頂元素vi出棧并輸出；然后，在鄰接表中查找以頂點(diǎn)vi為尾的弧<vi,vk>，將頂點(diǎn)vk的入度減1，若頂點(diǎn)vk的入度為0，則頂點(diǎn)vk進(jìn)棧。重復(fù)(2)。

(3)判斷輸出的頂點(diǎn)數(shù)，若不等于n，則AOV網(wǎng)中有回環(huán)存在。拓?fù)渑判蛩惴ǖ木唧w描述為：Proceduretopsort(GL);{Gl為圖的鄰接表}Begintop:=0;fori:=1tondoifGL[i].indegree=0then[g[i].indegree:=top;top:=i];m:=0;{用m記錄輸出頂點(diǎn)的個(gè)數(shù)。}whiletop<>0dobegin(1)j:=top;(2)top:=gl[top].indegree;{退棧}(3)write(gl[j].data);{輸出頂點(diǎn)j的值}(4)m:=m+1;(5)p:=gl[j].link;(6)whilep<>nildobegin(a)k:=p^.adjvex;(b)dec(gl[k].indegree);(c)ifgl[k].indegree=0then[gl[k].indegree:=top;top:=k];(d)p:=p^.next;end;ifm<nthen(‘thenetworkhasacycle’)End;時(shí)間復(fù)雜度分析：n個(gè)頂點(diǎn)和e條邊的AOV網(wǎng)而言，建立鄰接表的時(shí)間為O(e)；搜索入度為0頂點(diǎn)時(shí)間為O(n)；在拓?fù)渑判蛑?，若無(wú)回環(huán)存在，則每個(gè)頂點(diǎn)進(jìn)一次棧，出一次棧，入度減1的操作也總共執(zhí)行e次，所以，總的時(shí)間復(fù)雜度為O(n+e)。例題：士兵排序190頁(yè)請(qǐng)完成該題關(guān)鍵路徑對(duì)整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩個(gè)方面的問(wèn)題：

1）工程能否順利進(jìn)行對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判?/p>

2）估算整個(gè)工程完成所必須的最短時(shí)間對(duì)AOE網(wǎng)求關(guān)鍵路徑AOE-網(wǎng)AOE－網(wǎng)(ActivityOnEdgeNetwork)：即邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖。其中：頂點(diǎn)表示事件（Event）弧表示活動(dòng)（Activity）權(quán)值表示活動(dòng)持續(xù)的時(shí)間通?？捎肁OE網(wǎng)來(lái)估算工程的完成時(shí)間。上圖AOE-網(wǎng)中：共有11項(xiàng)活動(dòng)：a1,a2,a3,…a11；共有9個(gè)事件：v1,v2,v3,…v9，每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開(kāi)始。v9表示整個(gè)工程的結(jié)束v5表示a4和a5已經(jīng)完成，a7和a8可以開(kāi)始與每個(gè)活動(dòng)相聯(lián)系的數(shù)是執(zhí)行該活動(dòng)所需的時(shí)間v1表示整個(gè)工程的開(kāi)始由于整個(gè)工程只有一個(gè)開(kāi)始點(diǎn)和一個(gè)完成點(diǎn)，在正常的情況（無(wú)環(huán)）下，網(wǎng)中只有一個(gè)入度為零的點(diǎn)（稱(chēng)作源點(diǎn)）和一個(gè)出度為零的點(diǎn)（稱(chēng)作匯點(diǎn)）匯點(diǎn)源點(diǎn)依據(jù)AOE-網(wǎng)可以研究什么問(wèn)題？（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？完成工程的最短時(shí)間是從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑。從v1到v9的最長(zhǎng)路徑是（v1,v2,v5,v8,v9），路徑長(zhǎng)度是18。假設(shè)開(kāi)始點(diǎn)是v1，從v1到vi的最長(zhǎng)路徑長(zhǎng)度叫做事件vi的最早發(fā)生時(shí)間。這個(gè)時(shí)間決定了所有以vi為尾的弧所表示的活動(dòng)的最早開(kāi)始時(shí)間。用e(i)表示活動(dòng)ai的最早開(kāi)始時(shí)間。V9的最早發(fā)生時(shí)間是18事件vi的最早發(fā)生時(shí)間

l(i)－e(i)兩者之差意味著完成活動(dòng)ai的時(shí)間余量。我們把l(i)＝e(i)的活動(dòng)叫做關(guān)鍵活動(dòng)。顯然，關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)，因此提前完成非關(guān)鍵活動(dòng)并不能加快工程的進(jìn)度。a6的最早開(kāi)始時(shí)間是5，最遲開(kāi)始時(shí)間是8。如a6推遲3天開(kāi)始或延遲3天完成，都不會(huì)影響整個(gè)工程的完成?；顒?dòng)的最遲開(kāi)始時(shí)間l(i)，這是在不推遲整個(gè)工程完成的前提下，活動(dòng)ai最遲必須開(kāi)始進(jìn)行的時(shí)間。由此可知：辨別關(guān)鍵活動(dòng)就是找e(i)＝l(i)的活動(dòng)。為求得AOE網(wǎng)中活動(dòng)的e(i)和l(i)，首先應(yīng)求得事件的最早發(fā)生時(shí)間ve(j)和最遲發(fā)生時(shí)間vl(j)。若活動(dòng)ai由弧<i,j>表示，持續(xù)時(shí)間記為dut(<i,j>)，則有如下關(guān)系：

活動(dòng)i的最早開(kāi)始時(shí)間等于事件j的最早發(fā)生時(shí)間

e(i)＝ve(i)

活動(dòng)i的最遲開(kāi)始時(shí)間等于事件k的最遲時(shí)間減去活動(dòng)i的持續(xù)時(shí)間

l(i)＝vl(j)-dut(<i，j>)

求ve(j)和vl(j)需分兩步進(jìn)行：aiViVjve[j]和vl[j]可以采用下面的遞推公式計(jì)算：（1）向匯點(diǎn)遞推

ve(源點(diǎn))=0；

ve(j)=Max{ve(i)+dut(<i,j>)}公式意義：從指向頂點(diǎn)Vj的弧的活動(dòng)中取最晚完成的一個(gè)活動(dòng)的完成時(shí)間作為Vj的最早發(fā)生時(shí)間ve[j]pVjVi（2）向源點(diǎn)遞推由上一