超級(jí)盤(pán)數(shù)據(jù)結(jié)構(gòu)七章圖

7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)表示7.3圖的遍歷7.4.1最小生成樹(shù)7.4圖的應(yīng)用7.4.2最短路徑7.4.3拓?fù)渑判?.4.4關(guān)鍵路徑第七章圖柯尼斯堡七橋問(wèn)題歐拉定理:對(duì)于一個(gè)連通圖，如果它的奇點(diǎn)(通過(guò)此點(diǎn)邊的條數(shù)是奇數(shù))個(gè)數(shù)為0或2，則能不重復(fù)的遍歷每一條邊，否則則不能。圖的應(yīng)用領(lǐng)域：電路分析、最短路徑、工程規(guī)劃、化合物分類(lèi)、統(tǒng)計(jì)力學(xué)、自動(dòng)化、語(yǔ)言學(xué)、社會(huì)科學(xué)，等等。圖結(jié)構(gòu)是最廣泛使用的數(shù)學(xué)結(jié)構(gòu)。圖是由一個(gè)頂點(diǎn)集V和一個(gè)弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。Graph=(V,R)V={x|x∈GElemSet}集合V中的所有元素具有相同的特性R={VR}其中，VR＝{<v,w>|v,w∈V}

<v,w>表示從v到w的一條弧(Arc)，并稱(chēng)v為弧尾(Tail)，w為弧頭(Head)。圖的結(jié)構(gòu)定義:vw7.1圖的定義和術(shù)語(yǔ)

由于“弧”是有方向的，因此稱(chēng)由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。

ABECD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}若<v,w>VR必有<w,v>VR,則稱(chēng)

(v,w)為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊。

BCADFE由頂點(diǎn)集和邊集構(gòu)成的圖稱(chēng)作無(wú)向圖。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}名詞和術(shù)語(yǔ)網(wǎng)、子圖

完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹(shù)、生成森林ABECFAEFBBC設(shè)圖G=(V,{VR})和圖G=(V,{VR}),且VV,VRVR,則稱(chēng)G為G的子圖。1597211132

弧或邊帶權(quán)的圖分別稱(chēng)作有向網(wǎng)或無(wú)向網(wǎng)。圖G圖G

假設(shè)圖中有

n

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

條邊，則

含有e=n(n-1)/2條邊的無(wú)向圖稱(chēng)作完全圖；

含有e=n(n-1)條弧的有向圖稱(chēng)作

有向完全圖；若邊或弧的個(gè)數(shù)e<nlogn，則稱(chēng)作稀疏圖，否則稱(chēng)作稠密圖。

假若頂點(diǎn)v和頂點(diǎn)w之間存在一條邊，則稱(chēng)頂點(diǎn)v和w互為鄰接點(diǎn)，ACDFE例如:ID(B)=3ID(A)=2邊(v,w)

和頂點(diǎn)v和w相關(guān)聯(lián)。

和頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目定義為邊的度。B頂點(diǎn)的出度:以頂點(diǎn)v為弧尾的弧的數(shù)目；ABECF對(duì)有向圖來(lái)說(shuō)，頂點(diǎn)的入度:以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3設(shè)圖G=(V,{VR})中的一個(gè)頂點(diǎn)序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,則稱(chēng)從頂點(diǎn)u到頂點(diǎn)w之間存在一條路徑。路徑上邊的數(shù)目稱(chēng)作路徑長(zhǎng)度。ABECF如:長(zhǎng)度為3的路徑{A,B,C,F}簡(jiǎn)單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡(jiǎn)單回路:序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱(chēng)此無(wú)向圖為連通圖（如圖1）；若無(wú)向圖為非連通圖（如圖2），則圖中各個(gè)極大連通子圖稱(chēng)作此圖的連通分量。BACDFEBACDFE圖G1圖G2若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱(chēng)此有向圖為強(qiáng)連通圖（如圖1）。ABECFABECF對(duì)有向圖，否則，其各個(gè)強(qiáng)連通子圖稱(chēng)作它的強(qiáng)連通分量（如圖2）。圖G1圖G2

