第七章圖7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問(wèn)題7.5

有向無(wú)環(huán)圖及其應(yīng)用7.6

最短路徑7.1圖的定義和術(shù)語(yǔ)

圖是由一個(gè)頂點(diǎn)集V和一個(gè)弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。

Graph=(V,R)R={VR}其中，VR＝{<v,w>|v,w∈V且P(v,w)}

<v,w>表示從v到w的一條弧，并稱(chēng)v為弧尾，w為弧頭。

謂詞P(v,w)定義了弧<v,w>的意義或信息。圖的結(jié)構(gòu)定義:

由于“弧”是有方向的，因此稱(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)。假設(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ù)目定義為頂點(diǎn)v的度。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ú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱(chēng)作此圖的連通分量。BACDFEBACDFE對(duì)有向圖，若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱(chēng)此有向圖為強(qiáng)連通圖。ABECFABECF否則，其各個(gè)強(qiáng)連通子圖稱(chēng)作它的強(qiáng)連通分量。

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

7.2.4鄰接多重表Aij={0(i,j)VR1(i,j)VR7.2.1數(shù)組表示方法BACDFE定義:矩陣的元素為010010100011000101001001110000011100

用兩個(gè)數(shù)組分別存儲(chǔ)數(shù)據(jù)元素（頂點(diǎn)）和數(shù)據(jù)元素之間的關(guān)系（邊或?。┑男畔ⅰo(wú)向圖的鄰接矩陣一定是對(duì)稱(chēng)矩陣，而有向圖的鄰接矩陣則不一定為非對(duì)稱(chēng)矩陣。ABECF//-------圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示--------#defineINFINITYINF_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大頂點(diǎn)個(gè)數(shù)Typedef

enum{DG,DN,UDG,UDN}GraphKind;//{有向圖、

//有向網(wǎng)、無(wú)向圖、無(wú)向網(wǎng)}typedef

struct

ArcCell{//弧的定義

VRType

adj;//VRType是頂點(diǎn)關(guān)系類(lèi)型。對(duì)無(wú)權(quán)圖，用1//或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型。

InfoType*info;//該弧相關(guān)信息的指針}ArcCell，

AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef

struct{//圖的定義

VertexType

vexs[MAX_VERTEX_NUM];//頂點(diǎn)向量

AdjMatrixarcs;//鄰接矩陣

int

vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)

GraphKindkind;//圖的種類(lèi)標(biāo)志

}

MGraph;StatusCreateGraph(MGraph&G){

//采用數(shù)組（鄰接矩陣）表示法，構(gòu)造圖G.

scanf(&G.kind);

switch(G.kind){caseDG:return

CreateDG(G);//構(gòu)造有向圖GcaseDN:return

CreateDN(G);//構(gòu)造有向網(wǎng)GcaseUDG:return

CreateUDG(G);//構(gòu)造無(wú)向圖GcaseUDN:return

CreateUDN(G);//構(gòu)造無(wú)向網(wǎng)G

default:returnERROR;}}//CreateGraph算法7.1StatusCreateUND(MGraph&G){

//采用數(shù)組（鄰接矩陣）表示法，構(gòu)造無(wú)向網(wǎng)G.

scanf(&G.vexnum,&G.arcnum,&IncInfo);

//IncInfo為0則各弧不含其他信息

for(i=0;i<G.vexnum;++i)scanf(&G.vexs[i]);//構(gòu)造頂點(diǎn)向量

for(i=0;i<G.vexnum;++i)//初始化鄰接矩陣

for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};//{adj,info}

