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

第7章圖7.1圖的定義和術(shù)語圖(Graph)是一種數(shù)據(jù)結(jié)構(gòu)，形式定義

Graph=(V,R)

其中：V={x|x∈dataobject}R={VR}VR={<x,y>|p(x,y)∧(x,y∈V)}p(x,y)表示從x到y(tǒng)的一條通路圖的抽象數(shù)據(jù)類型定義：ADTGraph{

數(shù)據(jù)對(duì)象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：

R={VR}VR={<v,w>|v,w∈V且P(v,w),<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}

基本操作P：

GreateGraph(&G,V,VR);DestroyGraph(&G);LocateVex(G,u);GetVex(G,v);PutVex(&G,v,Value);FirstAdjVex(G,v);NextAdjVex(G,v,w);InsertVex(&G,v);DeleteVex(&G,v);InsertArc(&G,v,w);DeleteArc(&G,v,w);DFSTraverse(G,v,Visit());BFSTraverse(G,v,Visit());}ADTGraphv2v1v3v4v5v2v1v4v3例如：G1=(v1,{A1})其中：

v1={v1,v2,v3,v4,}A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}例如：G2=(v2,{E2})其中：

v2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3)(v2,v5),(v3,v4),(v3,v5)}設(shè)圖中頂點(diǎn)數(shù)為n，邊或弧數(shù)為e，則：對(duì)于無向圖，e的取值范圍為0~~n(n-1)/2具有n(n-1)/2條邊的無向圖稱為完全圖對(duì)于有向圖，e的取值范圍為0~~n(n-1)具有n(n-1)條邊的有向圖稱為有向完全圖和圖中邊相關(guān)的數(shù)叫作權(quán)（weigth）帶權(quán)的圖稱為網(wǎng)頂點(diǎn)的度是和該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目。記作TD(v)以頂點(diǎn)v為頭的弧的數(shù)目稱為v的入度。記作ID(v)以頂點(diǎn)v為尾的弧的數(shù)目稱為v的出度。記作OD(v)頂點(diǎn)v的度TD(v)=ID(v)+OD(v)鄰接點(diǎn)：對(duì)于無向圖G=(V,{E})，如果邊(v,v’)∈E,則稱頂點(diǎn)v和v’互為鄰接點(diǎn)路徑：路徑是頂點(diǎn)的序列V={Vi0,Vi1,……Vin}，

滿足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)路徑長度：沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑簡單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑簡單回路：除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路連通：從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說V和W是連通的連通圖：無向圖中任意兩個(gè)頂點(diǎn)都是連通的連通分量：無向圖中的極大連通子圖強(qiáng)連通圖：有向圖中，如果對(duì)每一對(duì)Vi,VjV,ViVj,從Vi到

Vj和從Vj到Vi都存在路徑，則稱G是強(qiáng)連通圖強(qiáng)連通分量：有向圖中的極大強(qiáng)連通子圖有向完全圖：具有n(n-1)條邊的有向圖無向完備圖：具有n(n-1)/2條邊的無向圖權(quán)：與圖的邊或弧相關(guān)的數(shù)網(wǎng)：帶權(quán)的圖7.2圖的存儲(chǔ)結(jié)構(gòu)多重鏈表例G12413V1V2^^V4^V3^例15324G2^V1V2V4^V5^V3實(shí)際中不適用數(shù)組表示法（鄰接矩陣）設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣A[i][j]=1,若(Vi,Vj)E或<Vi,Vj>E0,其它例G1v2v4v1v3例v1v5v3v2v4G2v1v3v2v4v1v3v2v4v5圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,djMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM]; AdjMatrixarcs; intvexnum,arcnum;GraphKindkind;}MGraph;特點(diǎn)：無向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無向圖需存儲(chǔ)空間為n(n+1)/2有向圖鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2無向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣中第i行元素之和有向圖中，頂點(diǎn)Vi的出度是鄰接矩陣中第i行元素之和頂點(diǎn)Vi的入度是鄰接矩陣中第i列元素之和易于實(shí)現(xiàn)基本操作A[i][j]=Wi,j,若(Vi,Vj)E或<Vi,Vj>E∞,其它網(wǎng)的鄰接矩陣可定義為：例v1v4v5v2v375318642v1v3v2v4v5∞57∞35∞∞487∞∞21∞42∞63816∞采用數(shù)組（鄰接矩陣）表示法，構(gòu)造圖GStatusCreateGraph(MGraph&G){scanf(&G.kind);switch(G.kind){ caseDG:returnCreateDG(G); caseDN:returnCreateDN(G); caseUDG:returnCreateUDG(G); caseUDN:returnCreateUDN(G);default:returnERROR;}}采用數(shù)組（鄰接矩陣）表示法，構(gòu)造無向網(wǎng)GStatusCreateUDN(MGraph&G){scanf(&G.vexnum,&G.arcnum,&IncInfo);for(i=0;i<G.vexnum;++i)scanf(&G.vexs[i]);for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};for(k=0;k<G.arcnum;++k){ scanf(&v1,&v2,&w); i=LocateVex(G,v1);j=LocateVex(G,v2); G.arcs[i][j].adj=w; if(IncInfo)Input(*G.arcs[i][j].info); G.arcs[j][i]=G.arcs[i][j]; }returnOK}鄰接表表示例G1v2v4v1v3例v1v5v3v2v4G20123v1v3v4v2vexdatafirstarc2130^^^^adjvexnext0123v1v3v4v2vexdatafirstarc1423^^^adjvexnext5v5320^41021^圖的鄰接表存儲(chǔ)表示#defineMAX_VERTEX_NUM20typedefstructArcNode{int adjvex;structArcNode*nextarc;InfoType *info;}ArcNode;typedefstructVnode{VertexTypedata;ArcNode*firstarc;}Vnode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListVertices;int vexnum,arcnum;int kind;}ALGraph;adjvexnextarcinfo表結(jié)點(diǎn)datafirstarc頭結(jié)點(diǎn)特點(diǎn)若無向圖中有n個(gè)頂點(diǎn)、e條邊，則需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)有向圖中頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表例G1v2v4v1v30123v1v3v4v2vexdatafirstarc30^0^^2^adjvexnext