例:有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)的情況)。

假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱(chēng)該極小連通子圖為此連通圖的生成樹(shù)。對(duì)非連通圖，則稱(chēng)由各個(gè)連通分量的生成樹(shù)的集合為此非連通圖的生成森林。BACDFE結(jié)構(gòu)的建立和銷(xiāo)毀插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問(wèn)操作遍歷插入和刪除弧基本操作CreatGraph(&G,V,VR)://按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷(xiāo)毀圖結(jié)構(gòu)的建立和銷(xiāo)毀對(duì)頂點(diǎn)的訪問(wèn)操作LocateVex(G,u);

//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在//圖中“位置”

；否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對(duì)v賦值value。對(duì)鄰接點(diǎn)的操作FirstAdjVex(G,v);

//返回v的“第一個(gè)鄰接點(diǎn)”。若該頂點(diǎn)//在G中沒(méi)有鄰接點(diǎn)，則返回“空”。NextAdjVex(G,v,w);

//返回v的（相對(duì)于w的）“下一個(gè)鄰接//點(diǎn)”。若w是v的最后一個(gè)鄰接點(diǎn)，則//返回“空”。插入或刪除頂點(diǎn)InsertVex(&G,v);

//在圖G中增添新頂點(diǎn)v。DeleteVex(&G,v);//刪除G中頂點(diǎn)v及其相關(guān)的弧。插入和刪除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是無(wú)向的，//則還增添對(duì)稱(chēng)弧<w,v>。DeleteArc(&G,v,w);

//在G中刪除弧<v,w>，若G是無(wú)向的，//則還刪除對(duì)稱(chēng)弧<w,v>。遍歷DFSTraverse(G,v,Visit());//從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每//個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());

//從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對(duì)每//個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。7.2圖的存儲(chǔ)表示一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示Aij={0(i,j)VR1(i,j)VR一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示BACDFE定義:矩陣的元素為易于判定兩頂點(diǎn)間是否有邊（弧）、易求頂點(diǎn)的度無(wú)向圖的鄰接矩陣為對(duì)稱(chēng)矩陣對(duì)無(wú)權(quán)圖，用1或0表示相鄰否有向圖的鄰接矩陣為非對(duì)稱(chēng)矩陣ABECFV1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010V20001V30001V41000

V1V2V3V4

V1

0111V21001V31000V41100應(yīng)用：1.結(jié)點(diǎn)間是否有關(guān)聯(lián)2.求結(jié)點(diǎn)的度在有向圖中：頂點(diǎn)出度=行中非零元素的個(gè)數(shù)。頂點(diǎn)入度=列中非零元素的個(gè)數(shù)。在無(wú)向圖中：頂點(diǎn)的度數(shù)=矩陣中對(duì)應(yīng)該頂點(diǎn)的行或列中非零元素的個(gè)數(shù)。特點(diǎn)：無(wú)向圖的關(guān)聯(lián)矩陣是對(duì)稱(chēng)矩陣V1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010V20001V30001V41000

V1V2V3V4

V1

0111V21001V31000V41100入度出度11112101度數(shù)3212優(yōu)點(diǎn)：增減邊的操作簡(jiǎn)單缺點(diǎn)：增減頂點(diǎn)的操作需要搬移大量的元素；稀疏圖時(shí)浪費(fèi)存儲(chǔ)空間對(duì)帶權(quán)圖：求值矩陣應(yīng)用：需對(duì)關(guān)聯(lián)結(jié)點(diǎn)間的值進(jìn)行運(yùn)算的問(wèn)題城市交通圖typedefintVRType;//