for(k=0;k<G.vexnum;++k){//構(gòu)造鄰接矩陣

scanf(&v1,&v2,&w);//輸入一條邊依附的頂點(diǎn)及權(quán)值

i=LocateVex(G,v1);j=LocateVex(G,v2);//確定v1和v2在G中位置

G.arcs[i][j].adj=w;//弧<v1,v2>的權(quán)值

if(IncInfo)Input(*G.arcs[i][j].info);//若弧含有相關(guān)信息，則輸入

G.arcs[j][i]=G.arcs[i][j]；//置<v1,v2>的對(duì)稱(chēng)弧<v2,v1>}returnOK;}//CreateUDN算法7.2typedef

struct

ArcNode

{

int

adjvex;//該弧所指向的頂點(diǎn)的位置

struct

ArcNode

*nextarc;//指向下一條弧的指針

InfoType

*info;//該弧相關(guān)信息的指針}

ArcNode;adjvex

nextarcinfo弧的結(jié)點(diǎn)結(jié)構(gòu)7.2.2鄰接表typedef

struct

VNode

{

VertexTypedata;//頂點(diǎn)信息

ArcNode

*firstarc;//指向第一條依附該頂點(diǎn)的弧

}

VNode,AdjList[MAX_VERTEX_NUM];

datafirstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)typedef

struct{

AdjListvertices;

int

vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)

intkind;//圖的種類(lèi)標(biāo)志

}

ALGraph;圖的結(jié)構(gòu)定義0A141B0452C353D254E015F123BACDFE無(wú)向圖的鄰接表142301201234ABCDE有向圖的鄰接表

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

01234在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。7.2.3十字鏈表

弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾頂點(diǎn)位置

弧頭頂點(diǎn)位置hlink

tlink

弧的相關(guān)信息指向下一個(gè)有相同弧尾的結(jié)點(diǎn)指向下一個(gè)有相同弧頭的結(jié)點(diǎn)typedef

struct

ArcBox

{//弧的結(jié)構(gòu)表示

int

tailvex,headvex;//該弧尾和頭頂點(diǎn)的位置

struct

ArcBox

*hlink,*tlink;//含義見(jiàn)上面框內(nèi)

InfoType*info;//該弧相關(guān)信息的指針

}

VexNode;頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù)firstin

firstout

指向該頂點(diǎn)的第一條入弧指向該頂點(diǎn)的第一條出弧typedef

struct

VexNode

