華東理工815數(shù)據(jù)結(jié)構(gòu)Chap5-圖

第五章圖5.1圖的基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4最小生成樹5.5兩點(diǎn)之間的最短路徑問題5.6用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（AOV網(wǎng)）5.7用邊表示活動(dòng)的網(wǎng)絡(luò)（AOE網(wǎng)）圖是由頂點(diǎn)集V和邊（弧）集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。

Graph=(V,E)其中：V={x|x

某個(gè)數(shù)據(jù)對(duì)象}是頂點(diǎn)的有窮非空集合；E是頂點(diǎn)之間關(guān)系的有窮集合。如果頂點(diǎn)之間關(guān)系是沒有方向的，則稱E為邊(edge)的集合，表示為E={(x,y)|x,yV}如果頂點(diǎn)之間關(guān)系是有方向的，則稱E為弧的集合，表示為E={<x,y>|x,yV}5.1圖的形式化定義有向圖：頂點(diǎn)對(duì)<x,y>是有序的EACBD例如:有向圖G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}BCAFED例如:

圖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)}無向圖：頂點(diǎn)對(duì)(x,y)是無序的。名詞和術(shù)語子圖、網(wǎng)、子圖

完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹、生成森林ABECFBBC如果圖G=(V,{VR})和圖

G=(V,{VR}),滿足：

VV,VRVR,則稱

G為G的子圖。1597211132

弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。子圖、網(wǎng)、子圖假設(shè)圖中有

n

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

條邊，則含有e=n(n-1)/2條邊的無向圖稱作完全圖;含有e=n(n-1)條弧的有向圖稱作

有向完全圖;若邊或弧的個(gè)數(shù)e<nlog2n，則稱作稀疏圖，否則稱作稠密圖。完全圖，有向完全圖，稀疏圖假若頂點(diǎn)v和頂點(diǎn)w之間存在一條邊或弧，則稱頂點(diǎn)v和w互為鄰接點(diǎn)，邊(v,w)或弧<v,w>與頂點(diǎn)v和w相關(guān)聯(lián)。例如:TD(B)=TD(A)=和某個(gè)頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目定義為v的度。ACDFEB鄰接點(diǎn)，度32頂點(diǎn)的出度:以頂點(diǎn)v為弧尾的弧的數(shù)目;ABECF有向圖的入度，出度頂點(diǎn)的入度:以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度(TD)=出度(OD)+入度(ID)例如:ID(B)=OD(B)=TD(B)=由于弧有方向性，則頂點(diǎn)的度有入度和出度之分123若圖G=(V,{VR})中存在一個(gè)頂點(diǎn)序列{u=vi,0,vi,1,…,vi,m=w}，其中(vi,j-1,vi,j)VR1≤j≤m,則稱從頂點(diǎn)u到頂點(diǎn)w之間存在一條路徑。路徑上邊或弧的數(shù)目稱作路徑長度。ABECF從A到F的路徑序列為：路徑，路徑長度例如：{A,B,C,F}3其路徑長度為：簡單路徑:指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡單回路:指序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。從A到F的路徑為簡單路徑：簡單路徑，簡單回路ABECF{A,B,C,F}簡單回路：{A,B,C,F,A}若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖;若無向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量。BACDFEBACDFE連通圖，無向圖的連通分量

若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。ABECFABECF對(duì)有向圖，非強(qiáng)連通圖的各個(gè)極大強(qiáng)連通子圖稱作它的強(qiáng)連通分量。強(qiáng)連通圖，強(qiáng)連通分量強(qiáng)連通圖非強(qiáng)連通圖假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，由其中的n個(gè)頂點(diǎn)和n-1

條邊構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。對(duì)非連通圖，則稱由各個(gè)連通分量的生成樹的集合為此非連通圖的生成森林。BACDFE生成樹和生成森林213213356245136245136G1157324G26有向完全圖無向完全圖圖與子圖頂點(diǎn)5的度=頂點(diǎn)2入度：

出度：頂點(diǎn)4入度：

出度：分別是什么圖？這兩個(gè)圖的關(guān)系？3頂點(diǎn)2的度=41310245136G1路徑：{1，2，3，5，6，3}路徑長度：簡單路徑：回路：{1，2，3，5，6，3，1}簡單回路：{3，5，6，3}5{1，2，3，5，6}

