數(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ù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(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è)圖中頂點數(shù)為n，邊或弧數(shù)為e，則：對于無向圖，e的取值范圍為0~~n(n-1)/2具有n(n-1)/2條邊的無向圖稱為完全圖對于有向圖，e的取值范圍為0~~n(n-1)具有n(n-1)條邊的有向圖稱為有向完全圖和圖中邊相關(guān)的數(shù)叫作權(quán)（weigth）帶權(quán)的圖稱為網(wǎng)頂點的度是和該頂點相關(guān)聯(lián)的邊的數(shù)目。記作TD(v)以頂點v為頭的弧的數(shù)目稱為v的入度。記作ID(v)以頂點v為尾的弧的數(shù)目稱為v的出度。記作OD(v)頂點v的度TD(v)=ID(v)+OD(v)鄰接點：對于無向圖G=(V,{E})，如果邊(v,v’)∈E,則稱頂點v和v’互為鄰接點路徑：路徑是頂點的序列V={Vi0,Vi1,……Vin}，

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

Vj和從Vj到Vi都存在路徑，則稱G是強連通圖強連通分量：有向圖中的極大強連通子圖有向完全圖：具有n(n-1)條邊的有向圖無向完備圖：具有n(n-1)/2條邊的無向圖權(quán)：與圖的邊或弧相關(guān)的數(shù)網(wǎng)：帶權(quán)的圖7.2圖的存儲結(jié)構(gòu)多重鏈表例G12413V1V2^^V4^V3^例15324G2^V1V2V4^V5^V3實際中不適用數(shù)組表示法（鄰接矩陣）設(shè)G=(V,E)是有n1個頂點的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣A[i][j]=1,若(Vi,Vj)E或<Vi,Vj>E0,其它例G1v2v4v1v3例v1v5v3v2v4G2v1v3v2v4v1v3v2v4v5圖的數(shù)組（鄰接矩陣）存儲表示#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;特點：無向圖的鄰接矩陣對稱，可壓縮存儲；有n個頂點的無向圖需存儲空間為n(n+1)/2有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存儲空間為n2無向圖中頂點Vi的度TD(Vi)是鄰接矩陣中第i行元素之和有向圖中，頂點Vi的出度是鄰接矩陣中第i行元素之和頂點Vi的入度是鄰接矩陣中第i列元素之和易于實現(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^圖的鄰接表存儲表示#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é)點datafirstarc頭結(jié)點特點若無向圖中有n個頂點、e條邊，則需n個頭結(jié)點和2e個表結(jié)點無向圖中頂點Vi的度為第i個單鏈表中的結(jié)點數(shù)有向圖中頂點Vi的出度為第i個單鏈表中的結(jié)點個數(shù)頂點Vi的入度為整個單鏈表中鄰接點域值是i的結(jié)點個數(shù)逆鄰接表：有向圖中對每個結(jié)點建立以Vi為頭的弧的單鏈表例G1v2v4v1v30123v1v3v4v2vexdatafirstarc30^0^^2^adjvexnext

十字鏈表------有向圖的另一種存儲結(jié)構(gòu)tailvexheadvexhlinktlinkdatafirstinfirstout有向圖的十字鏈表存儲表示#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采用十字鏈表存儲結(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);}}無向圖的鄰接多重表存儲表示#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

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

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

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

]

④非連通圖解決方案：從任意一個未被訪問的結(jié)點出發(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);}問題：判斷給定圖是否是連通圖？多少個連通分量深度遍歷：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);}鄰接矩陣存儲結(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);}鄰接表存儲結(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;}

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

時間復(fù)雜度：O(n+e)二、廣度優(yōu)先搜索(BreadthFirstSearch)方法：從圖的某一頂點V出發(fā)，訪問了V之后，依次訪問V的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。廣度遍歷：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}

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

