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

數(shù)據(jù)結(jié)構(gòu)第七章第1頁(yè)，共133頁(yè)，2023年，2月20日，星期六

圖結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的多對(duì)多的關(guān)系。在這種結(jié)構(gòu)中，任意兩個(gè)元素之間可能存在關(guān)系。即結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。圖的應(yīng)用極為廣泛，已滲入到諸如語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支。第2頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.1

圖的基本概念7.1.1圖的定義和術(shù)語(yǔ)

一個(gè)圖(G)定義為一個(gè)偶對(duì)(V,E)，記為G=(V,E)。其中：V是頂點(diǎn)(Vertex)的非空有限集合，記為V(G)；E是無(wú)序集V&V的一個(gè)子集，記為E(G)，其元素是圖的弧(Arc)。將頂點(diǎn)集合為空的圖稱為空?qǐng)D。其形式化定義為：G=(V，E)V={v|vdataobject}E={<v,w>|v,wV∧p(v,w)}P(v,w)表示從頂點(diǎn)v到頂點(diǎn)w有一條直接通路。第3頁(yè)，共133頁(yè)，2023年，2月20日，星期六

弧(Arc)

：表示兩個(gè)頂點(diǎn)v和w之間存在一個(gè)關(guān)系，用頂點(diǎn)偶對(duì)<v,w>表示。通常根據(jù)圖的頂點(diǎn)偶對(duì)將圖分為有向圖和無(wú)向圖。

有向圖(Digraph)：若圖G的關(guān)系集合E(G)中，頂點(diǎn)偶對(duì)<v,w>的v和w之間是有序的，稱圖G是有向圖。在有向圖中，若<v,w>E(G)，表示從頂點(diǎn)v到頂點(diǎn)w有一條弧。其中：v稱為弧尾(tail)或初始點(diǎn)(initial

node)，w稱為弧頭(head)或終端點(diǎn)(terminalnode)

。

無(wú)向圖(Undigraph)：若圖G的關(guān)系集合E(G)中，頂點(diǎn)偶對(duì)<v,w>的v和w之間是無(wú)序的，稱圖G是無(wú)向圖。第4頁(yè)，共133頁(yè)，2023年，2月20日，星期六在無(wú)向圖中，若<v,w>E(G)，有<w,v>E(G)，即E(G)是對(duì)稱，則用無(wú)序?qū)?v,w)表示v和w之間的一條邊(Edge)，因此(v,w)和(w,v)代表的是同一條邊。例1：設(shè)有有向圖G1和無(wú)向圖G2，形式化定義分別是：G1=(V1，E1)V1={a,b,c,d,e}E1={<a,b>,<a,c>,<a,e>,<c,d>,<c,e>,<d,a>,<d,b>,<e,d>}G2=(V2，E2)V2={a,b,c,d}E2={(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)}它們所對(duì)應(yīng)的圖如圖7-1所示。第5頁(yè)，共133頁(yè)，2023年，2月20日，星期六

完全圖：對(duì)于無(wú)向圖，若圖中頂點(diǎn)數(shù)為n，用e表示邊的數(shù)目，則e[0，n(n-1)/2]。具有n(n-1)/2條邊的無(wú)向圖稱為完全無(wú)向圖。完全無(wú)向圖另外的定義是：對(duì)于無(wú)向圖G=(V，E)，若vi，vj

V，當(dāng)vi≠vj時(shí)，有(vi,vj)E，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條無(wú)向邊，這樣的無(wú)向圖稱為完全圖。abcd(b)無(wú)向圖G2

圖7-1圖的示例(a)有向圖G1

acbde第6頁(yè)，共133頁(yè)，2023年，2月20日，星期六有向完全圖：對(duì)于有向圖，若圖中頂點(diǎn)數(shù)為n，用e表示弧的數(shù)目，則e[0，n(n-1)]。具有n(n-1)條邊的有向圖稱為有向完全圖。完全有向圖另外的定義是：對(duì)于有向圖G=(V，E)，若vi，vjV，當(dāng)vi≠vj時(shí)，有<vi,vj>E∧<vj,

vi>E，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條弧，這樣的有向圖稱為有向完全圖。有很少邊或弧的圖（e<n㏒n）的圖稱為稀疏圖，反之稱為稠密圖。權(quán)(Weight)：與圖的邊和弧相關(guān)的數(shù)。權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。第7頁(yè)，共133頁(yè)，2023年，2月20日，星期六子圖和生成子圖：設(shè)有圖G=(V，E)和G’=(V’，E’)，若V’V且E’E，則稱圖G’是G的子圖；若V’=V且E’E，則稱圖G’是G的一個(gè)生成子圖。頂點(diǎn)的鄰接(Adjacent)：對(duì)于無(wú)向圖G=(V，E)，若邊(v,v’)E，則稱頂點(diǎn)v和v’互為鄰接點(diǎn)，即v和w相鄰接。邊(v,v’)依附(incident)與頂點(diǎn)v和v’。對(duì)于有向圖G=(V，E)，若有向弧<v,w>E，則稱頂點(diǎn)v

“鄰接到”頂點(diǎn)w，頂點(diǎn)w“鄰接自”頂點(diǎn)v，弧<v,w>與頂點(diǎn)v和w

“相關(guān)聯(lián)”。頂點(diǎn)的度、入度、出度：對(duì)于無(wú)向圖G=(V，E)，viV，圖G中依附于vi的邊的數(shù)目稱為頂點(diǎn)vi的度(degree)，記為TD(vi)。第8頁(yè)，共133頁(yè)，2023年，2月20日，星期六

顯然，在無(wú)向圖中，所有頂點(diǎn)度的和是圖中邊的2倍。即∑TD(vi)=2ei=1,2,…,n，e為圖的邊數(shù)。對(duì)有向圖G=(V，E)，若viV，圖G中以vi作為起點(diǎn)的有向邊(弧)的數(shù)目稱為頂點(diǎn)vi的出度(Outdegree)，記為OD(vi)；以vi作為終點(diǎn)的有向邊(弧)的數(shù)目稱為頂點(diǎn)vi的入度(Indegree)，記為ID(vi)。頂點(diǎn)vi的出度與入度之和稱為vi的度，記為TD(vi)。即TD(vi)=OD(vi)+ID(vi)

路徑(Path)、路徑長(zhǎng)度、回路(Cycle)：對(duì)無(wú)向圖G=(V，E)，若從頂點(diǎn)vi經(jīng)過(guò)若干條邊能到達(dá)vj，稱頂點(diǎn)vi和vj是連通的，又稱頂點(diǎn)vi到vj有路徑。對(duì)有向圖G=(V，E)，從頂點(diǎn)vi到vj有有向路徑，指的是從頂點(diǎn)vi經(jīng)過(guò)若干條有向邊(弧)能到達(dá)vj。第9頁(yè)，共133頁(yè)，2023年，2月20日，星期六或路徑是圖G中連接兩頂點(diǎn)之間所經(jīng)過(guò)的頂點(diǎn)序列。即Path=vi0vi1…vim，vijV且(vij-1,vij)Ej=1,2,…,m或Path=vi0vi1…vim，vijV且<vij-1,vij>Ej=1,2,…,m