假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。對(duì)非連通圖，則稱由各個(gè)連通分量的生成樹的集合為此非連通圖的生成森林。BACDFE生成樹和生成森林結(jié)構(gòu)的建立和銷毀插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問操作遍歷插入和刪除弧5.1.2圖的基本操作（p171)5.2圖的存儲(chǔ)結(jié)構(gòu)一、

圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示二、

圖的鄰接表存儲(chǔ)表示三、有向圖的十字鏈表存儲(chǔ)表示四、無向圖的鄰接多重表存儲(chǔ)表示在圖的鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。設(shè)圖A=(V,E)是一個(gè)有n個(gè)頂點(diǎn)的圖,圖的鄰接矩陣是一個(gè)二維數(shù)組

A.edge[n][n]，定義：一、圖的鄰接矩陣(AdjacencyMatrix)存儲(chǔ)表示無向圖的鄰接矩陣是對(duì)稱的;有向圖的鄰接矩陣可能是不對(duì)稱的。0123012在有向圖中,統(tǒng)計(jì)第i

行1的個(gè)數(shù)可得頂點(diǎn)i

的出度，統(tǒng)計(jì)第j列1的個(gè)數(shù)可得頂點(diǎn)j

的入度。在無向圖中,統(tǒng)計(jì)第i

行(列)1的個(gè)數(shù)可得頂點(diǎn)i

的度。863129542031網(wǎng)絡(luò)的鄰接矩陣用鄰接矩陣表示的圖結(jié)構(gòu)的定義constint

NumEdges=50; //邊條數(shù)constintNumVertices=10;//頂點(diǎn)個(gè)數(shù)typedefcharVertexData;//頂點(diǎn)數(shù)據(jù)類型

typedefintEdgeData;//邊上權(quán)值類型typedefstruct{ VertexDatavexList[NumVertices];//頂點(diǎn)表

EdgeDataEdge[NumVertices][NumVertices];

//鄰接矩陣,可視為邊之間的關(guān)系

intn,e;//圖中當(dāng)前的頂點(diǎn)個(gè)數(shù)與邊數(shù)}MTGraph;intGraphEmpty(MTGraph&G){returnG.n==0;}//判圖G空否,空則返回1,否則返回0。EdgeDataGetWeight(MTGraph&G,intu,intv){//給出以頂點(diǎn)

u

和

v

為兩端點(diǎn)的邊上的權(quán)值

if(u!=-1&&v!=-1)returnG.Edge[u][v];elsereturn0; }

VertexDataGetValue

(MTGraph&G,inti){//給出第

i個(gè)頂點(diǎn)的數(shù)據(jù)值returni>=0&&i<G.n?G.VexList[i]:“\0”;}

intGetFirstNeighbor(MTGraph&G,intv){//給出頂點(diǎn)位置為

v

的第一個(gè)鄰接頂點(diǎn)的位置

if(v!=-1){for(intcol=0;col<G.n;col++)if(G.Edge[v][col]>0&&G.Edge[v][col]<MaxValue)returncol;

//順序檢測(cè)第

v行尋找第一個(gè)鄰接頂點(diǎn)}return

-1;}intGetNextNeighbor(MTGraph&G,intv,intw){//給出頂點(diǎn)v的某鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)

intcol;if(v!=-1&&w!=-1){ for(col=w+1;col<G.n;col++)if(Edge[v][col]>0&&Edge[v][col]<MaxValue)returncol;//在第

v行順序?qū)ふ蚁乱粋€(gè)鄰接頂點(diǎn)} return-1;}二、圖的鄰接表存儲(chǔ)表示無向圖的鄰接表同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊(邊結(jié)點(diǎn)),結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo)

dest和指針