鄰接表存儲：O(n+e)V1V2V3V4V5V6V7V8問題：二叉樹按層次遍歷問題：迷宮問題7.4圖的連通性問題一、無向圖的連通分量和生成樹對無向非連同圖進行深度優(yōu)先遍歷三次調(diào)用得到的訪問序列為：ALMJBFCDEGKHIABCDEFGHIJKLMALJMBFCDEGKHI生成樹：所有頂點均由邊連接在一起，但不存在回路的圖。深度優(yōu)先生成樹與廣度優(yōu)先生成樹生成森林：非連通圖每個連通分量的生成樹一起組成非連通圖的生成森林。說明一個圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點：生成樹的頂點個數(shù)與圖的頂點個數(shù)相同生成樹是圖的極小連通子圖一個有n個頂點的連通圖的生成樹有n-1條邊生成樹中任意兩個頂點間的路徑是唯一的在生成樹中再加一條邊必然形成回路含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個頂點出發(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個城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點表示城市，邊上的權(quán)值表示城市間建立通信線路所需花費代價，現(xiàn)希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費的總代價）最小———最小代價生成樹。問題分析：991886261312n個城市間，最多有n(n-1)/2條線路n個城市間建立通信網(wǎng)，只需n-1條線路問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費(各邊權(quán)值之和)最小。構(gòu)造一個最小生成樹12345性質(zhì)：假設(shè)N=(V,{E})是一個連通網(wǎng)，U是頂點集V的一個非空子集。若（u,v）是一條具有最小權(quán)值（代價）的邊，其中uU,vV-U，則必存在一棵包含邊(u,v)的最小生成樹。普里姆(Prim)算法算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)將(u0,v0)并入集合TE，同時v0并入U重復(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個頂點而無邊的非連通圖T=(V,{})，每個頂點自成一個連通分量在E中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊依此類推，直至T中所有頂點都在同一連通分量上為止。1234565135664251234561234567.5有向無環(huán)圖及其應(yīng)用有向無環(huán)圖（DirectedAcyclineGraph）一個無環(huán)的有向圖,簡稱DAG圖DAG圖有向樹有向圖用有向無環(huán)圖描述含有公共子式的表達式例((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)*+**+ab*b+cd*+cde+cde*+*e*+*+abcd一、拓?fù)渑判蛲負(fù)渑判颍═opologicalSort）:由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱為拓?fù)渑判颉?/p>

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

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

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

1、取棧頂頂點，并輸出，計數(shù)count++;2、取該頂點的所有鄰接點將其入度減1，若減1后入度為0，則該頂點入棧。4）當(dāng)?？諘r，若輸出的頂點數(shù)count小于圖的頂點數(shù)，則圖有回路，否則正常StatusTopologicalSort(ALGraphG){FindInDegree(G,indegree);//求各頂點的入度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;}時間復(fù)雜度：O(n+e)二、關(guān)鍵路徑問題提出：把工程計劃表示為有向圖，用頂點表示事件，弧表示活動；權(quán)表示活動持續(xù)的時間。例設(shè)一個工程有11項活動，9個事件事件V1——表示整個工程開始事件V9——表示整個工程結(jié)束問題：（1）完成整項工程至少需要多少時間？（2）哪些活動是影響工程進度的關(guān)鍵？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE網(wǎng)(ActivityOnEdge)——邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)時間。路徑長度——路徑上各活動持續(xù)時間之和關(guān)鍵路徑——路徑長度最長的路徑Ve(j)——表示事件Vj的最早發(fā)生時間Vl(j)——表示事件Vj的最遲發(fā)生時間e(i)——表示活動ai的最早開始時間l(i)——表示活動ai的最遲開始時間l(i)-e(i)——表示完成活動ai的時間余量關(guān)鍵活動——關(guān)鍵路徑上的活動。987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40645771416181814167108660511求ve(j)和vl(j)需分兩步進行：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算法實現(xiàn)1)從源點V1出發(fā)，令ve[0]=0,按拓?fù)湫蛄星蟾黜旤c的最早開始時間ve[i]2）從匯點Vn出發(fā)，令vl[n-1]=ve[n-1],按逆拓?fù)湫蛄星笃溆喔黜旤c的最遲發(fā)生時間vl[i]3）根據(jù)各頂點的Ve和Vl值，計算每條弧的最早開始時間e[i]和最遲開始時間l[i],找出e[i]=l[i]的關(guān)鍵活動StatusTopologicalOrder(ALGraphG,Stack&T){FindInDegree(G,indegree);//建立0入度頂點棧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時間復(fù)雜度：O(n+e)7.6最短路徑問題提出圖中：頂點：表示城市邊：表示城市間的交通聯(lián)系權(quán)：表示此線路的長度或沿此線路運輸所花的時間或費用等問題：從某頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑ABC832用帶權(quán)的有向圖表示一個交通運輸網(wǎng)一、從某個源點到其余各頂點的最短路徑迪杰斯特拉(Dijkstra)算法基本思想把圖中所有頂點分成兩組，第一組包含已確定最短路徑的頂點，第二組包含尚未確定最短路徑的頂點，按最短路徑遞增的順序，逐個把第二組的頂點加到第一組中去，直至從V0出發(fā)可以達到的所有頂點都包含到第一組中。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)

求最短路徑步驟初始時令S={V0},T={其余頂點}，T中頂點對應(yīng)的距離值若存在<V0,Vi>，為<V0,Vi>弧上的權(quán)值若不存在<V0,Vi>，為∞從T中選取一個其距離值為最小的頂點W，加入S對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復(fù)上述步驟，直到S中包含所有頂點，即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;}}}時間復(fù)雜度：O(n2)二、每一對頂點之間的最短路徑方法一：每次以一個頂點為源點，重復(fù)執(zhí)行Dijkstra算法n次，

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