路徑上邊或有向邊(弧)的數(shù)目稱為該路徑的長(zhǎng)度。在一條路徑中，若沒(méi)有重復(fù)相同的頂點(diǎn)，該路徑稱為簡(jiǎn)單路徑；第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路(環(huán))；在一個(gè)回路中，若除第一個(gè)與最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路(簡(jiǎn)單環(huán))。第10頁(yè)，共133頁(yè)，2023年，2月20日，星期六連通圖、圖的連通分量：對(duì)無(wú)向圖G=(V，E)，若vi，vjV，vi和vj都是連通的，則稱圖G是連通圖，否則稱為非連通圖。若G是非連通圖，則極大的連通子圖稱為G的連通分量。對(duì)有向圖G=(V，E)，若vi，vjV，都有以vi為起點(diǎn)，

vj

為終點(diǎn)以及以vj為起點(diǎn)，vi為終點(diǎn)的有向路徑，稱圖G是強(qiáng)連通圖，否則稱為非強(qiáng)連通圖。若G是非強(qiáng)連通圖，則極大的強(qiáng)連通子圖稱為G的強(qiáng)連通分量。

“極大”的含義：指的是對(duì)子圖再增加圖G中的其它頂點(diǎn)，子圖就不再連通。第11頁(yè)，共133頁(yè)，2023年，2月20日，星期六生成樹、生成森林：一個(gè)連通圖(無(wú)向圖)的生成樹是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)和只有足以構(gòu)成一棵樹的n-1條邊，稱為圖的生成樹，如圖7-2所示。關(guān)于無(wú)向圖的生成樹的幾個(gè)結(jié)論：

◆一棵有n個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊；

◆

如果一個(gè)圖有n個(gè)頂點(diǎn)和小于n-1條邊，則是非連通圖；adbc圖7-2圖G2的一棵生成樹◆

如果多于n-1條邊，則一定有環(huán)；

◆

有n-1條邊的圖不一定是生成樹。第12頁(yè)，共133頁(yè)，2023年，2月20日，星期六

有向圖的生成森林是這樣一個(gè)子圖，由若干棵有向樹組成，含有圖中全部頂點(diǎn)。有向樹是只有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1的有向圖，如圖7-3所示。網(wǎng)：每個(gè)邊(或弧)都附加一個(gè)權(quán)值的圖，稱為帶權(quán)圖。帶權(quán)的連通圖(包括弱連通的有向圖)稱為網(wǎng)或網(wǎng)絡(luò)。網(wǎng)絡(luò)是工程上常用的一個(gè)概念，用來(lái)表示一個(gè)工程或某種流程，如圖7-4所示。圖7-3有向圖及其生成森林abcdedce(a)有向圖(b)生成森林acbcb354126abcde3圖7-4帶權(quán)有向圖第13頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.1.2

圖的抽象數(shù)據(jù)類型定義

圖是一種數(shù)據(jù)結(jié)構(gòu)，加上一組基本操作就構(gòu)成了圖的抽象數(shù)據(jù)類型。圖的抽象數(shù)據(jù)類型定義如下：ADTGraph{數(shù)據(jù)對(duì)象V：具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}VR={<v,w>|<v,w>|v,wV∧p(v,w)，<v,w>表示從v到w的弧，P(v,w)定義了弧<v,w>的信息}第14頁(yè)，共133頁(yè)，2023年，2月20日，星期六基本操作P：Create_Graph()：圖的創(chuàng)建操作。初始條件：無(wú)。操作結(jié)果：生成一個(gè)沒(méi)有頂點(diǎn)的空?qǐng)DG。GetVex(G,v)：求圖中的頂點(diǎn)v的值。初始條件：圖G存在，v是圖中的一個(gè)頂點(diǎn)。操作結(jié)果：生成一個(gè)沒(méi)有頂點(diǎn)的空?qǐng)DG。

…

…DFStraver(G,V)：從v出發(fā)對(duì)圖G深度優(yōu)先遍歷。初始條件：圖G存在。操作結(jié)果：對(duì)圖G深度優(yōu)先遍歷，每個(gè)頂點(diǎn)訪問(wèn)且只訪問(wèn)一次。第15頁(yè)，共133頁(yè)，2023年，2月20日，星期六??BFStraver(G,V)：從v出發(fā)對(duì)圖G廣度優(yōu)先遍歷。初始條件：圖G存在。操作結(jié)果：對(duì)圖G廣度優(yōu)先遍歷，每個(gè)頂點(diǎn)訪問(wèn)且只訪問(wèn)一次。}ADTGraph詳見p156~157。第16頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.2

圖的存儲(chǔ)結(jié)構(gòu)

圖的存儲(chǔ)結(jié)構(gòu)比較復(fù)雜，其復(fù)雜性主要表現(xiàn)在：◆任意頂點(diǎn)之間可能存在聯(lián)系，無(wú)法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系?！魣D中頂點(diǎn)的度不一樣，有的可能相差很大，若按度數(shù)最大的頂點(diǎn)設(shè)計(jì)結(jié)構(gòu)，則會(huì)浪費(fèi)很多存儲(chǔ)單元，反之按每個(gè)頂點(diǎn)自己的度設(shè)計(jì)不同的結(jié)構(gòu)，又會(huì)影響操作。圖的常用的存儲(chǔ)結(jié)構(gòu)有：鄰接矩陣、鄰接鏈表、十字鏈表、鄰接多重表。第17頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.2.1鄰接矩陣(數(shù)組)表示法基本思想：對(duì)于有n個(gè)頂點(diǎn)的圖，用一維數(shù)組vexs[n]存儲(chǔ)頂點(diǎn)信息，用二維數(shù)組A[n][n]存儲(chǔ)頂點(diǎn)之間關(guān)系的信息。該二維數(shù)組稱為鄰接矩陣。在鄰接矩陣中，以頂點(diǎn)在vexs數(shù)組中的下標(biāo)代表頂點(diǎn)，鄰接矩陣中的元素A[i][j]存放的是頂點(diǎn)i到頂點(diǎn)j之間關(guān)系的信息。第18頁(yè)，共133頁(yè)，2023年，2月20日，星期六1無(wú)向圖的數(shù)組表示(1)無(wú)權(quán)圖的鄰接矩陣

無(wú)向無(wú)權(quán)圖G=(V，E)有n(n≧1)個(gè)頂點(diǎn)，其鄰接矩陣是n階對(duì)稱方陣，如圖7-5所示。其元素的定義如下：1若(vi,vj)E，即vi,vj鄰接0若(vi,vj)E，即vi,vj不鄰接A[i][j]=(a)無(wú)向圖

abcd圖7-5無(wú)向無(wú)權(quán)圖的數(shù)組存儲(chǔ)(b)頂點(diǎn)矩陣vexsabcd0111101111011110(c)鄰接矩陣第19頁(yè)，共133頁(yè)，2023年，2月20日，星期六(2)帶權(quán)圖的鄰接矩陣

無(wú)向帶權(quán)圖G=(V，E)的鄰接矩陣如圖7-6所示。其元素的定義如下：(a)帶權(quán)無(wú)向圖

(b)頂點(diǎn)矩陣圖7-6無(wú)向帶權(quán)圖的數(shù)組存儲(chǔ)(c)鄰接矩陣354126abcde3vexsabcde∞62∞∞6∞34323∞1∞∞43∞5∞3∞5∞Wij

若(vi,vj)E，即vi,vj鄰接，權(quán)值為wij∞若(vi,vj)E，即vi,vj不鄰接時(shí)A[i][j]=第20頁(yè)，共133頁(yè)，2023年，2月20日，星期六(3)