next。ABCDdataadjABCD0123destnextdestnext130210有向圖的鄰接表和逆鄰接表ABCdataadjABC012destnextdestnext鄰接表(出邊表)dataadjABC012destnext逆鄰接表(入邊表)102011二、圖的鄰接表存儲(chǔ)表示網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表BACD69528dataadjABCD0123destcostnext1536283219(出邊表)(頂點(diǎn)表)邊結(jié)點(diǎn)中保存該邊上的權(quán)值cost圖中如有n個(gè)頂點(diǎn)，e條邊，則用鄰接表表示無向圖時(shí)，需要n個(gè)頂點(diǎn)結(jié)點(diǎn)，2e個(gè)邊結(jié)點(diǎn)；用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需n個(gè)頂點(diǎn)結(jié)點(diǎn)，e個(gè)邊結(jié)點(diǎn)。鄰接表表示的圖的定義constintNumVertices=10;//頂點(diǎn)個(gè)數(shù)typedefcharVertexData;//頂點(diǎn)數(shù)據(jù)類型typedefintEdgeData;//邊上權(quán)值類型typedefstructnode{//邊結(jié)點(diǎn)

intdest;//目標(biāo)頂點(diǎn)下標(biāo)

EdgeDatacost; //邊上的權(quán)值

Structnode*next;//下一邊鏈接指針}EdgeNode;typedefstruct{//頂點(diǎn)結(jié)點(diǎn)

VertexDatadata;//頂點(diǎn)數(shù)據(jù)域

EdgeNode*firstAdj;

//邊鏈表頭指針}VertexNode;

typedefstruct{//圖的鄰接表

VertexNodeVexList[NumVertices];

//鄰接表

intn,e;

//圖中當(dāng)前的頂點(diǎn)個(gè)數(shù)與邊數(shù)}AdjGraph;無向圖的鄰接多重表的邊結(jié)點(diǎn)結(jié)構(gòu)markvertex1vextex2path1path2指向下一條與頂點(diǎn)vertex2相關(guān)聯(lián)的邊指向下一條與頂點(diǎn)vertex1相關(guān)聯(lián)的邊標(biāo)記位邊的一個(gè)頂點(diǎn)的下標(biāo)位置邊的另一個(gè)頂點(diǎn)的下標(biāo)位置typedefstructEdgeBox{VisitIfmark;//訪問標(biāo)記

intvertex1,vertex2;//該邊依附的兩個(gè)頂點(diǎn)的位置

structEdgeBox*path1,*path2;InfoTypecost;//權(quán)重信息

}EBox;無向圖的鄰接多重表的邊結(jié)點(diǎn)表示無向圖的鄰接多重表的頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)datafirstout指向依附于該頂點(diǎn)的第一條邊typedefstructVexNode{//頂點(diǎn)的結(jié)構(gòu)表示

DataTypedata;structEdgeBox*firstout;

}VexNode;頂點(diǎn)的值A(chǔ)BCDdataadjABCD012312030113^^^^e1e2e3e4e1e2e3e4三、有向圖的十字鏈表存儲(chǔ)表示