{//頂點(diǎn)的結(jié)構(gòu)表示

VertexTypedata;

ArcBox

*firstin,*firstout;//分別指向該頂點(diǎn)

//第一條入弧和出弧}

VexNode;typedef

struct{

VexNode

xlist[MAX_VERTEX_NUM];//頂點(diǎn)結(jié)點(diǎn)(表頭向量)

int

vexnum,arcnum;//有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}

OLGraph;有向圖的結(jié)構(gòu)表示(十字鏈表)V2V1V4V330∧V4

V3

V2∧V1

012331∧23∧∧200102∧32∧∧圖7.11有向圖的十字鏈表StatusCreateDG(OLGraph&G){

//采用十字鏈表存儲(chǔ)表示，構(gòu)造有向圖G(G.kind=DG)。

scanf(&G.vexnum,&G.arcnum,&IncInfo);//IncInfo為0則各弧不含其他信息

for(i=0;i<G.vexnum;++i)//構(gòu)造表頭向量

scanf(&G.xlist[i].data);//輸入頂點(diǎn)值

G.xlist[i].firstin=NULL;G.xlist[i].firstout=NULL;//初始化指針

}

for(k=0;k<G.vexnum;++k){//輸入各弧并構(gòu)造十字鏈表

scanf(&v1,&v2);//輸入一條邊依附的頂點(diǎn)及權(quán)值

i=LocateVex(G,v1);j=LocateVex(G,v2);//確定v1和v2在G中位置

p=(ArcBox*)malloc(sizeof(ArcBox));//假定有足夠空間*p={i,j,G.xlist[i].firstin,G.xlist[i].firstout,NULL}//對(duì)弧結(jié)點(diǎn)賦值

//{tailvex,headvex,hlink,tlink,info}

G.xlist[i].firstin=G.xlist[i].firstout=p;//完成在入弧和出弧鏈頭的插入

if(IncInfo)Input(*p->info);//若弧含有相關(guān)信息，則輸入

}//CreateUDN算法7.37.2.4鄰接多重表鄰接多重表是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。邊的結(jié)點(diǎn)結(jié)構(gòu)

mark

ivex

ilink

jvex

jlink

info其中：Mark為標(biāo)志域；ivex和jvex為該邊依附的兩個(gè)頂點(diǎn)在圖中的位置；ilink指向下一條依附于頂點(diǎn)ivex

的邊；jlink指向下一條依附于頂點(diǎn)jvex

的邊；info為指向和邊相關(guān)的各種信息的指針域。typedef

struct

Ebox

{

VisitIfmark;//訪(fǎng)問(wèn)標(biāo)記

int

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

struct

EBox

*ilink,*jlink;//分別指向依附這兩個(gè)

//頂點(diǎn)的下一條邊

InfoType

*info;//該邊信息指針}

EBox;其邊的結(jié)構(gòu)表示如下：typedef

struct

VexBox

{

VertexTypedata;

EBox

*firstedge;//指向第一條依附該頂點(diǎn)的邊}

VexBox;頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)

datafirstedge其中：data域存儲(chǔ)和該頂點(diǎn)相關(guān)的信息；firstedge指向第一條依附于該頂點(diǎn)的邊。typedef

struct{//鄰接多重表

VexBox

adjmulist[MAX_VERTEX_NUM];

int

vexnum,edgenum;//無(wú)向圖的當(dāng)前頂點(diǎn)數(shù)

//和邊數(shù)

}

AMLGraph;無(wú)向圖的鄰接多重表結(jié)構(gòu)表示0123圖7.12無(wú)向圖G2的鄰接多重表2∧4∧010∧3∧212341∧V1V2V3V4V54V2V1V5V4V37.3圖的遍歷何謂圖的遍歷？從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪(fǎng)遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次的過(guò)程。深度優(yōu)先搜索（DFS）廣度優(yōu)先搜索（BFS）

從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪(fǎng)問(wèn)此頂點(diǎn)，然后依次從V0的各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。7.3.1深度優(yōu)先搜索（Depth_FirstSearch）Vw1SG1SG2SG3W1、W2和W3

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

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

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

則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。w2w3w2V1v2對(duì)上圖，假設(shè)從v1開(kāi)始進(jìn)行深度優(yōu)先遍歷，則遍歷順序?yàn)椋?/p>

v1→v2→v4→v8→v5→v3→v6→v7v6v3v4v5v7v8從上頁(yè)的圖解可見(jiàn):1.深度優(yōu)先搜索遍歷連通圖的過(guò)程類(lèi)似于樹(shù)的先根遍歷；解決的辦法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪(fǎng)問(wèn)標(biāo)志visited[w]”。其初值為‘false’，一旦某個(gè)頂點(diǎn)被訪(fǎng)問(wèn)，則其相應(yīng)的分量置為‘true’。2.如何判別V的鄰接點(diǎn)是否被訪(fǎng)問(wèn)？voidDFS(GraphG,intv){//從頂點(diǎn)v出發(fā)，深度優(yōu)先遍歷圖Gvisited[v]=TRUE;VisitFunc(v);//訪(fǎng)問(wèn)第v個(gè)頂點(diǎn)

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

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

//對(duì)v的尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn)w//遞歸調(diào)用DFS}//DFS算法7.5首先將圖中每個(gè)頂點(diǎn)的訪(fǎng)問(wèn)標(biāo)志設(shè)為FALSE,之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪(fǎng)問(wèn)，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。一般圖的深度優(yōu)先搜索遍歷void

DFSTraverse(GraphG,

Status(*Visit)(intv)){

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

VisitFunc=Visit;

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

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

if(!visited[v])DFS(G,v);//對(duì)尚未訪(fǎng)問(wèn)的頂點(diǎn)調(diào)用DFS}算法7.4abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg訪(fǎng)問(wèn)標(biāo)志:訪(fǎng)問(wèn)次序:例如:0123456787.3.2廣度優(yōu)先搜索（Breadth_FirstSearch）從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪(fǎng)問(wèn)此頂點(diǎn)之后依次訪(fǎng)問(wèn)V0的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪(fǎng)問(wèn)的先后次序依次訪(fǎng)問(wèn)它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。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。w1Vw2w7w6w3w8w5w4V1v2對(duì)上圖，假設(shè)從v1開(kāi)始進(jìn)行廣度優(yōu)先遍歷，則遍歷順序?yàn)椋?/p>

v1→v2→v3→v4→v5→v6→v7→v8v6v3v4v5v7v8

voidBFSTraverse(GraphG,Status(*Visit)(intv)){//按廣度優(yōu)先非遞歸遍歷圖G，使用輔助隊(duì)列Q和

//訪(fǎng)問(wèn)標(biāo)志數(shù)組visited

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

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

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

if(

!visited[v]){//v尚未訪(fǎng)問(wèn)

}

}//BFSTraverse……算法7.6visited[u]=TRUE;Visit(u);//訪(fǎng)問(wèn)uEnQueue(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])

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

visited[w]=TRUE;Visit(w);

EnQueue(Q,w);

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

}//if}//while7.4.1無(wú)向圖的連通分量和生成樹(shù)

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

7.4.3最小生成樹(shù)

7.4.4關(guān)節(jié)點(diǎn)和重連通分量7.4圖的連通性問(wèn)題

voidDFSForest(GraphG,CSTree&T){

//建立無(wú)向圖G的深度優(yōu)先生成森林的(最左)孩子(右)兄弟鏈表TT=NULL;for(v=0;v<G.vexnum;++v)

visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v]){//第v頂點(diǎn)為新的生成樹(shù)的根結(jié)點(diǎn)

p=(CSTree)malloc(sizeof(CSNode));//分配根結(jié)點(diǎn)

*p={GetVex(G,v),NULL,NULL};//給該結(jié)點(diǎn)賦值

if(!T)T=p;//是第一棵生成樹(shù)的根(T的根)elseq->nextsibling=p;//是其他生成樹(shù)的根(前一棵的根的“兄弟”

q=p;//q指示當(dāng)前生成樹(shù)的根

DFSForest(G,v,p);//建立以p為根的生成樹(shù)

}}//DFSForest7.4.1無(wú)向圖的連通分量和生成樹(shù)算法7.7voidDFSTree(GraphG,CSTree&T){

//從第v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立以T為根的生成樹(shù)。

visited[v]=TRUE ;first=TRUE;for(w=FisrtAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w]){p=(CSTree)malloc(sizeof(CSNode));//分配孩子結(jié)點(diǎn)*p={GetVex(G,w),NULL,NULL};if(first){//w是v的第一個(gè)未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)

T->lchild=p;first=FALSE;//是根的左孩子結(jié)點(diǎn)

}//ifelse{//w是v的其他未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)