無(wú)向圖鄰接矩陣的特性◆鄰接矩陣是對(duì)稱方陣；

◆

對(duì)于頂點(diǎn)vi，其度數(shù)是第i行的非0元素的個(gè)數(shù)；

◆

無(wú)向圖的邊數(shù)是上(或下)三角形矩陣中非0元素個(gè)數(shù)。2有向圖的數(shù)組表示(1)無(wú)權(quán)圖的鄰接矩陣

若有向無(wú)權(quán)圖G=(V，E)有n(n≧1)個(gè)頂點(diǎn)，則其鄰接矩陣是n階對(duì)稱方陣，如圖7-7所示。元素定義如下：1若<vi,vj>E，從vi到vj有弧A[i][j]=0若<vi,vj>E從vi到vj沒(méi)有弧第21頁(yè)，共133頁(yè)，2023年，2月20日，星期六(a)有向圖acbde圖7-7有向無(wú)權(quán)圖的數(shù)組存儲(chǔ)(b)頂點(diǎn)矩陣vexsabcde(c)鄰接矩陣0110100000000111100000010(2)帶權(quán)圖的鄰接矩陣

有向帶權(quán)圖G=(V，E)的鄰接矩陣如圖7-8所示。其元素的定義如下：wij

若<vi,vj>E，即vi,vj鄰接，權(quán)值為wij∞若<vi,vj>E，即vi,vj不鄰接時(shí)A[i][j]=第22頁(yè)，共133頁(yè)，2023年，2月20日，星期六圖7-8帶權(quán)有向圖的數(shù)組存儲(chǔ)(b)頂點(diǎn)矩陣vexsabcde(c)鄰接矩陣∞62∞∞∞∞

∞

∞

3∞

3∞1∞∞4

∞∞5∞∞

∞∞∞(a)帶權(quán)有向圖

354126abcde3⑶有向圖鄰接矩陣的特性◆對(duì)于頂點(diǎn)vi，第i行的非0元素的個(gè)數(shù)是其出度OD(vi)；第i列的非0元素的個(gè)數(shù)是其入度ID(vi)?！?/p>

鄰接矩陣中非0元素的個(gè)數(shù)就是圖的弧的數(shù)目。第23頁(yè)，共133頁(yè)，2023年，2月20日，星期六3圖的鄰接矩陣的操作

圖的鄰接矩陣的實(shí)現(xiàn)比較容易，定義兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)信息(數(shù)據(jù)元素)和邊或弧的信息(數(shù)據(jù)元素之間的關(guān)系)。其存儲(chǔ)結(jié)構(gòu)形式定義如下：#defineINFINITYMAX_VAL/*最大值∞*//*根據(jù)圖的權(quán)值類型，分別定義為最大整數(shù)或?qū)崝?shù)*/#defineMAX_VEX30/*最大頂點(diǎn)數(shù)目*/typedefenum{DG,AG,WDG,WAG}GraphKind;/*{有向圖，無(wú)向圖，帶權(quán)有向圖，帶權(quán)無(wú)向圖}*/第24頁(yè)，共133頁(yè)，2023年，2月20日，星期六#defineVEX_NUM20typedefcharVextype；

typedefstruct{

Vextypevexs[VEX_NUM];

intadj[VEX_NUM][VEX_NUM];/*鄰接矩陣*/

intn,e;/*頂點(diǎn)數(shù)和邊數(shù)*/

}Mgragh;

第25頁(yè)，共133頁(yè)，2023年，2月20日，星期六voidCreateMGraph(Mgragh*G){inti,j,k,w;charch;printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):\n");scanf("%d,%d",&(G->n),&(G->e));/*輸入*/printf("請(qǐng)輸入頂點(diǎn)信息:\n");

for(i=0;i<G->n;i++)

scanf("%c",&(G->vexs[i]));

for(i=0;i<G->n;i++)

for(j=0;j<G->n;j++)G->adj[i][j]=0;/*初始化鄰接矩陣*/

printf("輸入每條邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)的序號(hào):\n");

for(k=0;k<G->e;k++){

scanf("%d,%d",&i,&j);/*輸入e條邊*/

G->adj[i][j]=1;G->adj[j][i]=1;/*對(duì)稱加入,無(wú)向圖的鄰接矩陣存儲(chǔ)建立*/}

}/*CreateMGraph*/第26頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.2.2

鄰接鏈表法

基本思想：對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息。每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。第i個(gè)單鏈表表示依附于頂點(diǎn)Vi的邊(對(duì)有向圖是以頂點(diǎn)Vi為頭或尾的弧)。第27頁(yè)，共133頁(yè)，2023年，2月20日，星期六1結(jié)點(diǎn)結(jié)構(gòu)與鄰接鏈表示例

鏈表中的結(jié)點(diǎn)稱為表結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)由三個(gè)域組成，如圖7-9(a)所示。其中鄰接點(diǎn)域(adjvex)指示與頂點(diǎn)Vi鄰接的頂點(diǎn)在圖中的位置(頂點(diǎn)編號(hào))，鏈域(nextarc)指向下一個(gè)與頂點(diǎn)Vi鄰接的表結(jié)點(diǎn)，數(shù)據(jù)域(info)存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。對(duì)于無(wú)權(quán)圖，如果沒(méi)有與邊相關(guān)的其他信息，可省略此域。每個(gè)鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)(稱為頂點(diǎn)結(jié)點(diǎn))，由兩個(gè)域組成，如圖7-9(b)所示。鏈域(firstarc)指向鏈表中的第一個(gè)結(jié)點(diǎn)，數(shù)據(jù)域(data)存儲(chǔ)頂點(diǎn)名或其他信息。adjvexnextarc

info表結(jié)點(diǎn)：datafirstarc頂點(diǎn)結(jié)點(diǎn)：圖7-9鄰接鏈表結(jié)點(diǎn)結(jié)構(gòu)第28頁(yè)，共133頁(yè)，2023年，2月20日，星期六在圖的鄰接鏈表表示中，所有頂點(diǎn)結(jié)點(diǎn)用一個(gè)向量以順序結(jié)構(gòu)形式存儲(chǔ)，可以隨機(jī)訪問(wèn)任意頂點(diǎn)的鏈表，該向量稱為表頭向量，向量的下標(biāo)指示頂點(diǎn)的序號(hào)。用鄰接鏈表存儲(chǔ)圖時(shí)，對(duì)無(wú)向圖，其鄰接鏈表是唯一的，如圖7-10所示；對(duì)有向圖，其鄰接鏈表有兩種形式，如圖7-11所示。圖7-10無(wú)向圖及其鄰接鏈表v1v2v3v4v501234MAX_VEX-1v1

v2v3

v4┇┇v5

213?02?0314?204?23?第29頁(yè)，共133頁(yè)，2023年，2月20日，星期六(a)有向圖v1v2v3v4v513?014?2?3?01234MAX_VEX-1v12v20?v33v41┇┇┇v51(b)正鄰接鏈表，出度直觀2?02?2?01234MAX_VEX-1v11v22v31v42┇┇┇v513?04?(c)逆鄰接鏈表，入度直觀圖7-11有向圖及其鄰接鏈表第30頁(yè)，共133頁(yè)，2023年，2月20日，星期六2

鄰接表法的特點(diǎn)