將有向圖的鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。markvertex1vextex2path1path2指向下一條以vertex2為終點(diǎn)的弧指向下一條以vertex1為起點(diǎn)的弧標(biāo)記位弧的起點(diǎn)的下標(biāo)位置弧的終點(diǎn)的下標(biāo)位置弧的結(jié)構(gòu)typedefstructArcBox{//弧的結(jié)構(gòu)表示

intvertex1,vertex2,mark;structArcBox*path1,*path2;

}VexNode;頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù)指向該頂點(diǎn)的第一條入弧指向該頂點(diǎn)的第一條出弧typedefstructVexNode{//頂點(diǎn)的結(jié)構(gòu)表示

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;datafirstinfirstout三、有向圖的十字鏈表存儲(chǔ)表示

ABCABC012∧02∧∧0121∧20∧∧將有向圖的鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。a1a2a3a4a1a2a3a45.3圖的遍歷從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。深度優(yōu)先搜索廣度優(yōu)先搜索遍歷應(yīng)用舉例從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;一、深度優(yōu)先搜索遍歷圖ACDEGBFH12345768前進(jìn)回退ACDEGBFH12345768深度優(yōu)先搜索過程深度優(yōu)先生成樹解決的辦法是:為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問標(biāo)志visited[w]”;由于圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。如何判別V的鄰接點(diǎn)是否被訪問？一、深度優(yōu)先搜索遍歷圖abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg訪問標(biāo)志:訪問次序:例如:achdkfevoidDFSTraverse(GraphG,

Status(*Visit)(intv)){

//對(duì)圖G作深度優(yōu)先遍歷。

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問標(biāo)志數(shù)組初始化

for(v=0;v<G.vexnum;++v)

if(!visited[v])DFS(G,v,Visit);//對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS}每調(diào)用一次DFS()就遍歷了圖的一個(gè)連通分量voidDFS(GraphG,intv,

void(*visit)(TElemType&e){//從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖Gvisited[v]=TRUE;visit(v);

for(w=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w,visit);

//對(duì)v的尚未訪問的鄰接頂點(diǎn)w//遞歸調(diào)用DFS}//DFS二、廣度優(yōu)先搜索遍歷圖對(duì)連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑。其中，A->B,A->C的路徑長度為1;A->D,A->E,A->F，A->G的路徑長度為2;A->H的路徑長度為3。廣度優(yōu)先搜索過程廣度優(yōu)先生成樹ACDEGBFH12345678ACDEGBFH深度優(yōu)先搜索是一種回溯的算法。廣度優(yōu)先搜索不是，它是一種分層的順序搜索過程，每向前走一步可能訪問一批頂點(diǎn)。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程。深度優(yōu)先VS廣度優(yōu)先從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問V0之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問,則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。廣度優(yōu)先搜索算法實(shí)現(xiàn)1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^220123451fr遍歷序列：10123454fr遍歷序列：14323遍歷序列：14325廣度優(yōu)先遍歷算法示例2012345325fr1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^2201234525fr遍歷序列：143250123455fr遍歷序列/p>

fr遍歷序列：14325for(v=0;v<G.vexnum;++v)

if(

!visited[v]){//v尚未訪問

}

voidBFS(constGraph&G,Status(*Visit)(intv)){}//BFS……

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//初始化訪問標(biāo)志InitQueue(Q);//置空的輔助隊(duì)列Qwhile(!QueueEmpty(Q)){//遍歷隊(duì)列頭的所有鄰接點(diǎn)

}//whileEnQueue(Q,v);//v入隊(duì)列visited[v]=TRUE;Visit(v);//訪問uDeQueue(Q,u);//隊(duì)頭元素出隊(duì)并置為u

for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))

if(!visited[w])

{

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

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

}//if連通圖的生成樹假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，由其中n-1條邊和n個(gè)頂點(diǎn)所構(gòu)成一個(gè)極小連通子圖，稱為此連通圖的生成樹。生成樹具有以下共同特點(diǎn)：生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹中再加一條邊必然形成回路V1V2V4V5V3V7V6V8深度遍歷：V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V4V8V5V3V6V7V1V2V3V4V5V6V7V8

非連通圖的連通分量及生成森林對(duì)于非連通圖，從圖中某一頂點(diǎn)出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn)，只能訪問到該頂點(diǎn)所在的最大連通子圖（連通分量）的所有頂點(diǎn)。從無向圖的每一個(gè)連通分量中的一個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷，即可求得無向圖的所有連通分量及其生成樹。對(duì)于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。IHJONMLK非連通無向圖ACDEBFGACDEBFGHIJKONML非連通圖的連通分量從不同頂點(diǎn)出發(fā)，通過強(qiáng)連通有向圖的遍歷，可以得到不同的生成樹。強(qiáng)連通有向圖

深度優(yōu)先生成樹ACDEBFACDEBF123456ACDEBF123456ACDEBF123456

(連通網(wǎng)的)最小生成樹構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。(連通網(wǎng)的)最小生成樹構(gòu)造最小生成樹的準(zhǔn)則：1必須使用且僅使用該帶權(quán)圖中的n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；2不能使用產(chǎn)生回路的邊；3各邊上的權(quán)值的總和達(dá)到最小。算法二：（克魯斯卡爾算法）算法一：（普里姆算法)(連通網(wǎng)的)最小生成樹普里姆算法的基本思想：從連通帶權(quán)圖N={V,E}中的某一頂點(diǎn)u0

出發(fā)，選擇與u0相關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v)，將其頂點(diǎn)v加入到生成樹頂點(diǎn)集合U中。以后每一步從一個(gè)頂點(diǎn)在U中，而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把v加入到集合U

中。如此繼續(xù)下去,直到帶權(quán)圖中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。采用鄰接矩陣作為帶權(quán)圖的存儲(chǔ)表示。abcdegf195141827168213127Prim算法示例:aedcbgf148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67在生成樹的構(gòu)造過程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集U和尚未落在生成樹上的頂點(diǎn)集V-U，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。