VRType是頂點(diǎn)關(guān)系類(lèi)型typedefstructArcCell{//弧的定義VRTypeadj;//VRType是頂點(diǎn)關(guān)系類(lèi)型。//對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；//對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型。InfoType*info;//該弧相關(guān)信息的指針（可無(wú)）}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefcharVertexType;//頂點(diǎn)信息（如頂點(diǎn)名稱(chēng)、頂點(diǎn)坐標(biāo)等，因圖而異）typedefstruct{//圖的定義VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)向量-AdjMatrixarcs;//鄰接矩陣-弧的信息intvexnum,arcnum;//頂點(diǎn)數(shù)，弧數(shù)GraphKindkind;//圖的種類(lèi)標(biāo)志}MGraph;0A141B0452C353D254E015F123BACDFE二、圖的鄰接表存儲(chǔ)表示優(yōu)點(diǎn):節(jié)省存儲(chǔ)空間邊的插入和刪除操作比較簡(jiǎn)便缺點(diǎn):結(jié)構(gòu)復(fù)雜

具有兩種不同的基本組成單元應(yīng)用：適于結(jié)點(diǎn)多，邊少advexnextarcinfodatafirstarc表頭結(jié)點(diǎn)弧結(jié)點(diǎn)typedefstructArcNode//弧的結(jié)點(diǎn)結(jié)構(gòu){intadjvex;//該弧的終點(diǎn)位置structArcNode*nextarc;//指向下一條弧的指針

InfoTypeinfo;//該弧的相關(guān)信息}ArcNode;typedefstructVnode//鄰接表頭結(jié)點(diǎn){Vertexdata;//頂點(diǎn)信息

ArcNode*firstarc;//指向第一條弧}VNode;typedefstruct{AdjListadjlist; //鄰接表intvexnum,arcnum;//頂點(diǎn)數(shù)和邊數(shù)}ALGraph;

//圖的類(lèi)型VNodeArcNodetypedefVNode

AdjList[MAXV]; //AdjList是鄰接表類(lèi)型AdjList鄰接表142301201234ABCDE有向圖的鄰接表

ABECF可見(jiàn)，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。ABECD有向圖的逆鄰接表ABCDE303420

01234在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。易于判定任一頂點(diǎn)的鄰接點(diǎn)7.3圖的遍歷

從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程。深度優(yōu)先搜索廣度優(yōu)先搜索

從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到。一、深度優(yōu)先搜索遍歷圖連通圖的深度優(yōu)先搜索遍歷Vw1SG1SG2SG3W1、W2和W3

均為V的鄰接點(diǎn)，SG1、SG2和SG3分別為含頂點(diǎn)W1、W2和W3

的子圖。訪問(wèn)頂點(diǎn)V：for(W1、W2、W3)

若該鄰接點(diǎn)W未被訪問(wèn)，

則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。w2w3w2深度優(yōu)先搜索遍歷遍歷類(lèi)似于樹(shù)的先根遍歷如何判別V的鄰接點(diǎn)是否被訪問(wèn)？為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問(wèn)標(biāo)志visited[w]”。首先將圖中每個(gè)頂點(diǎn)的訪問(wèn)標(biāo)志設(shè)為FALSE,之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問(wèn)，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先搜索遍歷voidDFSTraverse(GraphG,void(*Visit)(VertexType)){

//初始條件：圖G存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。算法7.4//操作結(jié)果：從第1個(gè)頂點(diǎn)起，深度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次intv;VisitFunc=Visit;//使用全局變量VisitFunc，使DFS不必設(shè)函數(shù)指針參數(shù)

for(v=0;v<G.vexnum;v++)//對(duì)圖G的所有頂點(diǎn)visite[v]=FALSE;//訪問(wèn)標(biāo)志數(shù)組初始化(未被訪問(wèn))

for(v=0;v<G.vexnum;v++)//對(duì)圖G的所有頂點(diǎn)if(!visite[v])//頂點(diǎn)v尚未被訪問(wèn)

DFS(G,v);

//對(duì)尚未訪問(wèn)的序號(hào)為v的頂點(diǎn)調(diào)用DFSprintf("\n");}voidDFS(GraphG,intv){//從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G。算法7.5（在同一連通（子）圖中遍歷。）intw;visite[v]=TRUE;//設(shè)置訪問(wèn)標(biāo)志為T(mén)RUE(已訪問(wèn))VisitFunc(GetVex(G,v));//訪問(wèn)第v個(gè)頂點(diǎn)for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))//從頂點(diǎn)v的第1個(gè)鄰接頂點(diǎn)w開(kāi)始if(!visite[w])DFS(G,w);

//對(duì)v的尚未訪問(wèn)的序號(hào)為w的鄰接頂點(diǎn)遞歸調(diào)用DFS(訪問(wèn)w)}連通圖的深度優(yōu)先搜索遍歷abchdk

e

fgFFFFFFFFFTTTTTTTTTachdefk

bgachefk

dbg訪問(wèn)標(biāo)志:訪問(wèn)次序:例如:012345678F=0T=1visite[v]=TRUE;VisitFunc(GetVex(G,v));for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visite[w])DFS(G,w);二、廣度優(yōu)先搜索遍歷圖Vw1w8w3w7w6w2w5w4對(duì)連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑。其中，V->w1,V->w2,V->w8

的路徑長(zhǎng)度為1；V->w7,V->w3,V->w5

的路徑長(zhǎng)度為2；V->w6,V->w4

的路徑長(zhǎng)度為3。w1Vw2w7w6w3w8w5w4從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問(wèn)此頂點(diǎn)之后依次訪問(wèn)V0的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。00000visited[]初始態(tài)

voidBFSTraverse(GraphG,Status(*Visit)(intv)){//廣度優(yōu)先搜索遍歷圖

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

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

for(v=0;v<G.vexnum;++v)//對(duì)于所有頂點(diǎn)

if(

!visited[v])

{

//v尚未訪問(wèn)visited[v]=TRUE;Visit(v

);//訪問(wèn)vEnQueue(Q,v);

//v入隊(duì)列while(!QueueEmpty(Q)){

DeQueue(Q,u);//隊(duì)頭元素出隊(duì)并置為ufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))

if

(!visited[w])

{

visited[w]=TRUE;Visit(w);EnQueue(Q,w);

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

}//if}//while}

//

}//BFSTraverse7.4.1最小生成樹(shù)7.4圖的應(yīng)用7.4.2最短路徑7.4.3拓?fù)渑判?.4.4關(guān)鍵路徑7.4.1(連通網(wǎng)的)最小生成樹(shù)

假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？問(wèn)題：構(gòu)造網(wǎng)的一棵最小生成樹(shù)(MST)

，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）該問(wèn)題等價(jià)于：算法一：（普里姆算法）構(gòu)造網(wǎng)的一棵最小生成樹(shù)(MST)

在生成樹(shù)的構(gòu)造過(guò)程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集U

和尚未落在生成樹(shù)上的頂點(diǎn)集V-U，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。UV-U最小生成樹(shù)有如下重要性質(zhì)：設(shè)N=(V,{E})是一連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若（u,v）是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U，則存在一棵包含邊（u,v）的最小生成樹(shù)。uvabcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹(shù)權(quán)值和=14+8+3+5+16+21=67

取圖中任意一個(gè)頂點(diǎn)v作為生成樹(shù)的根，之后往生成樹(shù)上添加新的頂點(diǎn)w。在添加的頂點(diǎn)w和已經(jīng)在生成樹(shù)上的頂點(diǎn)v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v和w之間的邊中取值最小。之后繼續(xù)往生成樹(shù)上添加頂點(diǎn)，直至生成樹(shù)上含有n-1個(gè)頂點(diǎn)為止。普里姆算法思想abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c55for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=k)