◆表頭向量中每個(gè)分量就是一個(gè)單鏈表的頭結(jié)點(diǎn)，分量個(gè)數(shù)就是圖中的頂點(diǎn)數(shù)目；

◆在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲(chǔ)空間；

◆在無(wú)向圖，頂點(diǎn)Vi的度是第i個(gè)鏈表的結(jié)點(diǎn)數(shù)；◆

對(duì)有向圖可以建立正鄰接表或逆鄰接表。正鄰接表是以頂點(diǎn)Vi為出度(即為弧的起點(diǎn))而建立的鄰接表；逆鄰接表是以頂點(diǎn)Vi為入度(即為弧的終點(diǎn))而建立的鄰接表；◆

在有向圖中，第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)是頂點(diǎn)Vi的出(或入)度；求入(或出)度，須遍歷整個(gè)鄰接表；第31頁(yè)，共133頁(yè)，2023年，2月20日，星期六◆

在鄰接表上容易找出任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)；3結(jié)點(diǎn)及其類型定義typedefstructnode{/*邊結(jié)點(diǎn)*/

intadjvex;/*鄰接點(diǎn)域*/

structnode*nextarc;/*指向下一個(gè)邊結(jié)點(diǎn)的指針域*/

}EdgeNode;

typedefstructvnode{

Vextypevertex;

EdgeNode*firstedge;

}VertexNode;

typedefstruct{

VertexNodeadjlist[MAXSIZE];

intn,e;

}ALGraph;第32頁(yè)，共133頁(yè)，2023年，2月20日，星期六利用上述的存儲(chǔ)結(jié)構(gòu)描述，可方便地實(shí)現(xiàn)圖的基本操作。圖的創(chuàng)建voidCreateALGraph(ALGraph*G)

{/*建立有向圖的鄰接表存儲(chǔ)*/

inti,j,k;

EdgeNode*s;

printf(“請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：\n”);

scanf(“%d,%d”,&(G->n),&(G->e));

第33頁(yè)，共133頁(yè)，2023年，2月20日，星期六

printf(“請(qǐng)輸入頂點(diǎn)信息：\n”);

for(i=0;i<G->n;i++){

scanf(“%c”,&(G->adjlist[i].vertex));

G->adjlist[i].firstedge=NULL;

}

printf(“請(qǐng)輸入邊的信息：\n”);

for(k=0;k<G->e;k++){/*建立邊表*/

scanf(“%d,%d”,&i,&j);

/在頭結(jié)點(diǎn)和邊結(jié)點(diǎn)之間插入新的邊結(jié)點(diǎn)

s=(EdgeNode*)malloc(sizeof(EdgeNode));

s->adjvex=j;

s->nextarc=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;

}

}/*CreateALGraph*/第34頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.2.3

十字鏈表法

十字鏈表(OrthogonalList)是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是將有向圖的正鄰接表和逆鄰接表結(jié)合起來(lái)得到的一種鏈表。在這種結(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)的鏈表中。這種結(jié)構(gòu)的結(jié)點(diǎn)邏輯結(jié)構(gòu)如圖7-12所示。弧結(jié)點(diǎn)tailvexheadvex

hlinktlink

info頂點(diǎn)結(jié)點(diǎn)Datafirstinfirstout圖7-12十字鏈表結(jié)點(diǎn)結(jié)構(gòu)第35頁(yè)，共133頁(yè)，2023年，2月20日，星期六◆

data域：存儲(chǔ)和頂點(diǎn)相關(guān)的信息；◆

指針域firstin：指向以該頂點(diǎn)為弧頭的第一條弧所對(duì)應(yīng)的弧結(jié)點(diǎn)；◆指針域firstout：指向以該頂點(diǎn)為弧尾的第一條弧所對(duì)應(yīng)的弧結(jié)點(diǎn)；◆尾域tailvex：指示弧尾頂點(diǎn)在圖中的位置；◆頭域headvex：指示弧頭頂點(diǎn)在圖中的位置；◆指針域hlink：指向弧頭相同的下一條弧；◆指針域tlink：指向弧尾相同的下一條??；◆

Info域：指向該弧的相關(guān)信息；第36頁(yè)，共133頁(yè)，2023年，2月20日，星期六結(jié)點(diǎn)類型定義#defineINFINITYMAX_VAL/*最大值∞*/#defineMAX_VEX30//最大頂點(diǎn)數(shù)typedefstructArcNode{inttailvex,headvex;//尾結(jié)點(diǎn)和頭結(jié)點(diǎn)在圖中的位置InfoTypeinfo;//與弧相關(guān)的信息,如權(quán)值structArcNode*hlink,*tlink;}ArcNode;/*弧結(jié)點(diǎn)類型定義*/typedefstructVexNode{VexTypedata;//頂點(diǎn)信息ArcNode*firstin,*firstout;}VexNode;/*頂點(diǎn)結(jié)點(diǎn)類型定義*/第37頁(yè)，共133頁(yè)，2023年，2月20日，星期六typedefstruct{intvexnum;VexNodexlist[MAX_VEX];}OLGraph;/*圖的類型定義*/

圖7-13所示是一個(gè)有向圖及其十字鏈表(略去了表結(jié)點(diǎn)的info域)。從這種存儲(chǔ)結(jié)構(gòu)圖可以看出，從一個(gè)頂點(diǎn)結(jié)點(diǎn)的firstout出發(fā)，沿表結(jié)點(diǎn)的tlink指針構(gòu)成了正鄰接表的鏈表結(jié)構(gòu)，而從一個(gè)頂點(diǎn)結(jié)點(diǎn)的firstin出發(fā)，沿表結(jié)點(diǎn)的hlink指針構(gòu)成了逆鄰接表的鏈表結(jié)構(gòu)。第38頁(yè)，共133頁(yè)，2023年，2月20日，星期六V0V1V2V30102∧2023∧∧30∧31∧32∧∧0213V0V1∧V2V3圖7-13有向圖的十字鏈表結(jié)構(gòu)第39頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.2.4

鄰接多重表

鄰接多重表(AdjacencyMultilist)是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鄰接表是無(wú)向圖的一種有效的存儲(chǔ)結(jié)構(gòu)，在無(wú)向圖的鄰接表中，一條邊(v,w)的兩個(gè)表結(jié)點(diǎn)分別初選在以v和w為頭結(jié)點(diǎn)的鏈表中，很容易求得頂點(diǎn)和邊的信息，但在涉及到邊的操作會(huì)帶來(lái)不便。鄰接多重表的結(jié)構(gòu)和十字鏈表類似，每條邊用一個(gè)結(jié)點(diǎn)表示；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)與鄰接表中的完全相同，而表結(jié)點(diǎn)包括六個(gè)域如圖7-14所示。datafirstedge頂點(diǎn)結(jié)點(diǎn)圖7-14鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)markivexilinkjvexjlink

info第40頁(yè)，共133頁(yè)，2023年，2月20日，星期六◆

Data域：存儲(chǔ)和頂點(diǎn)相關(guān)的信息；◆

指針域firstedge：指向依附于該頂點(diǎn)的第一條邊所對(duì)應(yīng)的表結(jié)點(diǎn)；◆

標(biāo)志域mark：用以標(biāo)識(shí)該條邊是否被訪問(wèn)過(guò)；◆

ivex和jvex域：分別保存該邊所依附的兩個(gè)頂點(diǎn)在圖中的位置；◆

info域：保存該邊的相關(guān)信息；◆