一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:UV-U設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前V－U集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：struct{VertexTypeadjvex;//U集中的頂點(diǎn)序號(hào)

VRTypelowcost;//邊的權(quán)值}closedge[MAX_VERTEX_NUM];abcdegf195141827168213127aedcbaaa19141814e12ee8168d3dd7213c55

19mm14m18195712mmm53mmmm73821m1412m8m16mmm21m2718mmm162701234561621gf0000000voidMiniSpanTree_P(MGraphG,VertexTypeu){

//用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹}

k=LocateVex(G,u);//找出頂點(diǎn)u的邊信息在數(shù)組中的行號(hào)

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

if(j!=k)

closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0;//初始，U＝{u}for(i=0;i<G.vexnum;++i){

繼續(xù)向生成樹上添加頂點(diǎn);}

k=minimum(closedge.lowcost);

//求出加入生成樹的下一個(gè)頂點(diǎn)(k)

printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹上一條邊

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)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止?？紤]問題的出發(fā)點(diǎn):為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄核惴枋?構(gòu)造非連通圖ST=(V,{});k=i=0;//k計(jì)選中的邊數(shù)

while(k<n-1){++i;

檢查邊集E中第i條權(quán)值最小的邊(u,v);

若(u,v)加入ST后不使ST中產(chǎn)生回路，

則輸出邊(u,v);

且k++;}abcdegf195141827168213127aedcbgf148531621克魯斯卡爾算法示例:71218195.5最短路徑(ShortestPath)如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。有兩類最短路徑問題

求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑—Dijkstra算法

每一對(duì)頂點(diǎn)之間的最短路徑—Floyd算法單源最短路徑問題問題的提法：給定一個(gè)帶權(quán)有向圖D與源點(diǎn)v，求從

v

到D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序,逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。下一條路徑長度次短的路徑的特點(diǎn):路徑長度最短的最短路徑的特點(diǎn):它只可能有兩種情況:或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是，從源點(diǎn)經(jīng)過某個(gè)已求得最短路徑的頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。其余最短路徑的特點(diǎn)：它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是，從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。求最短路徑的迪杰斯特拉算法：把V分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合算法將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，保證：從源點(diǎn)V0到S中各頂點(diǎn)的最短路徑長度都不大于從V0到T中任何頂點(diǎn)的最短路徑長度。設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Dist[k]記錄

當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)k的最短路徑。13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>終點(diǎn)從V0到各終點(diǎn)的最短路徑及其長度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329

138m30m32mmmm97mm5mmmmmm6mmmmmm2mmmmmm17mmmmmmDijkstra算法可描述如下：①

初始化：

S←{v0};

dist[j]←Edge[0][j],j=1,2,…,n-1;

//n為圖中頂點(diǎn)個(gè)數(shù)②求出最短路徑的長度：

dist[k]←min{dist[i]},

i

V-S

;S←{k

};③修改：

dist[i]←min{dist[i],dist[k]+Edge[k][i]},

對(duì)于每一個(gè)i

V-S

;④判斷：若S=V,

則算法結(jié)束，否則轉(zhuǎn)②。求每一對(duì)頂點(diǎn)之間的最短路徑問題的提法：已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有向圖，對(duì)每一對(duì)頂點(diǎn)vi

vj，要求求出vi

與vj之間的最短路徑和最短路徑長度。

求每一對(duì)頂點(diǎn)之間的最短路徑方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次——

T(n)=O(n3)方法二：弗洛伊德(Floyd)算法算法思想：逐個(gè)頂點(diǎn)試探法求最短路徑步驟初始時(shí)設(shè)置一個(gè)n階方陣，令其對(duì)角線元素為0，若存在弧<Vi,Vj>，則對(duì)應(yīng)元素為權(quán)值；否則為逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值所有頂點(diǎn)試探完畢，算法結(jié)束021264311041160230初始：路徑：0102101220046602370加入結(jié)點(diǎn)V1：路徑：010121012202010411602370加入結(jié)點(diǎn)V0：路徑：01021012202010465

0237

0加入結(jié)點(diǎn)V2：路徑：010121201220201拓?fù)渑判?/p>

問題:

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

檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判颉Ｓ庙旤c(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(AOV網(wǎng))何謂“拓?fù)渑判颉保?/p>

