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

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

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

某個數(shù)據(jù)對象}是頂點的有窮非空集合；E是頂點之間關(guān)系的有窮集合。如果頂點之間關(guān)系是沒有方向的，則稱E為邊(edge)的集合，表示為E={(x,y)|x,yV}如果頂點之間關(guān)系是有方向的，則稱E為弧的集合，表示為E={<x,y>|x,yV}5.1圖的形式化定義有向圖：頂點對<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)}無向圖：頂點對(x,y)是無序的。名詞和術(shù)語子圖、網(wǎng)、子圖

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

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

VV,VRVR,則稱

G為G的子圖。1597211132

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

n

個頂點，e

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

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

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

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

出度：頂點4入度：

出度：分別是什么圖？這兩個圖的關(guān)系？3頂點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}

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

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

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

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

行1的個數(shù)可得頂點i

的出度，統(tǒng)計第j列1的個數(shù)可得頂點j

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

行(列)1的個數(shù)可得頂點i

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

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

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

EdgeDataEdge[NumVertices][NumVertices];

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

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

u

和

v

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

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

VertexDataGetValue

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

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

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

v

的第一個鄰接頂點的位置

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

//順序檢測第

v行尋找第一個鄰接頂點}return

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

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ū)ふ蚁乱粋€鄰接頂點} return-1;}二、圖的鄰接表存儲表示無向圖的鄰接表同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點代表一條邊(邊結(jié)點),結(jié)點中有另一頂點的下標

dest和指針

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

intdest;//目標頂點下標

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

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

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

EdgeNode*firstAdj;

//邊鏈表頭指針}VertexNode;

typedefstruct{//圖的鄰接表

VertexNodeVexList[NumVertices];

//鄰接表

intn,e;

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

intvertex1,vertex2;//該邊依附的兩個頂點的位置

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

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

DataTypedata;structEdgeBox*firstout;

}VexNode;頂點的值ABCDdataadjABCD012312030113^^^^e1e2e3e4e1e2e3e4三、有向圖的十字鏈表存儲表示

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

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

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

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

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

Status(*Visit)(intv)){

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

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

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

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

void(*visit)(TElemType&e){//從頂點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);

//對v的尚未訪問的鄰接頂點w//遞歸調(diào)用DFS}//DFS二、廣度優(yōu)先搜索遍歷圖對連通圖，從起始點V到其余各頂點必定存在路徑。其中，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)先搜索不是，它是一種分層的順序搜索過程，每向前走一步可能訪問一批頂點。因此，廣度優(yōu)先搜索不是一個遞歸的過程。深度優(yōu)先VS廣度優(yōu)先從圖中的某個頂點V0出發(fā)，并在訪問V0之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。廣度優(yōu)先搜索算法實現(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;//初始化訪問標志InitQueue(Q);//置空的輔助隊列Qwhile(!QueueEmpty(Q)){//遍歷隊列頭的所有鄰接點

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

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

if(!visited[w])

{

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

//訪問的頂點w入隊列

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

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

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

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

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

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

一般情況下所添加的頂點應滿足下列條件:UV-U設置一個輔助數(shù)組，對當前V－U集中的每個頂點，記錄和頂點集U中頂點相連接的代價最小的邊：struct{VertexTypeadjvex;//U集中的頂點序號

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

19mm14m18195712mmm53mmmm73821m1412m8m16mmm21m2718mmm162701234561621gf0000000voidMiniSpanTree_P(MGraphG,VertexTypeu){

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

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

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ù)向生成樹上添加頂點;}

k=minimum(closedge.lowcost);

//求出加入生成樹的下一個頂點(k)

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

closedge[k].lowcost=0;//第k頂點并入U集

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

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};

具體做法:先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止?？紤]問題的出發(fā)點:為使生成樹上邊的權(quán)值之和達到最小，則應使生成樹中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄核惴枋?構(gòu)造非連通圖ST=(V,{});k=i=0;//k計選中的邊數(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)如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。有兩類最短路徑問題

求從某個源點到其余各點的最短路徑—Dijkstra算法

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

v

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

當前所求得的從源點到其余各頂點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>終點從V0到各終點的最短路徑及其長度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為圖中頂點個數(shù)②求出最短路徑的長度：

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

i

V-S

;S←{k

};③修改：

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

對于每一個i

V-S

;④判斷：若S=V,

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

vj，要求求出vi

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

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

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

0237

0加入結(jié)點V2：路徑：010121201220201拓撲排序

問題:

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

檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。用頂點表示活動的網(wǎng)絡(AOV網(wǎng))何謂“拓撲排序”？

按照有向圖給出的次序關(guān)系，將圖中頂點排成一個線性序列，即若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼。例如：對于下列有向圖BDAC可求得拓撲有序序列：

ABCD

或

ACBD由此所得頂點的線性序列稱之為拓撲有序序列BDAC反之，對于下列有向圖不能求得它的拓撲有序序列。因為圖中存在一個回路

{B,C,D}如何進行拓撲排序？一、從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之;

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

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

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

structnode*next;//鏈域}JD;表頭結(jié)點：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)有向圖中，用有向邊表示一個工程中的活動(Activity),

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

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

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

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

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

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