指針域ilink：指向下一條依附于頂點(diǎn)ivex的邊；◆

指針域jlink：指向下一條依附于頂點(diǎn)jvex的邊；第41頁(yè)，共133頁(yè)，2023年，2月20日，星期六結(jié)點(diǎn)類型定義#defineINFINITYMAX_VAL/*最大值∞*/#defineMAX_VEX30/*最大頂點(diǎn)數(shù)*/typedefemnu{unvisited,visited}Visitting;typedefstructEdgeNode{Visittingmark;//訪問(wèn)標(biāo)記intivex,jvex;//該邊依附的兩個(gè)結(jié)點(diǎn)在圖中的位置InfoTypeinfo;//與邊相關(guān)的信息,如權(quán)值structEdgeNode*ilink,*jlink;

//分別指向依附于這兩個(gè)頂點(diǎn)的下一條邊}EdgeNode;/*弧邊結(jié)點(diǎn)類型定義*/第42頁(yè)，共133頁(yè)，2023年，2月20日，星期六typedefstructVexNode{VexTypedata;//頂點(diǎn)信息ArcNode*firsedge;//指向依附于該頂點(diǎn)的第一條邊}VexNode;/*頂點(diǎn)結(jié)點(diǎn)類型定義*/typedefstruct{intvexnum;VexNodemullist[MAX_VEX];}AMGraph;

圖7-15所示是一個(gè)無(wú)向圖及其鄰接多重表。第43頁(yè)，共133頁(yè)，2023年，2月20日，星期六鄰接多重表與鄰接表的區(qū)別：

后者的同一條邊用兩個(gè)表結(jié)點(diǎn)表示，而前者只用一個(gè)表結(jié)點(diǎn)表示；除標(biāo)志域外，鄰接多重表與鄰接表表達(dá)的信息是相同的，因此，操作的實(shí)現(xiàn)也基本相似。圖7-15無(wú)向圖及其多重鄰接鏈表v1v2v3v4v1v2v3v40123

01

02∧

21∧

23

0∧3∧第44頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.3

圖的遍歷圖的遍歷(TraveringGraph)：從圖的某一頂點(diǎn)出發(fā)，訪遍圖中的其余頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次。圖的遍歷算法是各種圖的操作的基礎(chǔ)?！魪?fù)雜性：圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，可能在訪問(wèn)了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原頂點(diǎn)。◆解決辦法：在遍歷過(guò)程中記下已被訪問(wèn)過(guò)的頂點(diǎn)。設(shè)置一個(gè)輔助向量Visited[1…n](n為頂點(diǎn)數(shù))，其初值為0，一旦訪問(wèn)了頂點(diǎn)vi后，使Visited[i]為1或?yàn)樵L問(wèn)的次序號(hào)。圖的遍歷算法有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)結(jié)構(gòu)是(正)鄰接鏈表。第45頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.3.1深度優(yōu)先搜索算法深度優(yōu)先搜索(DepthFirstSearch--DFS)遍歷類似樹的先序遍歷，是樹的先序遍歷的推廣。1

算法思想設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，則：⑴

：從圖中某個(gè)頂點(diǎn)vi出發(fā)，訪問(wèn)vi；然后找到vi的一個(gè)鄰接頂點(diǎn)vi1；⑵：從vi1出發(fā)，深度優(yōu)先搜索訪問(wèn)和vi1相鄰接且未被訪問(wèn)的所有頂點(diǎn)；⑶：轉(zhuǎn)⑴

，直到和vi相鄰接的所有頂點(diǎn)都被訪問(wèn)為止第46頁(yè)，共133頁(yè)，2023年，2月20日，星期六圖7-17無(wú)向圖深度優(yōu)先搜索遍歷(a)無(wú)向圖Gv1v2v3v4v5(b)G的鄰接鏈表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21?20?01?4?3?⑷：繼續(xù)選取圖中未被訪問(wèn)頂點(diǎn)vj作為起始頂點(diǎn)，轉(zhuǎn)(1)，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。圖7-17是無(wú)向圖的深度優(yōu)先搜索遍歷示例(紅色箭頭)。某種DFS次序是：v1→

v3→

v2→

v4→

v5第47頁(yè)，共133頁(yè)，2023年，2月20日，星期六2

算法實(shí)現(xiàn)

由算法思想知，這是一個(gè)遞歸過(guò)程。因此，先設(shè)計(jì)一個(gè)從某個(gè)頂點(diǎn)(編號(hào))為v0開始深度優(yōu)先搜索的函數(shù)，便于調(diào)用。在遍歷整個(gè)圖時(shí)，可以對(duì)圖中的每一個(gè)未訪問(wèn)的頂點(diǎn)執(zhí)行所定義的函數(shù)。typedefemnu{FALSE,TRUE}BOOLEAN;BOOLEANVisited[MAX_VEX];第48頁(yè)，共133頁(yè)，2023年，2月20日，星期六采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷voidDFS_traverse(ALGraph*G){

intv;for(v=0;v<G->vexnum;v++)Visited[v]=FALSE;/*訪問(wèn)標(biāo)志初始化*/

p=G->AdjList[v].firstarc;

for(v=0;v<G->vexnum;v++)

if(!Visited[v])DFS(G,v);}第49頁(yè)，共133頁(yè)，2023年，2月20日，星期六voidDFS(ALGraph*G,intv){EdgeNode*p;Visited[v]=TRUE;

Visit[v];/*置訪問(wèn)標(biāo)志，訪問(wèn)頂點(diǎn)v*/p=G->AdjList[v].firstarc;/*鏈表的第一個(gè)結(jié)點(diǎn)*/while(p!=NULL){if(!Visited[p->adjvex])

DFS(G,p->adjvex);/*從v的未訪問(wèn)過(guò)的鄰接頂點(diǎn)出發(fā)深度優(yōu)先搜索*/p=p->nextarc;}}第50頁(yè)，共133頁(yè)，2023年，2月20日，星期六3算法分析

遍歷時(shí)，對(duì)圖的每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù)。其實(shí)質(zhì)就是對(duì)每個(gè)頂點(diǎn)查找鄰接頂點(diǎn)的過(guò)程，取決于存儲(chǔ)結(jié)構(gòu)。當(dāng)圖有e條邊，其時(shí)間復(fù)雜度為O(e)，總時(shí)間復(fù)雜度為O(n+e)。第51頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.3.2廣度優(yōu)先搜索算法

廣度優(yōu)先搜索(BreadthFirstSearch--BFS)遍歷類似樹的按層次遍歷的過(guò)程。1

算法思想設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，則：⑴

：從圖中某個(gè)頂點(diǎn)vi出發(fā)，訪問(wèn)vi；⑵：訪問(wèn)vi的所有相鄰接且未被訪問(wèn)的所有頂點(diǎn)vi1，vi2，…，vim；⑶：以vi1，vi2，…，vim的次序，以vij(1≦j≦m)依此作為vi，轉(zhuǎn)⑴；第52頁(yè)，共133頁(yè)，2023年，2月20日，星期六⑷

：繼續(xù)選取圖中未被訪問(wèn)頂點(diǎn)vk作為起始頂點(diǎn)，轉(zhuǎn)⑴，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。圖7-18是有向圖的廣度優(yōu)先搜索遍歷示例(紅色箭頭)。上述圖的BFS次序是：v1→

v2→

v4→

v3→