按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，即若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼。例如：對(duì)于下列有向圖BDAC可求得拓?fù)溆行蛐蛄校?/p>

ABCD

或

ACBD由此所得頂點(diǎn)的線性序列稱之為拓?fù)溆行蛐蛄蠦DAC反之，對(duì)于下列有向圖不能求得它的拓?fù)溆行蛐蛄小Ｒ驗(yàn)閳D中存在一個(gè)回路

{B,C,D}如何進(jìn)行拓?fù)渑判?？一、從有向圖中選取一個(gè)沒有前驅(qū)的頂點(diǎn)，并輸出之;

重復(fù)上述兩步，直至圖空，或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。二、從有向圖中刪去此頂點(diǎn)以及所

有以它為尾的弧;abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

沒有前驅(qū)的頂點(diǎn)入度為零的頂點(diǎn)刪除頂點(diǎn)及以它為尾的弧弧頭頂點(diǎn)的入度減1算法描述以鄰接表作存儲(chǔ)結(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧重復(fù)上述操作直至?？諡橹?。若?？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤呧徑颖斫Y(jié)點(diǎn)：typedefstructnode{intvex;//頂點(diǎn)域

structnode*next;//鏈域}JD;表頭結(jié)點(diǎn)：typedefstructtnode{intin;//入度域

structnode*link;//鏈域}TD;TDg[M];//g[0]不用321041234560122inlink5543^^^vexnext3^25^240123456^160122inlink5543^^^vexnext3^25^240123456^輸出序列：6321041123456210112inlink5543^^^vexnext2^25^240123456^輸出序列：6132104112345604031310224055如果在無有向環(huán)的帶權(quán)有向圖中，用有向邊表示一個(gè)工程中的活動(dòng)(Activity),

用邊上權(quán)值表示活動(dòng)持續(xù)時(shí)間(Duration),

用頂點(diǎn)表示事件(Event),則這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡稱AOE(ActivityOnEdges)網(wǎng)絡(luò)。AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：完成整個(gè)工程至少需要多少時(shí)間（假設(shè)網(wǎng)絡(luò)中沒有環(huán)）?為縮短完成工程所需的時(shí)間，應(yīng)當(dāng)加快哪些活動(dòng)?

5.7用邊表示活動(dòng)的網(wǎng)絡(luò)（AOE網(wǎng)）問題:

假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間。問：哪些子工程項(xiàng)是“關(guān)鍵工程”？即：哪些子工程項(xiàng)將影響整個(gè)工程的完成期限。關(guān)鍵路徑整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長路徑。abcdefghk64521187244例如:“關(guān)鍵活動(dòng)”指的是關(guān)鍵路徑上的活動(dòng)：該弧上的權(quán)值增加

將使有向圖上的最長路徑的長度增加。源點(diǎn)表示工程開始的狀態(tài)匯點(diǎn)表示工程結(jié)束的狀態(tài)6174任務(wù)進(jìn)度時(shí)間參數(shù)說明最早開始時(shí)間ES(Earlystart)最晚開始時(shí)間LS(Latestart)最早完成時(shí)間EF(Earlyfinish)最晚完成時(shí)間LF(Latefinish)關(guān)鍵活動(dòng)：該活動(dòng)的最早開始時(shí)間=該活動(dòng)的最遲開始時(shí)間,即活動(dòng)的時(shí)間余量為0的時(shí)間“事件（頂點(diǎn)）”的最早可能發(fā)生時(shí)間ve(j)=從源點(diǎn)到頂點(diǎn)vj的最長路徑長度;v0v1v2v3v4v5v6v7v8a1=6a2=4a3=5a6=2a4=1a5=1a7=8a8=7a10=2a11=4a9=4“事件（頂點(diǎn)）”的最遲允許發(fā)生時(shí)間vl(j)=ve(匯點(diǎn))-v(j)到匯點(diǎn)的最長路徑;

“活動(dòng)(弧)”的最早可能開始時(shí)間e(i)=弧頭頂點(diǎn)的最早發(fā)生時(shí)間;“活動(dòng)(弧)”的最遲開始時(shí)間l(i)=vl(弧頭)–活動(dòng)的執(zhí)行時(shí)間dut活動(dòng)ai的時(shí)間余量=l(i)-e(i)chapter__396正推法實(shí)例StartLFLSEFES