q->nextsibling=p;//是上一鄰接頂點(diǎn)的有兄弟結(jié)點(diǎn)

}//elseq=p;

DFSTree(G,w,q);

//從第w個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立子生成樹(shù)q}//if}//DFSTree算法7.8

問(wèn)題：7.4.3最小生成樹(shù)假設(shè)要在n個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要修建n-1條線(xiàn)路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。該問(wèn)題等價(jià)于：算法二：（克魯斯卡爾算法）算法一：（普里姆算法）

取圖中任意一個(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條邊為止。普里姆算法的基本思想:假設(shè)N=（V，{E｝）是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合。算法從U={u0}(u0∈V,TE=={}開(kāi)始，重復(fù)執(zhí)行下述操作：在所有u∈U,v∈V-U的邊(u,v)∈E中找一條代價(jià)最小的邊（u0，v0）并入集合，同時(shí)v0并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，則T=（V，{TE｝）為N的最小生成樹(shù)。普里姆算法:abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹(shù)權(quán)值和=14+8+3+5+16+21=67在生成樹(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)值最小的邊。

一般情況下所添加的頂點(diǎn)應(yīng)滿(mǎn)足下列條件:UV-U

設(shè)置一個(gè)輔助數(shù)組closedge，對(duì)當(dāng)前V－U集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊。對(duì)每個(gè)頂點(diǎn)vi

∈V-U，在輔助數(shù)組中存在一個(gè)相應(yīng)分量closedge[i-1]，它包括兩個(gè)域，其中l(wèi)owcost存儲(chǔ)該邊上的權(quán)。顯然：

closedge[i-1].lowcost=Min{cost(u,v)|u

∈U}struct{

VertexType

adjvex;//U集中的頂點(diǎn)序號(hào)

VRType

lowcost;//邊的權(quán)值}

closedge[MAX_VERTEX_NUM];abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c55closedge0a1b2c3d4e5f6gAdjvexLowcostvoidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)

k=LocateVex(G,u);

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

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ù)向生成樹(shù)上添加頂點(diǎn);算法7.9

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算法描述:構(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++;}普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法7.4.4關(guān)節(jié)點(diǎn)和重連通分量

若從一個(gè)連通圖中刪去任何一個(gè)頂點(diǎn)及其相關(guān)聯(lián)的邊，它仍為一個(gè)連通圖的話(huà)，則該連通圖被稱(chēng)為重（雙）連通圖。問(wèn)題：

若連通圖中的某個(gè)頂點(diǎn)和其相關(guān)聯(lián)的邊被刪去之后，該連通圖被分割成兩個(gè)或兩個(gè)以上的連通分量，則稱(chēng)此頂點(diǎn)為關(guān)節(jié)點(diǎn)。沒(méi)有關(guān)節(jié)點(diǎn)的連通圖為雙連通圖。如何判別給定的連通圖是否是雙連通圖？ahgcbfdeabcdefgh1234567833111111例如:下列連通圖中，頂點(diǎn)

a

和頂點(diǎn)c

是關(guān)節(jié)點(diǎn)深度優(yōu)先生成樹(shù)關(guān)節(jié)點(diǎn)有何特征？

假設(shè)從某個(gè)頂點(diǎn)V0出發(fā)對(duì)連通圖進(jìn)行深度優(yōu)先搜索遍歷，則可得到一棵深度優(yōu)先生成樹(shù)，樹(shù)上包含圖的所有頂點(diǎn)。需借助圖的深度優(yōu)先生成樹(shù)來(lái)分析。

若生成樹(shù)的根結(jié)點(diǎn)，有兩個(gè)或兩個(gè)以上的分支，則此頂點(diǎn)(生成樹(shù)的根)必為關(guān)節(jié)點(diǎn)；

對(duì)生成樹(shù)上的任意一個(gè)“頂點(diǎn)”，若其某棵子樹(shù)的根或子樹(shù)中的其它“頂點(diǎn)”沒(méi)有和其祖先相通的回邊，則該“頂點(diǎn)”必為關(guān)節(jié)點(diǎn)。對(duì)上述兩個(gè)判定準(zhǔn)則在算法中如何實(shí)現(xiàn)？1)設(shè)V0為深度優(yōu)先遍歷的出發(fā)點(diǎn)

p=G.vertices[0].firstarc;v=p->adjvex;

DFSArticul(G,v);

//從第v頂點(diǎn)出發(fā)深度優(yōu)先搜索

if

(count<G.vexnum)

{

//生成樹(shù)的根有至少兩棵子樹(shù)

printf

(0,G.vertices[0].data);

//根是關(guān)節(jié)點(diǎn)2)定義函數(shù):low(v)=Min{visited[v],low[w],visited[k]}

其中:頂點(diǎn)w

是生成樹(shù)上頂點(diǎn)v

的孩子；頂點(diǎn)k

是生成樹(shù)上和頂點(diǎn)v由回邊相聯(lián)接的祖先；

visited記錄深度優(yōu)先遍歷時(shí)的訪(fǎng)問(wèn)次序

若對(duì)頂點(diǎn)v，在生成樹(shù)上存在一個(gè)子樹(shù)根w，

且

low[w]≥visited[v]

則頂點(diǎn)v為關(guān)節(jié)點(diǎn)。對(duì)深度優(yōu)先遍歷算法作如下修改：1．visited[v]的值改為遍歷過(guò)程中頂點(diǎn)的訪(fǎng)問(wèn)次序count值；

2．遍歷過(guò)程中求得

low[v]=Min{visited[v],low[w],visited[k]}3．從子樹(shù)遍歷返回時(shí)，判別low[w]≥visited[v]?for(p=G.vertices[v0].firstarc;p;p=p->nextarc){

}voidDFSArticul(ALGraphG,intv0){//從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G,

//查找并輸出關(guān)節(jié)點(diǎn)}//DFSArticulmin=visited[v0]=++count;//v0是第count個(gè)訪(fǎng)問(wèn)的頂點(diǎn),并設(shè)low[v0]的初值//為min

//檢查v0的每個(gè)鄰接點(diǎn)low[v0]=min;算法7.10

w=p->adjvex;//w為v0的鄰接頂點(diǎn)

if(visited[w]==0){//w未曾被訪(fǎng)問(wèn)

DFSArticul(G,w);//返回前求得low[w]

}

else//w是回邊上的頂點(diǎn)if(low[w]<min)min=low[w];

if(low[w]>=visited[v0])

printf(v0,G.vertices[v0].data);

//輸出關(guān)節(jié)點(diǎn)if(visited[w]<min)min=visited[w];7.5有向無(wú)環(huán)圖及其應(yīng)用

問(wèn)題:

假設(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。對(duì)整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩個(gè)方面的問(wèn)題：一是工程能否順利進(jìn)行；二是估算整個(gè)工程完成所必需的最短時(shí)間。

對(duì)應(yīng)于有向圖，即為進(jìn)行拓?fù)渑判蚝颓箨P(guān)鍵路經(jīng)的操作。何謂“拓?fù)渑判颉?？?jiǎn)單地說(shuō)，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱(chēng)之為拓?fù)渑判颉Ｈ绾蔚玫接邢驁D的一個(gè)拓?fù)湫蛄校?.5.1拓?fù)渑判驅(qū)τ邢驁D進(jìn)行如下操作：按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線(xiàn)性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。由此所得頂點(diǎn)的線(xiàn)性序列稱(chēng)之為拓?fù)溆行蛐蛄?。例如：?duì)于下列有向圖BDAC可求得拓?fù)溆行蛐蛄校?/p>