{

closedge[j]={u,G.arcs[k][j].adj};k=minimum(closedge);//求出加入生成樹(shù)的下一個(gè)頂點(diǎn)(k)

printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹(shù)上一條邊closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集lowcost[k].lowcost=0;/ /標(biāo)記k已經(jīng)加入U(xiǎn)

for(j=0;j<G.vexnum;++j)//修改其它頂點(diǎn)的最小邊

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};0設(shè)置一個(gè)輔助數(shù)組closedge[]，對(duì)當(dāng)前V－U集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：voidMiniSpanTree_P(MGraphG,VertexType

u){//用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)k=LocateVex(G,u);//頂點(diǎn)u的序號(hào)

for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=k)

{closedge[j].adjvex=k;//頂點(diǎn)u的序號(hào)賦給closedge[j].adjvex

closedge[j].lowcost=G.arcs[k][j].adj;//頂點(diǎn)u到頂點(diǎn)j的權(quán)值

}//書(shū)中closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0;//初始，U＝{u}

for(i=0;i<G.vexnum;++i){//

選擇其余G.vexnum-1個(gè)頂點(diǎn)k=minimum(closedge);//求出加入生成樹(shù)的下一個(gè)頂點(diǎn)(k)

printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹(shù)上一條邊closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集for(j=0;j<G.vexnum;++j)//修改其它頂點(diǎn)的最小邊

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};}}具體做法:先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。考慮問(wèn)題的出發(fā)點(diǎn):為使生成樹(shù)上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄篴bcdegf195141827168213ae12dcbgf7148531621例如:7121819普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法7.4.2最短路徑求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑

每一對(duì)頂點(diǎn)之間的最短路徑

求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想:依最短路徑的長(zhǎng)度遞增的次序求得各條路徑源點(diǎn)v1…其中，從源點(diǎn)到頂點(diǎn)v的最短路徑是所有最短路徑中長(zhǎng)度最短者。v2采用狄克斯特拉(Dijkstra)算法求解基本思想是：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖,把圖中頂點(diǎn)集合V分成兩組：第一組為已求出最短路徑的頂點(diǎn)集合(用S表示,初始時(shí)S中只有一個(gè)源點(diǎn),以后每求得一條最短路徑v,…vk,就將vk加入到集合S中,直到全部頂點(diǎn)都加入到S中,算法就結(jié)束了)第二組為其余未確定最短路徑的頂點(diǎn)集合(用U表示)。它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。路徑長(zhǎng)度最短的最短路徑的特點(diǎn)：求最短路徑的迪杰斯特拉算法：。設(shè)置輔助數(shù)組:一維數(shù)組Dist[i]：紀(jì)錄從源點(diǎn)v0到頂點(diǎn)vi的當(dāng)前最短路徑。一維數(shù)組path[i]：紀(jì)錄從源點(diǎn)v0到終點(diǎn)vi的當(dāng)前最短路徑上vi的直接前驅(qū)頂點(diǎn)序號(hào)。一維數(shù)組S[i]：紀(jì)錄從源點(diǎn)v0到終點(diǎn)vi是否已被確定最短路徑長(zhǎng)度.S U dist[]path[]01234560123456{0} {1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,0,0,0,-1,-1,-1}{0,1}{2,3,4,5,6}{0,4,5,6,11,∞,∞}{0,0,1,0,1,-1,-1}{0,1,2}{3,4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3}{4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,0,1,0,5,2,5}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}尋找序號(hào)為v的頂點(diǎn)到所有其它頂點(diǎn)的最短路徑(1)初始時(shí),S只包含源點(diǎn),即S={v},v的距離為0。U包含除v外的其他頂點(diǎn),U中頂點(diǎn)u距離為邊上的權(quán)(若v與u有邊<v,u>)或∞(若u不是v的出邊鄰接點(diǎn))。(2)從U中選取一個(gè)距離v最小的頂點(diǎn)k,把k加入S中(該選定的距離就是v到k的最短路徑長(zhǎng)度)。(3)以k為新考慮的中間點(diǎn),修改U中各頂點(diǎn)的距離：若從源點(diǎn)v到頂點(diǎn)u(u∈U)的距離(經(jīng)過(guò)頂點(diǎn)k)比原來(lái)距離(不經(jīng)過(guò)頂點(diǎn)k)短,則修改頂點(diǎn)u的距離值,修改后的距離值的頂點(diǎn)k的距離加上邊<k,u>上的權(quán)。