十字鏈表------有向圖的另一種存儲(chǔ)結(jié)構(gòu)tailvexheadvexhlinktlinkdatafirstinfirstout有向圖的十字鏈表存儲(chǔ)表示#defineMAX_VERTEX_NUM20typedefstructArcBox{inttailvex,headvex;structArcBox*hlink,*tlink;InfoType*info;}ArcBox;typedefstructVexNode{VertexTypedata;ArcBox*firstin,*firstout;}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];intvexnum,arcnum;}OLGraph;例v2v4v1v3v1v2v3v4012302012320323130^^^^^^^^tailvexheadvexhlinktlinkdatafirstinfirstout采用十字鏈表存儲(chǔ)結(jié)構(gòu)，構(gòu)造有向圖StatusCreateDG(OLGraph&G){scanf(&G.vernum,&G.arcnum,&IncInfo);for(i=0;i<G.vexnum;++i){scanf(&G.xlist[i].data);G.xlist[i].firstin=NULL;G.xlist[i].firstout=NULL;}for(k=0;k<G.arcnum;++k){scanf(&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);p=(ArcBox*)malloc(sizeof(ArcBox));*p={i,j,G.xlist[j].firstin,G.xlist[i].firstout,NULL} //{tailvex,headvex,hlink,tlink,info}G.xlist[j].firstin=G.xlist[i].firstout=p;if(IncInfo)Input(*p->info);}}無向圖的鄰接多重表存儲(chǔ)表示#defineMAX_VERTEX_NUM20typedefemnu{unvisited,visited}VisitIf;typedefstructEBox{VisitIf mark;int ivex,jvex;structEBox*ilink,*jlink;InfoType*info;}Ebox;typedefstructVexBox{VertexType data;EBox*firstedge;}VexBox;typedefstruct{VexBoxadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;}AMLGraph;markivexilinkjvexjlinkdatafirstedge

鄰接多重表-----無向圖的另一種存儲(chǔ)結(jié)構(gòu)例v1v5v3v2v40123v1v3v4v24v5010323212441^^^^^markivexilinkjvexjlinkdatafirstedge7.3圖的遍歷圖的遍歷：從圖中某一頂點(diǎn)出發(fā)，對(duì)圖中所有頂點(diǎn)訪問一次且僅訪問一次。

操作的抽象，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理可以以輸出結(jié)點(diǎn)的數(shù)據(jù)為例來理解在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在樹結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系為雙親和孩子；在圖結(jié)構(gòu)中，頂點(diǎn)之間的關(guān)系為鄰接。

FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)7.3圖的遍歷不同結(jié)構(gòu)中邏輯關(guān)系的對(duì)比一、深度優(yōu)先搜索(DepthFirstSearch)方法：從圖的某一頂點(diǎn)V出發(fā)，訪問此頂點(diǎn)；然后依次從V的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先搜索圖，直至圖中所有和V有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。深度優(yōu)先搜索序列：V1V2V3V1V4V5V6V7V2V8V7V3V4V5V3V6V2V8V1V2V3V4V5V6V7V8v1v2v4v8v5v3v6v7遍歷操作中要解決的關(guān)鍵問題：①“從圖的某一頂點(diǎn)V出發(fā)”，如何選取出發(fā)頂點(diǎn)。解決方案：按存儲(chǔ)結(jié)構(gòu)排列順序的第一個(gè)。②“依次從V的未被訪問的鄰接點(diǎn)出發(fā)”中“依次”解決方案：按基本操作，先找第一鄰接點(diǎn)，再找下一個(gè),循環(huán)查找各鄰接點(diǎn)。③“未被訪問的”鄰接點(diǎn)解決方案：設(shè)訪問標(biāo)志數(shù)組visited[

]

④非連通圖解決方案：從任意一個(gè)未被訪問的結(jié)點(diǎn)出發(fā)調(diào)用算法

算法7.47.5深度優(yōu)先算法Booleanvisited[MAX];Status(*VisitFunc)(intv);voidDFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}

voidDFS(GraphG,intv){visited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}問題：判斷給定圖是否是連通圖？多少個(gè)連通分量深度遍歷：V10123v1v3v4v2vexdatafirstarc2571^^^adjvexnext4v5640^30171^v6v7v8567625243^^^V2V4V8V5V3V6V7V1V2V3V4V5V6V7V8voidDFS(GraphG,intv){visited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);}鄰接矩陣存儲(chǔ)結(jié)構(gòu)voidDFS(MGraphG,intv){visited[v]=TRUE;VisitFunc(v);for(j=0;j<G.vexnum;j++)if(G.arcs[v][j].adj==1&&!visited[j])DFS(G,j);}鄰接表存儲(chǔ)結(jié)構(gòu)voidDFS(ALGraphG,intv){visited[v]=TRUE;VisitFunc(v);p=G.vertices[v].firstarc;while(p){if(!visited[p->adjvex])DFS(G,p-adjvex);p=p->nextarc;}

時(shí)間復(fù)雜度：O(n2)

時(shí)間復(fù)雜度：O(n+e)二、廣度優(yōu)先搜索(BreadthFirstSearch)方法：從圖的某一頂點(diǎn)V出發(fā)，訪問了V之后，依次訪問V的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，依次訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。廣度遍歷：V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8voidBFSTraverse(GraphG,Status(*visit)(intv)){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;InitQueue(Q);for(v=0;v<G.vexnum;++v)if(!visited[v]){visited[v]=TRUE;visit(v);EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u); for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;visit(w);EnQueue(Q,w)}//if}//while}//if}

時(shí)間復(fù)雜度：鄰接矩陣存儲(chǔ)：O(n2)

鄰接表存儲(chǔ)：O(n+e)V1V2V3V4V5V6V7V8問題：二叉樹按層次遍歷問題：迷宮問題7.4圖的連通性問題一、無向圖的連通分量和生成樹對(duì)無向非連同圖進(jìn)行深度優(yōu)先遍歷三次調(diào)用得到的訪問序列為：ALMJBFCDEGKHIABCDEFGHIJKLMALJMBFCDEGKHI生成樹：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖。深度優(yōu)先生成樹與廣度優(yōu)先生成樹生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的生成森林。說明一個(gè)圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點(diǎn)：生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同生成樹是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹建立非連通圖G的深度優(yōu)先生成森林voidDFSForest(GraphG,CSTree&T){T=NULL;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v]){p=(CSTree)malloc(sizeof(CSNode));*p={GetVex(G,v),NULL,NULL};if(!T)T=p;elseq->nextsibling=p;q=p;DFSTree(G,v,p);}}從第v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，建立以T為根的生成樹voidDFSTree(GraphG,intv,CSTree&T){visited[v]=TRUE;first=TRUE;for(w=FisrtAdjVex(g,v);w;w=NextAdjVex(G,u,w))if(!visited[w]){p=(CSTree)malloc(sizeof(CSNode));*p={GetVex(G,w),NULL,NULL};if(first){T->lchild=p;first=FALSE;}else{q->nextsibling=p;}q=p;DFSTree(G,w,q);}}二、最小生成樹問題提出：要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)表示城市，邊上的權(quán)值表示城市間建立通信線路所需花費(fèi)代價(jià)，現(xiàn)希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小———最小代價(jià)生成樹。問題分析：991886261312n個(gè)城市間，最多有n(n-1)/2條線路n個(gè)城市間建立通信網(wǎng)，只需n-1條線路問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點(diǎn)）均連起來，且總耗費(fèi)(各邊權(quán)值之和)最小。構(gòu)造一個(gè)最小生成樹12345性質(zhì)：假設(shè)N=(V,{E})是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若（u,v）是一條具有最小權(quán)值（代價(jià)）的邊，其中uU,vV-U，則必存在一棵包含邊(u,v)的最小生成樹。普里姆(Prim)算法算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹6513566425123456123456Struct{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];0v16v11v15∞∞adjvexlowcost0(v1)1(v2)2(v3)3(v4)4(v5)5(v6)0v350v15v36v34U={V1}V-U={V2,V3,V4,V5,V6}U={V1,V3}V-U={V2,V4,V5,V6}0v350v62v360U={V1,V3,V6}V-U={V2,V4,V5}U={V1,V3,V6,V4}V-U={V2,V5}0v3500v360U={V1,V3,V6,V4,V2}V-U={V5}0000v230U={V1,V3,V6,V4,V2,V5}V-U={}0000006513566425123456voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){k=LocateVex(G,u);for(j=0;j<G.vexnum;++j)if(j!=k)closedge[j]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=minimum(closedge);printf(closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0for(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};}}克魯斯卡爾(Kruskal)算法算法思想：設(shè)連通網(wǎng)N=(V,{E})，令最小生成樹初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,{})，每個(gè)頂點(diǎn)自成一個(gè)連通分量在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止。1234565135664251234561234567.5有向無環(huán)圖及其應(yīng)用有向無環(huán)圖（DirectedAcyclineGraph）一個(gè)無環(huán)的有向圖,簡稱DAG圖DAG圖有向樹有向圖用有向無環(huán)圖描述含有公共子式的表達(dá)式例((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)*+**+ab*b+cd*+cde+cde*+*e*+*+abcd一、拓?fù)渑判蛲負(fù)渑判颍═opologicalSort）:由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱為拓?fù)渑判颉?/p>