ABCD

或

ACBD反之：對(duì)于下列有向圖BDAC不能求得它的拓?fù)溆行蛐蛄?。因?yàn)閳D中存在一個(gè)回路

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

重復(fù)上述兩步，直至圖空，或者圖不空但找不到無(wú)前驅(qū)的頂點(diǎn)為止。后一種情況說(shuō)明有向圖中存在環(huán)。二、從有向圖中刪去此頂點(diǎn)以及所有以它為尾的??；abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

沒(méi)有前驅(qū)的頂點(diǎn)=入度為零的頂點(diǎn)刪除頂點(diǎn)及以它為尾的弧=弧頭頂點(diǎn)的入度減1取入度為零的頂點(diǎn)v;while(v<>0){

printf(v);++m;w:=FirstAdj(v);

while(w<>0){

inDegree[w]--;w:=nextAdj(v,w);

}

取下一個(gè)入度為零的頂點(diǎn)v;}ifm<nprintf(“圖中有回路”);算法描述算法7.12為避免每次都要搜索入度為零的頂點(diǎn)，在算法中設(shè)置一個(gè)“棧”，以保存“入度為零”的頂點(diǎn)。CountInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度InitStack(S);for(i=0;i<G.vexnum;++i)

if(!indegree[i])Push(S,i);//入度為零的頂點(diǎn)入棧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(“圖中有回路”)7.5.2關(guān)鍵路徑問(wèn)題:

假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，其中，頂點(diǎn)表示事件，弧表示活動(dòng)，弧上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間。該網(wǎng)絡(luò)稱(chēng)之為AOE網(wǎng)絡(luò)。

假設(shè)以該AOE網(wǎng)絡(luò)表示一個(gè)施工流圖，則有待研究的問(wèn)題是：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些工程是影響整個(gè)工程進(jìn)度的關(guān)鍵？abcdefghk64521187244例如:“關(guān)鍵活動(dòng)”指的是：該弧上的權(quán)值增加

將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑。源點(diǎn)匯點(diǎn)6174

如何求關(guān)鍵活動(dòng)？“事件(頂點(diǎn))”的最早發(fā)生時(shí)間ve(j)ve(j)=從源點(diǎn)到頂點(diǎn)Vj的最長(zhǎng)路徑長(zhǎng)度；這個(gè)時(shí)間決定了所有以Vj為尾的弧所表示的活動(dòng)的最早開(kāi)始時(shí)間

“事件(頂點(diǎn))”的最遲發(fā)生時(shí)間vl(k)

，表示在不推遲整個(gè)工程完成的前提下，事件最遲發(fā)生的時(shí)間。vl(k)=工程完成時(shí)間-從頂點(diǎn)Vk到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度。

假設(shè)第i條弧為<j,k>則對(duì)第i項(xiàng)活動(dòng)而言“活動(dòng)(弧)”的最早開(kāi)始時(shí)間ee(i)