for(i=0;i<g.n;i++){dist[i]=g.arcs[v][i];/*距離初始化*/s[i]=0;/*s[]置空*/if(g.arcs[v][i]<INF) /*路徑初始化*/path[i]=v;elsepath[i]=-1;}s[v]=1;path[v]=0; /*源點(diǎn)編號(hào)v放入s中*/mindis=INF;k=-1;for(j=0;j<g.n;j++)//選取不在s中且具有最小距離的頂點(diǎn)kif(s[j]==0&&dist[j]<mindis){k=j;mindis=dist[j]; }s[k]=1; //頂點(diǎn)k加入s中for(u=0;u<g.n;u++)//修改不在s中的頂點(diǎn)的距離if(s[u]==0)if(g.arcs[k][u]<INF&&

dist[k]+g.arcs[k][u]<dist[u]){dist[u]=dist[k]+g.arcs[k][u];path[u]=k;}

voidDijkstra(MGraphg,intv)(4)重復(fù)步驟(2)和(3)直到所有頂點(diǎn)都包含在S中。7.4.3拓?fù)渑判?/p>

問(wèn)題:

假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。

檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判?。例子：?jì)算機(jī)專(zhuān)業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專(zhuān)業(yè)課才能畢業(yè)，這時(shí)工程就是完成給定的學(xué)習(xí)計(jì)劃，而活動(dòng)就是學(xué)習(xí)課程，這些課程的名稱(chēng)與代號(hào)如表所示在AOV網(wǎng)中，用頂點(diǎn)表示課程，有向邊表示課程之間的優(yōu)先關(guān)系，如果課程Ci是課程Cj的先修課，則在AOV網(wǎng)中必定存在一條有向邊<Ci,Cj>。表中各課程的AOV網(wǎng)如下圖所示AOV網(wǎng)：如果用圖中的頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)間的先后關(guān)系，則這樣的有向圖稱(chēng)為頂點(diǎn)活動(dòng)網(wǎng)(ActivityOnVertexnetwork，簡(jiǎn)稱(chēng)AOV網(wǎng))AOV網(wǎng)何謂“拓?fù)渑判颉?？?duì)有向圖進(jìn)行如下操作：

按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。例如：對(duì)于下列有向圖BDAC可求得拓?fù)溆行蛐蛄校?/p>

ABCD

或

ACBD由此所得頂點(diǎn)的線性序列稱(chēng)之為拓?fù)溆行蛐蛄型負(fù)溆行蛐蛄胁皇俏ㄒ坏摹DAC反之，對(duì)于下列有向圖不能求得它的拓?fù)溆行蛐蛄?。因?yàn)閳D中存在一個(gè)回路{B,C,D}任何無(wú)回路的AOV網(wǎng)，其頂點(diǎn)都可以排成一個(gè)拓?fù)湫蛄?，方法如下：從AOV網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)將其輸出。在AOV網(wǎng)中刪除此頂點(diǎn)及其所有的出邊。反復(fù)執(zhí)行以上兩步，直到所有頂點(diǎn)都已經(jīng)輸出為止，此時(shí)整個(gè)拓?fù)渑判蛲瓿?；或者直到剩下的頂點(diǎn)的入度都不為0為止，此時(shí)說(shuō)明AOV網(wǎng)中存在回路，拓?fù)渑判驘o(wú)法再進(jìn)行。拓?fù)渑判蛩枷耄篴bcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

沒(méi)有前驅(qū)的頂點(diǎn)

入度為零的頂點(diǎn)刪除頂點(diǎn)及以它為尾的弧

弧頭頂點(diǎn)的入度減1拓?fù)渑判蛩惴ǎ?/p>

設(shè)置：設(shè)AOV網(wǎng)采用鄰接表表示，邊表為出邊表。算法中定義一個(gè)indegree（1：n)數(shù)組，存放各頂點(diǎn)的入度。設(shè)置一個(gè)鏈棧S（1：n)存儲(chǔ)入度為0的頂點(diǎn)。

算法：