若集合X上的關(guān)系R是自反的，反對(duì)稱的和傳遞的，則稱R是集合X上的偏序關(guān)系。

設(shè)R是集合X上的偏序關(guān)系，如果對(duì)每個(gè)小x,yX

必有xRy或yRx，則稱R是集合X上的全序關(guān)系。V1V2V3V4學(xué)生選修課程問題頂點(diǎn)——表示課程有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)——拓?fù)渑判蛘n程代號(hào)課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1,C2,C3,C4,C5,C7,C9,C10,C11,C6,C12,C8C9,C10,C11,C6,C1,C12,C4,C2,C3,C5,C7,C8一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏捻旤c(diǎn)表示活動(dòng)，弧表示優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)（ActivityOnVertexNetwork）簡稱AOV網(wǎng)C9C1C3C2C4C5C7C6C8C12C11C10拓?fù)渑判虻姆椒?）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之2）從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止C9C1C3C2C4C5C7C6C8C12C11C10拓?fù)渑判蛩惴ǎ?）掃描頂點(diǎn)表，求各頂點(diǎn)入度indegree[0..vernum-1]2）初始化棧，入度為0的頂點(diǎn)入棧，計(jì)數(shù)count=0;3）當(dāng)棧不空時(shí)重復(fù)

1、取棧頂頂點(diǎn)，并輸出，計(jì)數(shù)count++;2、取該頂點(diǎn)的所有鄰接點(diǎn)將其入度減1，若減1后入度為0，則該頂點(diǎn)入棧。4）當(dāng)?？諘r(shí)，若輸出的頂點(diǎn)數(shù)count小于圖的頂點(diǎn)數(shù)，則圖有回路，否則正常StatusTopologicalSort(ALGraphG){FindInDegree(G,indegree);//求各頂點(diǎn)的入度indegree[0..vernum-1]InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(S,i);count=0;while(!StackEmpty(S)){Pop(S,i);printf(i,G.vertices[i].data);++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!(--indegree[k]))Push(S,k);}}if(count<G.vexnum)returnERROR;elsereturnOK;}時(shí)間復(fù)雜度：O(n+e)二、關(guān)鍵路徑問題提出：把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；權(quán)表示活動(dòng)持續(xù)的時(shí)間。例設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件事件V1——表示整個(gè)工程開始事件V9——表示整個(gè)工程結(jié)束問題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE網(wǎng)(ActivityOnEdge)——邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間。路徑長度——路徑上各活動(dòng)持續(xù)時(shí)間之和關(guān)鍵路徑——路徑長度最長的路徑Ve(j)——表示事件Vj的最早發(fā)生時(shí)間Vl(j)——表示事件Vj的最遲發(fā)生時(shí)間e(i)——表示活動(dòng)ai的最早開始時(shí)間l(i)——表示活動(dòng)ai的最遲開始時(shí)間l(i)-e(i)——表示完成活動(dòng)ai的時(shí)間余量關(guān)鍵活動(dòng)——關(guān)鍵路徑上的活動(dòng)。987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40645771416181814167108660511求ve(j)和vl(j)需分兩步進(jìn)行：1）從ve(0)=0開始向前遞推：ve(j)=Max{ve(i)+dut(<i,j>)}

i

<i,j>Tj=1,2,…n-1其中：T為所有以j為頭的弧的集合ij2）從vl(n-1)=ve(n-1)起向后遞推：vl(i)=Min{vl(j)-dut(<i,j>)}

j

<i,j>Sj=1,2,…n-1其中：S為所有以i為尾的弧的集合ij算法實(shí)現(xiàn)1)從源點(diǎn)V1出發(fā)，令ve[0]=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)的最早開始時(shí)間ve[i]2）從匯點(diǎn)Vn出發(fā)，令vl[n-1]=ve[n-1],按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vl[i]3）根據(jù)各頂點(diǎn)的Ve和Vl值，計(jì)算每條弧的最早開始時(shí)間e[i]和最遲開始時(shí)間l[i],找出e[i]=l[i]的關(guān)鍵活動(dòng)StatusTopologicalOrder(ALGraphG,Stack&T){FindInDegree(G,indegree);//建立0入度頂點(diǎn)棧SInitStack(T);count=0;ve[0..G.vexnum–1]=0;while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;if(--indegree[k]==0)Push(S,k);if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);}}if(count<G.vexnum)returnERROR;elsereturnOK;}jkStatusCriticalPath(ALGraphG){if(!TopologicalOrder(G,T))returnERROR;vl[0..G.vexnum–1]=ve[G.vexnum–1];while(!StackEmpty(T))for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);if(vl[k]–dut<vl[j])vl[j]=vl[k]–dut;}for(j=0;j<G.vexnum;++j)for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);ee=ve[j];el=vl[k]–dut;tag=(ee==el)?’*’:‘’;printf(j,k,dut,ee,el,tag);}}jk時(shí)間復(fù)雜度：O(n+e)7.6最短路徑問題提出圖中：頂點(diǎn)：表示城市邊：表示城市間的交通聯(lián)系權(quán)：表示此線路的長度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑ABC832用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)一、從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑迪杰斯特拉(Dijkstra)算法基本思想把圖中所有頂點(diǎn)分成兩組，第一組包含已確定最短路徑的頂點(diǎn)，第二組包含尚未確定最短路徑的頂點(diǎn)，按最短路徑遞增的順序，逐個(gè)把第二組的頂點(diǎn)加到第一組中去，直至從V0出發(fā)可以達(dá)到的所有頂點(diǎn)都包含到第一組中。v0100v4v5v3v2v13060101020505第一組第二組v0v1,v2,v3,v4,v5v1=∞

v2=10v3=∞v4=30v5=100v2=10

v3=60(v2)v4=30v5=90(v4)v3=50(v4)

v5=60(v4v3)v5=60(v4v3)

v3=50(v4)

求最短路徑步驟初始時(shí)令S={V0},T={其余頂點(diǎn)}，T中頂點(diǎn)對(duì)應(yīng)的距離值若存在<V0,Vi>，為<V0,Vi>弧上的權(quán)值若不存在<V0,Vi>，為∞從T中選取一個(gè)其距離值為最小的頂點(diǎn)W，加入S對(duì)T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復(fù)上述步驟，直到S中包含所有頂點(diǎn)，即S=V為止voidDIJ(MgraphG,intv0,PathMatrix&P,ShortPathTable&D){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;if(D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;}}D[v0]=0;final[v0]=TRUE;for(i=1;i<G.vexnum;++i){min=INFINITY;for(w=0;w<G.vexnum;++w)if(!final[w])if(D[w]<min){v=w;min=D[w];}final[v]=TRUE;for(w=0;w<G.vexnum;++w)if(!final[w]&&(min+G.arcs[v][w]<D[w])){D[w]=min+G.arcs[v][w];P[w]=P[v];P[w][w]=TRUE;}}}時(shí)間復(fù)雜度：O(n2)二、每一對(duì)頂點(diǎn)之間的最短路徑方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次，

其時(shí)間復(fù)雜度為：O(n3)方法二：弗洛伊德(Floyd)算法算法基本思想：遞推地產(chǎn)生一個(gè)矩陣序列：D(-1