ee(i)=ve(j)；“活動(dòng)(弧)”的最遲開(kāi)始時(shí)間el(i)

el(i)=vl(k)–dut(<j,k>)；

事件發(fā)生時(shí)間的計(jì)算公式：

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

ve(k)=Max{ve(j)+dut(<j,k>)}

vl(匯點(diǎn))=ve(匯點(diǎn))；

vl(j)=Min{vl(k)–dut(<j,k>)}{{abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓?fù)溆行蛐蛄?

a-d-f-c-b-e-h-g-kabcdefghkvevl0645771514181814161078660000645777151414160236688710算法的實(shí)現(xiàn)要點(diǎn):顯然，求ve的順序應(yīng)該是按拓?fù)溆行虻拇涡颍欢髒l的順序應(yīng)該是按拓?fù)淠嫘虻拇涡?；因?yàn)椋負(fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械哪嫘蛄?，因此，?yīng)該在拓?fù)渑判虻倪^(guò)程中，另設(shè)一個(gè)“棧”記下拓?fù)溆行蛐蛄?。StatusTopologicalOrder(ALGraph

G,Stack&T){//有向網(wǎng)G采用鄰接表存儲(chǔ)結(jié)構(gòu)，求各頂點(diǎn)事件的最早發(fā)生時(shí)間ve（全局變量）。//T為拓?fù)湫蛄许旤c(diǎn)棧，S為零入度頂點(diǎn)棧。//若G無(wú)回路，則用棧T返回G的一個(gè)拓?fù)湫蛄?，且函?shù)值為OK，否則為ERROR。FindInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度//indegree[0..vernum-1]，建零入度頂點(diǎn)棧S；InitStack(T);count=0;ve[0..G.vernum-1]=0;//初始化

while(!StackEmpty(S)){

Pop(S,j);Push(T,j);++count;//j號(hào)頂點(diǎn)入T棧并計(jì)數(shù)算法7.13

for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;//對(duì)j號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1if(--indegree[k]==0)Push(S,k);//若入度減為0，則入棧

if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);}//for*(p->info)=dut(<j,k>)}//while

if(count<G.vexnum)returnERROR;

//該有向網(wǎng)有回路

elsereturnOK;}//TopologicalOrderStatusCriticalPath(ALGraphG){