1.拓?fù)渑判蚯?，先得到所有結(jié)點(diǎn)的入度，然后將所有入度為0的頂點(diǎn)壓棧。 2.從棧頂取出一個(gè)頂點(diǎn)將其輸出，由它的出邊表可以得到以該頂點(diǎn)為起點(diǎn)的出邊，將這些邊終點(diǎn)的入度減1，即刪除這些邊。如果某條邊終點(diǎn)的入度為0，則將該頂點(diǎn)入棧。 3.反復(fù)進(jìn)行上述2操作，直到棧為空，如果這時(shí)輸出的頂點(diǎn)個(gè)數(shù)小于n，則說(shuō)明該AOV網(wǎng)中存在回路，否則，拓?fù)渑判蛘＝Y(jié)束。 4.算法結(jié)束后。

C0C1C22257∧36∧C3C4C5C6∧∧C78∧4∧3∧5∧00221221C86∧1拓?fù)湫蛄袨椤肅1,C4,C0,C7,C8,C2,C3,C6,C51.拓?fù)渑判蚯?，先得到所有結(jié)點(diǎn)的入度，然后將所有入度為0的頂點(diǎn)壓棧。2.從棧頂取出一個(gè)頂點(diǎn)將其輸出，同時(shí)將該頂點(diǎn)的所有后繼頂點(diǎn)的入度減1。若后繼頂點(diǎn)的入度為0，則將該頂點(diǎn)入棧。3.反復(fù)進(jìn)行上述2操作，直到棧為空。如果這時(shí)輸出的頂點(diǎn)個(gè)數(shù)小于n，則說(shuō)明該AOV網(wǎng)中存在回路，否則，拓?fù)渑判蛘＝Y(jié)束。

voidFindInDegree(ALGraphG,intindegree[])

{//求頂點(diǎn)的入度inti;ArcNode*p;for(i=0;i<G.vexnum;i++)//對(duì)于所有頂點(diǎn)indegree[i]=0;//給頂點(diǎn)的入度賦初值0for(i=0;i<G.vexnum;i++)//對(duì)于所有頂點(diǎn)

{p=G.vertices[i].firstarc;//p指向頂點(diǎn)的鄰接表的頭指針while(p)

//p不空

{indegree[p->data.adjvex]++;//將p所指鄰接頂點(diǎn)的入度+1p=p->nextarc;//p指向下一個(gè)鄰接頂點(diǎn)}}}indegree[MAX_VERTEX_NUM-1];入度數(shù)組，存放各頂點(diǎn)當(dāng)前入度數(shù)count=0;//對(duì)輸出頂點(diǎn)計(jì)數(shù)while(!EmptyStack(S)){

Pop(S,v);++count;printf(v);

for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){

--indegree(w);//弧頭頂點(diǎn)的入度減一

if(!indegree[w])Push(S,w);

//新產(chǎn)生的入度為零的頂點(diǎn)入棧

}}if(count<G.vexnum){printf("此有向圖有回路\n");returnERROR;}else{printf("為一個(gè)拓?fù)湫蛄?。\n");returnOK;}}FindInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度InitStack(S);for(i=0;i<G.vexnum;++i)

if(!indegree[i])Push(S,i);

//入度為零的頂點(diǎn)入棧StatusTopologicalSort(ALGraphG){

//有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無(wú)回路，則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K；否則返回ERROR。7.4.4關(guān)鍵路徑問(wèn)題:

假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間。問(wèn)：哪些子工程項(xiàng)是“關(guān)鍵工程”？即：哪些子工程項(xiàng)將影響整個(gè)工程的完成期限的。AOE-網(wǎng)：在帶權(quán)的有向圖中，用頂點(diǎn)表示事件，用弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間，這樣組成的網(wǎng)稱(chēng)為以邊表示活動(dòng)的網(wǎng)。abcdefghk64521187244例如:“關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加

將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。(關(guān)鍵路徑上的活動(dòng))整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑(關(guān)鍵路徑)。源點(diǎn)匯點(diǎn)6174注意:在一個(gè)AOE網(wǎng)中,可以有不止一條的關(guān)鍵路徑。

如何求關(guān)鍵活動(dòng)？