v5(b)G’的正鄰接鏈表13?014?2?3?01234MAX_VEX-1v12v20?v33v41┇┇┇v51圖7-18有向圖廣度優(yōu)先搜索遍歷(a)有向圖G’v1v2v3v4v5第53頁(yè)，共133頁(yè)，2023年，2月20日，星期六2

算法實(shí)現(xiàn)

為了標(biāo)記圖中頂點(diǎn)是否被訪問(wèn)過(guò)，同樣需要一個(gè)訪問(wèn)標(biāo)記數(shù)組；其次，使用隊(duì)列來(lái)存儲(chǔ)已被訪問(wèn)的頂點(diǎn)的次序，以確定下一層頂點(diǎn)的訪問(wèn)順序。采用鄰接矩陣存儲(chǔ)的圖的廣度優(yōu)先遍歷第54頁(yè)，共133頁(yè)，2023年，2月20日，星期六void

BFSTraverse(Graph

G,

Status

(*Visit)(int

v)){//連通圖G廣度優(yōu)先搜索

for

(v=0;

v<G.vexnum;

++v)

visited[v]

=

FALSE;

//初始化訪問(wèn)標(biāo)志

InitQueue(

Q

);

//置空的輔助隊(duì)列

for

(v=0;

v<G.vexnum;

++v)

if(!visited[v]){

//

v未訪問(wèn)

visited[v]=TRUE;

Visit(v);

EnQueue(Q,

v);

//

v入隊(duì)列

while

(!QueueEmpty(Q))

{

DeQueue(Q,

u);

//

隊(duì)頭元素出隊(duì)并置為u

For(w=FirstAdjVex(G,u);w>=0;NextAdjVex(G,u,w))

if

(

!

visited[w]){

//w為u尚未訪問(wèn)的鄰接頂點(diǎn)

visited[w]=TRUE;

Visit(w);

EnQueue(Q,

w);

//訪問(wèn)的頂點(diǎn)w入隊(duì)列

}

//

if

}

//

while}

//

BFSTraverse第55頁(yè)，共133頁(yè)，2023年，2月20日，星期六算法分析：在廣度優(yōu)先遍歷算法中，每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。因此廣度優(yōu)先遍歷圖和深度優(yōu)先遍歷在相同的存儲(chǔ)結(jié)構(gòu)下的時(shí)間復(fù)雜度是相同的.用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索算法遍歷圖的唯一區(qū)別是鄰接點(diǎn)搜索次序不同，因此，廣度優(yōu)先搜索算法遍歷圖的總時(shí)間復(fù)雜度為O(n+e)。圖的遍歷可以系統(tǒng)地訪問(wèn)圖中的每個(gè)頂點(diǎn)，因此，圖的遍歷算法是圖的最基本、最重要的算法，許多有關(guān)圖的操作都是在圖的遍歷基礎(chǔ)之上加以變化來(lái)實(shí)現(xiàn)的。第56頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.4

圖的連通性問(wèn)題

本節(jié)所討論的內(nèi)容是圖的遍歷算法的具體應(yīng)用。7.4.1無(wú)向圖的連通分量與生成樹1無(wú)向圖的連通分量和生成樹

對(duì)于無(wú)向圖，對(duì)其進(jìn)行遍歷時(shí)：◆

若是連通圖：僅需從圖中任一頂點(diǎn)出發(fā)，就能訪問(wèn)圖中的所有頂點(diǎn)；◆

若是非連通圖：需從圖中多個(gè)頂點(diǎn)出發(fā)。每次從一個(gè)新頂點(diǎn)出發(fā)所訪問(wèn)的頂點(diǎn)集序列恰好是各個(gè)連通分量的頂點(diǎn)集；第57頁(yè)，共133頁(yè)，2023年，2月20日，星期六(a)無(wú)向圖Gv1v2v3v4v5(b)G的鄰接鏈表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21?20?01?4?3?圖7-19無(wú)向圖及深度優(yōu)先生成森林(c)深度優(yōu)先生成森林v1v2v3v4v5

如圖7-19所示的無(wú)向圖是非連通圖，按圖中給定的鄰接表進(jìn)行深度優(yōu)先搜索遍歷，2次調(diào)用DFS所得到的頂點(diǎn)訪問(wèn)序列集是：{v1,v3,v2}和{v4,v5}第58頁(yè)，共133頁(yè)，2023年，2月20日，星期六

⑴若G=(V,E)是無(wú)向連通圖，頂點(diǎn)集和邊集分別是V(G)，E(G)。若從G中任意點(diǎn)出發(fā)遍歷時(shí)，E(G)被分成兩個(gè)互不相交的集合：T(G)：遍歷過(guò)程中所經(jīng)過(guò)的邊的集合；B(G)：遍歷過(guò)程中未經(jīng)過(guò)的邊的集合；顯然：E(G)=T(G)∪B(G)，T(G)∩B(G)=?

顯然，圖G’=(V,T(G))是G的極小連通子圖，且G’是一棵樹。G’稱為圖G的一棵生成樹。從任意點(diǎn)出發(fā)按DFS算法得到生成樹G’稱為深度優(yōu)先生成樹；按BFS算法得到的G’稱為廣度優(yōu)先生成樹。第59頁(yè)，共133頁(yè)，2023年，2月20日，星期六

⑵

若G=(V,E)是無(wú)向非連通圖，對(duì)圖進(jìn)行遍歷時(shí)得到若干個(gè)連通分量的頂點(diǎn)集：V1(G),V2(G),…,Vn(G)和相應(yīng)所經(jīng)過(guò)的邊集：T1(G),T2(G),…,Tn(G)。則對(duì)應(yīng)的頂點(diǎn)集和邊集的二元組：Gi=(Vi(G),Ti(G))(1≦i≦n)是對(duì)應(yīng)分量的生成樹，所有這些生成樹構(gòu)成了原來(lái)非連通圖的生成森林。說(shuō)明：當(dāng)給定無(wú)向圖要求畫出其對(duì)應(yīng)的生成樹或生成森林時(shí)，必須先給出相應(yīng)的鄰接表，然后才能根據(jù)鄰接表畫出其對(duì)應(yīng)的生成樹或生成森林。第60頁(yè)，共133頁(yè)，2023年，2月20日，星期六2圖的生成樹和生成森林算法

對(duì)圖的深度優(yōu)先搜索遍歷DFS(或BFS)算法稍作修改，就可得到構(gòu)造圖的DFS生成樹算法。

在算法中，樹的存儲(chǔ)結(jié)構(gòu)采用孩子—兄弟表示法。首先建立從某個(gè)頂點(diǎn)V出發(fā)，建立一個(gè)樹結(jié)點(diǎn)，然后再分別以V的鄰接點(diǎn)為起始點(diǎn)，建立相應(yīng)的子生成樹，并將其作為V結(jié)點(diǎn)的子樹鏈接到V結(jié)點(diǎn)上。顯然，算法是一個(gè)遞歸算法。算法實(shí)現(xiàn)：typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;第61頁(yè)，共133頁(yè)，2023年，2月20日，星期六圖的生成森林算法Void

DFSForest(GraphG,CSTree

&T){

//建立無(wú)向圖左孩子右兄弟鏈表TT=NULL;for(v=0;v<G.vexnum;++v)

visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v]){

//v為新的生成樹的根結(jié)點(diǎn)p=(CSTree)malloc(sizeof(CSNode));*p={GetVex(G,w),NULL,NULL);

//給該結(jié)點(diǎn)賦值if(!T)T=p;

//是第一個(gè)樹的根elseq->nextsibling=p;

//是其他樹的根,(第一個(gè)根的兄弟)q=p;

//q指示當(dāng)前生成樹的根

DFSTree(G,v,p)

//建立以p為根的生成樹}

//建立以P為根的生成樹}第62頁(yè)，共133頁(yè)，2023年，2月20日，星期六DFStree算法Void

DFStree(Graph

G,intv,CSTree

&T)

{Visited[v]=TRUE,first=TRUE;for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visted[w]){p=(CSTree)malloc(sizeof(CSNode));

//分配孩子結(jié)點(diǎn)*p={GetVex(G,w),NULL,NULL);if(first){

//w是第一個(gè)未被訪問(wèn)的鄰接點(diǎn)T->lchild=p;

first=FALSE//建立根左孩子結(jié)點(diǎn)

else

//

w是其他未被訪問(wèn)的鄰接點(diǎn)

q->nextsibling=p;

//w是上一個(gè)鄰接點(diǎn)的兄弟結(jié)點(diǎn)

}

q=p;

DFSTree(G,W,q);//從第w頂點(diǎn)出發(fā)遍歷圖,建立子生成樹q}//if}//DFSTree

第63頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.4.2

有向圖的強(qiáng)連通分量

對(duì)于有向圖，在其每一個(gè)強(qiáng)連通分量中，任何兩個(gè)頂點(diǎn)都是可達(dá)的。VG，與V可相互到達(dá)的所有頂點(diǎn)就是包含V的強(qiáng)連通分量的所有頂點(diǎn)。設(shè)從V可到達(dá)(以V為起點(diǎn)的所有有向路徑的終點(diǎn))的頂點(diǎn)集合為T1(G)，而到達(dá)V(以V為終點(diǎn)的所有有向路徑的起點(diǎn))的頂點(diǎn)集合為T2(G)，則包含V的強(qiáng)連通分量的頂點(diǎn)集合是：

T1(G)∩T2(G)。求有向圖G的強(qiáng)連通分量的基本步驟是：⑴對(duì)G進(jìn)行深度優(yōu)先遍歷，生成G的深度優(yōu)先生成森林T。⑵對(duì)森林T的頂點(diǎn)按中序遍歷順序進(jìn)行編號(hào)。第64頁(yè)，共133頁(yè)，2023年，2月20日，星期六⑶改變G中每一條弧的方向，構(gòu)成一個(gè)新的有向圖G’。⑷按⑵中標(biāo)出的頂點(diǎn)編號(hào)，從編號(hào)最大的頂點(diǎn)開始對(duì)G’進(jìn)行深度優(yōu)先搜索，得到一棵深度優(yōu)先生成樹。若一次完整的搜索過(guò)程沒(méi)有遍歷G’的所有頂點(diǎn)，則從未訪問(wèn)的頂點(diǎn)中選擇一個(gè)編號(hào)最大的頂點(diǎn)，由它開始再進(jìn)行深度優(yōu)先搜索，并得到另一棵深度優(yōu)先生成樹。在該步驟中，每一次深度優(yōu)先搜索所得到的生成樹中的頂點(diǎn)就是G的一個(gè)強(qiáng)連通分量的所有頂點(diǎn)。⑸重復(fù)步驟⑷，直到G’中的所有頂點(diǎn)都被訪問(wèn)。如圖7-20(a)是求一棵有向樹的強(qiáng)連通分量過(guò)程。第65頁(yè)，共133頁(yè)，2023年，2月20日，星期六dacfeb(a)有向圖G654321dacfeb(b)執(zhí)行步驟(1)和(2)acdfeb(c)執(zhí)行步驟(3)adcbef(d)執(zhí)行步驟(4)和(5)圖7-20利用深度優(yōu)先搜索求有向圖的強(qiáng)連通分量

在算法實(shí)現(xiàn)時(shí)，建立一個(gè)數(shù)組in_order[n]存放深度優(yōu)先生成森林的中序遍歷序列。對(duì)每個(gè)頂點(diǎn)v，在調(diào)用DFS函數(shù)結(jié)束時(shí)，將頂點(diǎn)依次存放在數(shù)組in_order[n]中。圖采用十字鏈表作為存儲(chǔ)結(jié)構(gòu)最合適。算法實(shí)現(xiàn)：intin_order[MAX_VEX];第66頁(yè)，共133頁(yè)，2023年，2月20日，星期六voidDFS(OLGraph*G,intv)//按弧的正向搜索{ArcNode*p;Count=0;Visited[v]=TRUE;for(p=G->xlist[v].firstout;p!=NULL;p=p->tlink)if(!Visited[p->headvex])DFS(G,p->headvex);in_order[count++]=v;}第67頁(yè)，共133頁(yè)，2023年，2月20日，星期六voidRev_DFS(OLGraph*G,intv){ArcNode*p;Visited[v]=TRUE;printf(“%d”,v);/*輸出頂點(diǎn)*/for(p=G->xlist[v].firstin;p!=NULL;p=p->hlink)if(!Visited[p->tailvex])Rev_DFS(G,p->tailvex);}/*對(duì)圖G按弧的逆向進(jìn)行搜索*/voidConnected_DG(OLGraph*G){intk=1,v,j;for(v=0;v<G->vexnum;v++)Visited[v]=FALSE;第68頁(yè)，共133頁(yè)，2023年，2月20日，星期六for(v=0;v<G->vexnum;v++)/*對(duì)圖G正向遍歷*/if(!Visited[v])DFS(G,v);for(v=0;v<G->vexnum;v++)Visited[v]=FALSE;for(j=G->vexnum-1;j>=0;j--)/*對(duì)圖G逆向遍歷*/{v=in_order[j];if(!Visited[v]){printf(“\n第%d個(gè)連通分量頂點(diǎn):”,k++);Rev_DFS(G,v);}}}第69頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.5

最小生成樹

如果連通圖是一個(gè)帶權(quán)圖，則其生成樹中的邊也帶權(quán)，生成樹中所有邊的權(quán)值之和稱為生成樹的代價(jià)。

最小生成樹(MinimumSpanningTree)：帶權(quán)連通圖中代價(jià)最小的生成樹稱為最小生成樹。最小生成樹在實(shí)際中具有重要用途，如設(shè)計(jì)通信網(wǎng)。設(shè)圖的頂點(diǎn)表示城市，邊表示兩個(gè)城市之間的通信線路，邊的權(quán)值表示建造通信線路的費(fèi)用。n個(gè)城市之間最多可以建n(n-1)/2條線路，如何選擇其中的n-1條，使總的建造費(fèi)用最低?

構(gòu)造最小生成樹的算法有許多，基本原則是：第70頁(yè)，共133頁(yè)，2023年，2月20日，星期六構(gòu)造最小生成樹的算法有許多，基本原則是：◆盡可能選取權(quán)值最小的邊，但不能構(gòu)成回路；◆選擇n-1條邊構(gòu)成最小生成樹。以上的基本原則是基于MST的如下性質(zhì)：設(shè)G=(V，E)是一個(gè)帶權(quán)連通圖，U是頂點(diǎn)集V的一個(gè)非空子集。若u∈U，v∈V-U，且(u,v)是U中頂點(diǎn)到V-U中頂點(diǎn)之間權(quán)值最小的邊，則必存在一棵包含邊(u,v)的最小生成樹。第71頁(yè)，共133頁(yè)，2023年，2月20日，星期六證明：

用反證法證明。設(shè)圖G的任何一棵最小生成樹都不包含邊(u,v)。設(shè)T是G的一棵生成樹，則T是連通的，從u到v必有一條路徑(u,…,v)，當(dāng)將邊(u,v)加入到T中時(shí)就構(gòu)成了回路。則路徑(u,…,v)中必有一條邊(u’,v’)，滿足u’∈U，v’∈V-U。刪去邊(u’,v’)便可消除回路，同時(shí)得到另一棵生成樹T’。由于(u,v)是U中頂點(diǎn)到V-U中頂點(diǎn)之間權(quán)值最小的邊，故(u,v)的權(quán)值不會(huì)高于(u’,v’)的權(quán)值，T’的代價(jià)也不會(huì)高于T，T’是包含(u,v)的一棵最小生成樹，與假設(shè)矛盾。第72頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.5.1普里姆(Prim)算法

從連通網(wǎng)N=(U，E)中找最小生成樹T=(U，TE)

。1算法思想⑴若從頂點(diǎn)v0出發(fā)構(gòu)造，U={v0}，TE={}；⑵

先找權(quán)值最小的邊(u，v)，其中u∈U且v∈V-U，并且子圖不構(gòu)成環(huán)，則U=U∪{v}，TE=TE∪{(u，v)}

；⑶

重復(fù)⑵

，直到U=V為止。則TE中必有n-1條邊，

T=(U，TE)就是最小生成樹。如圖7-21所提示。第73頁(yè)，共133頁(yè)，2023年，2月20日，星期六v1v3v2v4v54857121136(a)v2v45(b)(c)v53v2v45(d)v14v53v2v45v36(e)v14v53v2v45圖7-21按prime算法從v2出發(fā)構(gòu)造最小生成樹的過(guò)程第74頁(yè)，共133頁(yè)，2023年，2月20日，星期六2算法實(shí)現(xiàn)說(shuō)明

設(shè)用鄰接矩陣(二維數(shù)組)表示圖，兩個(gè)頂點(diǎn)之間不存在邊的權(quán)值為機(jī)內(nèi)允許的最大值。為便于算法實(shí)現(xiàn)，設(shè)置一個(gè)一維數(shù)組closedge[n]，用來(lái)保存V-U中各頂點(diǎn)到U中頂點(diǎn)具有權(quán)值最小的邊。數(shù)組元素的類型定義是：struct{intadjvex;/*邊所依附于U中的頂點(diǎn)*/intlowcost;/*該邊的權(quán)值*/}closedge[MAX_EDGE];第75頁(yè)，共133頁(yè)，2023年，2月20日，星期六例如：closedge[j].adjvex=k，表明邊(vj,vk)是V-U中頂點(diǎn)vj到U中權(quán)值最小的邊，而頂點(diǎn)vk是該邊所依附的U中的頂點(diǎn)。closedge[j].lowcost存放該邊的權(quán)值。假設(shè)從頂點(diǎn)vs開始構(gòu)造最小生成樹。初始時(shí)令：Closedge[s].lowcost=0

：表明頂點(diǎn)vs首先加入到U中；Closedge[k].adjvex=s

，Closedge[k].lowcost=cost(k,s)

表示V-U中的各頂點(diǎn)到U中權(quán)值最小的邊(k≠s)，cost(k,s)表示邊(vk,vs)

權(quán)值。第76頁(yè)，共133頁(yè)，2023年，2月20日，星期六3算法步驟⑴從closedge中選擇一條權(quán)值(不為0)最小的邊(vk,vj)，然后做：①置closedge[k].lowcost為0，表示vk已加入到U中。②

根據(jù)新加入vk的更新closedge中每個(gè)元素：

vi∈V-U，若cost(i,k)≦colsedge[i].lowcost，表明在U中新加入頂點(diǎn)vk后，(vi,vk)成為vi到U中權(quán)值最小的邊，置：Closedge[i].lowcost=cost(i,k)Closedge[i].adjvex=k

⑵

重復(fù)⑴n-1次就得到最小生成樹。如表7-1所提示。第77頁(yè)，共133頁(yè)，2023年，2月20日，星期六

在Prime算法中，圖采用鄰接矩陣存儲(chǔ)，所構(gòu)造的最小生成樹用一維數(shù)組存儲(chǔ)其n-1條邊，每條邊的存儲(chǔ)結(jié)構(gòu)描述：算法實(shí)現(xiàn)VoidMiniSpanTree_Prim(MgraphG,VertexTypeu)/*從第u個(gè)頂點(diǎn)開始構(gòu)造圖G的最小生成樹*/{k=LocateVex(G,u);

for(j=0;j<G.vexnum;++j）//輔助數(shù)組初始化if(j!=k)closedge[j]={u,G.arcs[k][j].adj;}//adjvex,lowcoseclosedge[k].lowcose=0;//初始,U={u}for(i=1;j<G.vexnum;++j){//選擇其余頂點(diǎn)k=minimum(closedge);//求出T的下一個(gè)結(jié)點(diǎn)，第k個(gè)//此時(shí)closedge[k].lowcost=MIN{closedge[vi].lowcost|closedge[vi].lowcost>0,vi∈V-U}第78頁(yè)，共133頁(yè)，2023年，2月20日，星期六

printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹的邊closedge[k].lowcose=0;//第K點(diǎn)并入U(xiǎn)集合for(j=0;j<G.vexnum;++j）

if（G.arcs[k][j].adj<closedge[j].Lowcose)Closedge[j]={G.vexs[k],G.arcs[k][j].adj};}}//MiniSpanTree