//G為有向網(wǎng)，輸出G的各項(xiàng)關(guān)鍵活動(dòng)。

if(!TopologicalOrder(G,T))returnERROR;v1[0..G.vernum-1]=ve[G.vernum-1]；

//初始化頂點(diǎn)事件的最遲發(fā)生時(shí)間

while(!StackEmpty(T))

//按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的v1值

for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);//dut<j,k>算法7.14

if(v1[k]-dut<v1[j])v1[j]=v1[k]-dut;}//for

for(j=0;j<G.vexnum;++j)//求ee，e1和關(guān)鍵活動(dòng)

for(p=G.vertices[j]；.firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);

ee=ve[j];e1=v1[k]-dut;tag=(ee==e1)?’*’:’’;printf(j,k,dut,ee,e1,tag);//輸出關(guān)鍵活動(dòng)

}}//CriticalPath7.6最短路徑

7.6.1從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑

7.6.2每一對(duì)頂點(diǎn)之間的最短路徑7.6.1從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想:

迪杰斯特拉（Dijkstra）提出依路徑長(zhǎng)度遞增的次序求得各條最短路徑的算法。源點(diǎn)v1…其中，從源點(diǎn)到頂點(diǎn)vj的最短路徑是所有最短路徑中長(zhǎng)度最短者。v2在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。假設(shè)該頂點(diǎn)為Vj

。下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn)：路徑長(zhǎng)度最短的最短路徑的特點(diǎn)：它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)（只含一條?。?；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)vj，再到達(dá)該頂點(diǎn)(由兩條弧組成)。假設(shè)該頂點(diǎn)為V2

。其余最短路徑的特點(diǎn)：再下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn):它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)vj，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v2的最短路徑，再到達(dá)該頂點(diǎn)。它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。求最短路徑的迪杰斯特拉算法：一般情況下，Dist[k]=Min{<源點(diǎn)到頂點(diǎn)k的弧上的權(quán)值>，

<源點(diǎn)到其它頂點(diǎn)的最短路徑長(zhǎng)度>

+<其它頂點(diǎn)到頂點(diǎn)k的弧上的權(quán)值>}

設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Dist[k]表示

當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)k的最短路徑。1）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點(diǎn)的Dist[k]值。假設(shè)已求得最短路徑的頂點(diǎn)為u，若Dist[u]+G.arcs[u][k]<Dist[k]則將Dist[k]改為Dist[u]+G.arcs[u][k]。V0和k之間存在弧V0和k之間不存在弧其中的最小值即為最短路徑的長(zhǎng)度。?íì=∞kvarcsGkDist]][0[.][

voidShortestPath_DIJ(MGraphG,intv0,PathMatrix

&P,ShortPathTable&D){//用Dijkstra算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短//路徑P[v]及其帶權(quán)長(zhǎng)度D[v]。若P[v][w]為T(mén)RUE,則w是//從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)，final[v]為T(mén)RUE當(dāng)//且僅當(dāng)v∈S,即已經(jīng)求得從v0到v的最短路徑

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

final[v]=FALSE;D[v]=G.arcs[v0][v];

for(w=0;w<G.vexnum;++w)P[v][w]=FALSE;

//設(shè)空路徑

if(D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;}}//for算法7.15

D[v0]=0;final[v0]=TRUE;//初始化,v0頂點(diǎn)屬于S集

//開(kāi)始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到S集

for(i=0;i<G.vexnum;++i){//其余G.vexnum-1個(gè)頂點(diǎn)

min=INFINITY;//當(dāng)前所知離v0頂點(diǎn)的最近距離

for(w=0;w<G.vexnum;++w)if(!final[w])//w頂點(diǎn)在V-S中

if(D[w]<min){v=w;min=D[w];}//w頂點(diǎn)離v0頂點(diǎn)更近

final[v]=TRUE;//離v0頂點(diǎn)最近的v加入S集

for(w=0;w<G.vexnum;++