第79頁(yè)，共133頁(yè)，2023年，2月20日，星期六

iclosedge01234UV-UKadjvexlwcostv28v2

7v25v212{v2}{v1,v3,v4,v5}3adjvexlwcostv44v27v20v43{v2,v4}{v1,v3,v5}4adjvexlwcostv44v56v20v40{v2,v4,v5}{v1,v3}0adjvexlwcostv40v56v20v40{v2,v4,v5,v1}{v3}2adjvexlwcostv40v50v20v40{v2,v4,v5,v1,v3}{}表7-1構(gòu)造過(guò)程中輔組數(shù)組closedge中各分量的值的變化情況第80頁(yè)，共133頁(yè)，2023年，2月20日，星期六算法分析：設(shè)帶權(quán)連通圖有n個(gè)頂點(diǎn)，則算法的主要執(zhí)行是二重循環(huán)：求closedge中權(quán)值最小的邊，頻度為n-1；修改closedge數(shù)組，頻度為n。因此，整個(gè)算法的時(shí)間復(fù)雜度是O(n2)，與邊的數(shù)目無(wú)關(guān)。第81頁(yè)，共133頁(yè)，2023年，2月20日，星期六7.5.2克魯斯卡爾(Kruskal)算法1

算法思想設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是其最小生成樹。初值：U=V，TE={}。對(duì)G中的邊按權(quán)值大小從小到大依次選取。⑴選取權(quán)值最小的邊(vi，vj)，若邊(vi，vj)加入到TE后形成回路，則舍棄該邊(邊(vi，vj)；否則，將該邊并入到TE中，即TE=TE∪{(vi，vj)}。⑵

重復(fù)⑴

，直到TE中包含有n-1條邊為止