17.1圖的定義與基本術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.4圖的應(yīng)用第7章圖7.3圖的遍歷27.1圖的定義與基本術(shù)語(yǔ)第7章圖圖的結(jié)構(gòu)定義:圖是由頂點(diǎn)集V

和弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。

Graph=(V,R)其中:V={x|x∈DataObject}

R={VR}VR={<v,w>|P(v,w)且(v,w∈V)}

<v,w>表示從v到w的一條弧，

并稱(chēng)v為弧尾，w為弧頭。

P(v,w)定義了弧<x,y>的意義或信息,表示x和y間的特定關(guān)聯(lián)屬性。37.1圖的定義與基本術(shù)語(yǔ)第7章圖有向圖：由于“弧”是有方向的，因此稱(chēng)由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。例如:ABCDE其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}47.1圖的定義與基本術(shù)語(yǔ)第7章圖無(wú)向圖：由頂點(diǎn)集和邊集構(gòu)成的圖稱(chēng)作無(wú)向圖。例如:其中V2={A,B,C,D,E,F}E2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}若<v,w>VR必有<w,v>VR,則以(v,w)代替這兩個(gè)有序?qū)?稱(chēng)v和w之間存在一條邊。ABCDEF5有向圖或無(wú)向圖中的弧或邊帶權(quán)后的圖分別稱(chēng)作有向網(wǎng)或無(wú)向網(wǎng)。7.1圖的定義與基本術(shù)語(yǔ)第7章圖ABCDE159117322167.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)例如:設(shè)圖G=(V,{VR})和圖G=(V,{VR}),且VV,VRVR,則稱(chēng)G為G的子圖。ABCDEBCDAEDA77.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)假設(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)作稠密圖。87.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)若無(wú)向圖頂點(diǎn)v和w之間存在一條邊(v,w),則稱(chēng)頂點(diǎn)v和w互為鄰接點(diǎn),稱(chēng)邊(v,w)依附于頂點(diǎn)v和w或邊(v,w)與頂點(diǎn)v和w相關(guān)聯(lián)。與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目定義為v的度（ID）。例如:ABCDEFID(B)=3ID(A)=297.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)對(duì)于有向圖，若頂點(diǎn)v和w之間存在一條弧<v,w>則稱(chēng)頂點(diǎn)v鄰接到頂點(diǎn)w,頂點(diǎn)w鄰接自頂點(diǎn)v,稱(chēng)弧<v,w>與頂點(diǎn)v和w相關(guān)聯(lián)。以v為尾的弧的數(shù)目定義為v的出度（OD）。例如:OD(B)=1ID(B)=2以v為頭的弧的數(shù)目定義為v的入度（ID）。出度+入度=該頂點(diǎn)的度（TD）ABCDETD(B)=3107.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)設(shè)圖G=(V,{VR})中的{u=vi,0,vi,1,…,vi,m=w}頂點(diǎn)序列中,有(vi,j-1,vi,j)VR1≤j≤m,則稱(chēng)從頂點(diǎn)u到頂點(diǎn)w之間存在一條路徑。路徑上邊的數(shù)目稱(chēng)作路徑長(zhǎng)度，有向圖的路徑也是有向的。例如:路徑{A,E,C,D,B,C,D}路徑長(zhǎng)度為6ABCDE117.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)回路:首尾頂點(diǎn)相同的路徑。簡(jiǎn)單路徑:頂點(diǎn)不重復(fù)的路徑。{A,E,C,D}簡(jiǎn)單回路:中間頂點(diǎn)不重的回路ABCDE{B,C,D,B}{A,E,C,D,B,C,D,A}{A,E,C,D,A}127.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)若無(wú)向圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通,則稱(chēng)此圖為連通圖。若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱(chēng)作此圖的連通分量。ABCDEFABCDEFBAECFD137.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)對(duì)有向圖,若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱(chēng)此有向圖為強(qiáng)連通圖。否則,其各強(qiáng)連通子圖稱(chēng)作它的強(qiáng)連通分量。ABCDEABCDEBCDAE147.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊,其中n-1

條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖,稱(chēng)該極小連通子圖為此連通圖的生成樹(shù)。ABCDEFABCDFE157.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)對(duì)非連通圖，則稱(chēng)由各個(gè)連通分量的生成樹(shù)的集合為此非連通圖的生成森林。ABCDEFABCDEF

在圖中，我們可以將任一頂點(diǎn)看成是圖的第一個(gè)頂點(diǎn)，同理，對(duì)于任一頂點(diǎn)而言，它的鄰接點(diǎn)之間也不存在順序關(guān)系。為了操作的方便，我們需要將圖中的頂點(diǎn)按任意序列排列起來(lái)。頂點(diǎn)在這個(gè)人為的隨意排列中的位置序號(hào)稱(chēng)為頂點(diǎn)在圖中的位置。7.1圖的定義與基本術(shù)語(yǔ)第7章圖名詞和基本術(shù)語(yǔ)177.1圖的定義與基本術(shù)語(yǔ)第7章圖圖的抽象數(shù)據(jù)類(lèi)型ADTGraph{}ADTGraph數(shù)據(jù)對(duì)象V：一個(gè)集合，該集合中的所有元素具有相同的特性。數(shù)據(jù)關(guān)系R:R={VR}VR={<v,w>|P(v,w)∧(v,w∈V)}基本操作：1.CreatGraph(G);2.DestroyGraph(G);3.LocateVertex(G,v);4.GetVertex(G,i);5.InsertVertex(G,u);…P200187.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖①圖的鄰接矩陣表示法②圖的鄰接表表示法③有向圖的十字鏈表表示法④無(wú)向圖的鄰接多重表表示法197.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖①圖的鄰接矩陣表示法（數(shù)組表示法）一維數(shù)組：二維數(shù)組：用于存儲(chǔ)頂點(diǎn)信息。用于存儲(chǔ)圖中頂點(diǎn)之間關(guān)聯(lián)關(guān)系鄰接矩陣A[i,j]=若<vi,vj>或（vi,vj)

VR0反之ABCDEF010010100011000101001001110000011100ABCDEFABCDEF無(wú)向圖對(duì)稱(chēng)矩陣207.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖①圖的鄰接矩陣表示法（數(shù)組表示法）一維數(shù)組：二維數(shù)組：用于存儲(chǔ)頂點(diǎn)信息。用于存儲(chǔ)圖中頂點(diǎn)之間關(guān)聯(lián)關(guān)系鄰接矩陣A[i,j]=若<vi,vj>或（vi,vj)

VR0反之0100100100000101100000100ABCDEABCDEABCDE有向圖非對(duì)稱(chēng)矩陣217.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖①圖的鄰接矩陣表示法（數(shù)組表示法）一維數(shù)組：二維數(shù)組：用于存儲(chǔ)頂點(diǎn)信息。用于存儲(chǔ)圖中頂點(diǎn)之間關(guān)聯(lián)關(guān)系鄰接矩陣A[i,j]=若<vi,vj>或（vi,vj)

VR0反之∞15∞∞9∞∞3∞∞∞∞∞2∞117∞∞∞∞∞21∞∞ABCDEABCDEABCDE1591173221∞wij有向網(wǎng)非對(duì)稱(chēng)矩陣227.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖①圖的鄰接矩陣表示法（數(shù)組表示法）形式化描述#define

MAX_V

20#defineINFINITY

32768typedefenum{DG,DN,UDG,UDN}GraphKind;typedefcharVertexData;typedefArcNode{AdjType

adj;

OtherInfoinfo;}ArcNode;typedefstruct{

VertexData

vertex[MAX_V];

ArcNode

arcs[MAX_V][MAX_V];intvexnum,arcnum;

GraphKind

kind;}AdjMatrix;創(chuàng)建鄰接矩陣存儲(chǔ)的有向網(wǎng)intLocateVex(AdjMatrix*G,VertexDatav){intj=Error,k;for(k=0;k<G->vexnum;k++) if(G->vertex[k]==v) {j=k;break;}return(j);}intCreateDN(AdjMatrix*G)/*創(chuàng)建一個(gè)有向網(wǎng)*/{inti,j,k,weight;VertexDatav1,v2;scanf("%d,%d",&G->arcnum,&G->vexnum);for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++) G->arcs[i][j].adj=MAX;for(i=0;i<G->vexnum;i++)scanf("%c",&G->vertex[i]);

/*輸入圖的頂點(diǎn)*/for(k=0;k<G->arcnum;k++) {scanf("%c,%c,%d",&v1,&v2,&weight);

/*輸入一條弧的兩個(gè)頂點(diǎn)及權(quán)值*/ i=LocateVex(G,v1); j=LocateVex(G,v2); G->arcs[i][j].adj=weight; }return(Ok);}分析：算法的時(shí)間復(fù)雜度為O(n2+e×n).其中:O(n2)耗費(fèi)在對(duì)數(shù)組arcs的adj域初始化賦值上。

O(e×n)的時(shí)間耗費(fèi)在有向網(wǎng)中邊權(quán)的賦值上。

257.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖①圖的鄰接矩陣表示法（數(shù)組表示法）特點(diǎn)：Ⅰ.存儲(chǔ)空間無(wú)向圖（網(wǎng)）：n(n-1)/2有向圖（網(wǎng)）：n2注意：稀疏圖不適于用鄰接矩陣來(lái)存儲(chǔ)，因?yàn)檫@樣會(huì)造成存儲(chǔ)空間的浪費(fèi)。267.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖①圖的鄰接矩陣表示法（數(shù)組表示法）特點(diǎn)：Ⅱ.便于運(yùn)算無(wú)向圖（網(wǎng)）：TD（vi）=∑A[i,j]j=1n有向圖（網(wǎng)）：OD（vi）=∑A[i,j]j=1nID（vi）=∑A[j,i]j=1n1、判斷圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連。2、求頂點(diǎn)的度3、FirstAdjVertex(G,v)a、找v在G.Vertex[]中的下標(biāo)ib、找G.arc[i][]中第一個(gè)非零分量的列下標(biāo)jc、j或者G.Vertex[j]中的信息即為所求277.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖②圖的鄰接表表示法（鏈?zhǔn)酱鎯?chǔ)法）Ⅰ.表頭結(jié)點(diǎn)Ⅱ.表結(jié)點(diǎn)對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊。datafirstarc圖adjvexnextarc網(wǎng)adjvexnextarcinfo287.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖②圖的鄰接表表示法（鏈?zhǔn)酱鎯?chǔ)法）ABCDEF12345625∧156∧46∧36∧12∧234∧ABCDEF無(wú)向圖297.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖②圖的鄰接表表示法（鏈?zhǔn)酱鎯?chǔ)法）ABCDE1234525∧3∧4∧12∧3∧ABCDE有向圖307.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖②圖的鄰接表表示法（鏈?zhǔn)酱鎯?chǔ)法）ABCDE12345ABCDE1591173221有向網(wǎng)21559∧33∧42∧11127∧321∧317.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖②圖的鄰接表表示法（鏈?zhǔn)酱鎯?chǔ)法）形式化描述#defineMAX_V20#defineenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcNode{intadjvex;structArcNode*nextarc;OtherInfoinfo;}ArcNode;typedefstructVertexNode{VertexDatadata;

ArcNode*firstarc;}VertexNode;typedefstruct{

VertexNodevertex[MAX_V];intvexnum,arcnum;

GraphKindkind;}AdjList;327.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖②圖的鄰接表表示法（鏈?zhǔn)酱鎯?chǔ)法）特點(diǎn)：Ⅰ.無(wú)向圖存儲(chǔ)空間：Ⅱ.n+2e無(wú)向圖：TD（vi）=第i個(gè)單鏈表上結(jié)點(diǎn)的個(gè)數(shù)有向圖（網(wǎng)）：OD（vi）=第i個(gè)單鏈表上結(jié)點(diǎn)的個(gè)數(shù)ID（vi）掃描整個(gè)鄰接表逆鄰接表337.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖②圖的鄰接表表示法（鏈?zhǔn)酱鎯?chǔ)法）逆鄰接表ABCDE有向圖ABCDE123454∧4∧5∧3∧1∧12347.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖③有向圖的十字鏈表表示法（鏈?zhǔn)酱鎯?chǔ)法）頂點(diǎn)和弧分別各用一種存儲(chǔ)結(jié)構(gòu)的結(jié)點(diǎn)表示?；☆^相同的弧被鏈在同一鏈表上，弧尾相同的弧也被鏈在同一鏈表上，鏈表的頭結(jié)點(diǎn)就是頂點(diǎn)結(jié)點(diǎn)?；〉慕Y(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)tailvexheadvexhlinktlinkdatafirstinfirstout357.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖③有向圖的十字鏈表表示法ABCDE有向圖12345ABCDE1215∧23∧34∧4142∧53∧∧∧∧∧∧367.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖③有向圖的十字鏈表表示法形式化描述#defineMAX_VERTEX_NUM20#defineenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcNode{inttailvex,headvex;structArcNode*hlink,*tlink;InfoType*info;}ArcNode;typedefstructVertexNode{VertexDatadata;ArcNode*firstin,*firstout;}VertexNode;typedefstruct{VertexNodevertex[MAX_VERTEX_NUM];intvexnum,arcnum;GraphKindkind;}OrthList;377.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖④無(wú)向圖的鄰接多重表表示法頂點(diǎn)和邊分別各用一種存儲(chǔ)結(jié)構(gòu)的結(jié)點(diǎn)表示。依附于相同頂點(diǎn)的邊被鏈在同一鏈表上，每條邊依附于兩個(gè)頂點(diǎn)，所以每個(gè)邊結(jié)點(diǎn)同時(shí)被鏈接在兩個(gè)鏈表中，鏈表的頭結(jié)點(diǎn)就是頂點(diǎn)結(jié)點(diǎn)。同時(shí)還在邊結(jié)點(diǎn)中增加了一個(gè)訪(fǎng)問(wèn)標(biāo)志位。邊的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)markivexilinkjlinkjvexdatafirstedge387.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖④無(wú)向圖的鄰接多重表表示法無(wú)向圖ABCDEABCDE123451214∧32345235∧∧∧397.3圖的遍歷第7章圖從圖中某個(gè)頂點(diǎn)出發(fā)遍歷圖，訪(fǎng)遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次的過(guò)程。①深度優(yōu)先搜索②廣度優(yōu)先搜索407.3圖的遍歷第7章圖①深度優(yōu)先搜索基本思想：Ⅰ.從圖中某個(gè)頂點(diǎn)v0出發(fā)，首先訪(fǎng)問(wèn)v0;Ⅱ.找出剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)的第一個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)，然后訪(fǎng)問(wèn)該頂點(diǎn)。以該頂點(diǎn)為新頂點(diǎn)，重復(fù)此步驟，直到剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)沒(méi)有未被訪(fǎng)問(wèn)的鄰接點(diǎn)為止；Ⅲ.返回前一個(gè)訪(fǎng)問(wèn)過(guò)的且仍有未被訪(fǎng)問(wèn)的鄰接點(diǎn)的頂點(diǎn)，找出該頂點(diǎn)的下一個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)，訪(fǎng)問(wèn)該頂點(diǎn)。然后執(zhí)行步驟Ⅱ。類(lèi)似于樹(shù)的先根次序遍歷417.3圖的遍歷第7章圖①深度優(yōu)先搜索例如：ABCDEFGHIABCABCFEFEGGDDHHII回到A結(jié)束！深度優(yōu)先搜索樹(shù)每個(gè)頂點(diǎn)設(shè)置一個(gè)標(biāo)志用于檢查是否被訪(fǎng)問(wèn)過(guò)，即設(shè)置數(shù)組visited[n]，visited[i]=0未訪(fǎng)問(wèn)1已訪(fǎng)問(wèn)427.3圖的遍歷第7章圖①深度優(yōu)先搜索算法思想：遞歸Ⅰ.訪(fǎng)問(wèn)出發(fā)點(diǎn)v0;Ⅱ.依次以v0的未被訪(fǎng)問(wèn)的鄰接點(diǎn)為出發(fā)點(diǎn)，深度優(yōu)先搜索圖，直至圖中所有與v0有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)。對(duì)于非連通圖，則圖中一定還有頂點(diǎn)未被訪(fǎng)問(wèn)，要從圖中另選一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述深度優(yōu)先搜索過(guò)程。437.3圖的遍歷第7章圖①深度優(yōu)先搜索深度優(yōu)先遍歷圖g的算法描述#defineTrue1#defineFalse0intvisited[MAX_VERTEX_NUM];VoidTraverseGraph(Graphg){for(vi=0;vi<g.vexnum;vi++)visited[vi]=False;for(vi=0;vi<g.vexnum;vi++)if(!visited[vi])DepthFirstSearch(g,vi);}447.3圖的遍歷第7章圖①深度優(yōu)先搜索深度優(yōu)先遍歷v0所在的連通子圖voidDepthFirstSearch(Graphg,intv0){visit(v0);visited[v0]=True;

w=FirstAdjVertex(g,v0);while(w!=-1){if(!visited[w])DepthFirstSearch(g,w);

w=NextAdjVertex(g,v0,w);}}457.3圖的遍歷第7章圖①深度優(yōu)先搜索采用鄰接矩陣的DepthFirstSearchvoidDepthFirstSearch(AdjMaxtrig,intv0){visit(v0);visited[v0]=True;

for(vj=0;vj<g.vexnum;vj++)if(!visited[vj]&&g.arcs[v0][vj].adj==1)DepthFirstSearch(g,vj);}467.3圖的遍歷第7章圖①深度優(yōu)先搜索采用鄰接表的DepthFirstSearchvoidDepthFirstSearch(AdjListg,intv0){visit(v0);visited[v0]=True;p=g.vertex[v0].firstarc;while(p!=NULL){if(!visited[p->adjvex])DepthFirstSearch(g,vj);p=p->nexarc;}}477.3圖的遍歷第7章圖①深度優(yōu)先搜索非遞歸形式的DepthFirstSearchⅠ.首先將v0入棧；Ⅱ.只要棧不空，則重復(fù)下述處理：a.棧頂頂點(diǎn)出棧，如果未訪(fǎng)問(wèn)，則訪(fǎng)問(wèn)并置訪(fǎng)問(wèn)標(biāo)志；b.然后將v0所有未訪(fǎng)問(wèn)的鄰接點(diǎn)入棧。ABCDEFGHIA000000000IHGFEDCBAvisited[n]A1EDBB1ECC1FF1E1GG1HDD1H1II1487.3圖的遍歷第7章圖①深度優(yōu)先搜索非遞歸形式的DepthFirstSearchvoidDepthFirstSearch(Graphg,intv0){InitStack(S);Push(S,v0);while(!Empty(S))

{v=Pop(S);

if(!visited[v])

{visit(v);visited[v]=True;

w=FirstAdjVertex(g,v);

while(w!=-1)

{if(!visit[w])Push(S,w);

w=NextAdjVertex(g,v,w);

}}}}497.3圖的遍歷第7章圖②廣度優(yōu)先搜索基本思想：Ⅰ.從圖中某個(gè)頂點(diǎn)v0出發(fā)，首先訪(fǎng)問(wèn)v0;Ⅱ.依次訪(fǎng)問(wèn)v0各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)；Ⅲ.分別從這些鄰接點(diǎn)出發(fā)，依次訪(fǎng)問(wèn)它們的各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)。訪(fǎng)問(wèn)時(shí)應(yīng)保證：如果vi和vk為當(dāng)前端結(jié)點(diǎn)，且

vi在vk之前被訪(fǎng)問(wèn)，則vi的所有未被訪(fǎng)問(wèn)的鄰接點(diǎn)應(yīng)在vk

所有未被訪(fǎng)問(wèn)的鄰接點(diǎn)之前訪(fǎng)問(wèn)。重復(fù)Ⅲ，直到所有端結(jié)點(diǎn)均沒(méi)有未被訪(fǎng)問(wèn)的鄰接點(diǎn)為止。類(lèi)似于樹(shù)的層次遍歷507.3圖的遍歷第7章圖例如：ABCDEFGHIABABDECGFHI廣度優(yōu)先搜索樹(shù)每個(gè)頂點(diǎn)設(shè)置一個(gè)標(biāo)志用于檢查是否訪(fǎng)問(wèn)過(guò)，即設(shè)置數(shù)組visited[n]，visited[i]=0未訪(fǎng)問(wèn)1已訪(fǎng)問(wèn)②廣度優(yōu)先搜索EDCFGHI需要輔助隊(duì)列Q，以便實(shí)現(xiàn)訪(fǎng)問(wèn)時(shí)應(yīng)保證的一點(diǎn)！517.3圖的遍歷第7章圖算法思想：Ⅰ.訪(fǎng)問(wèn)出發(fā)點(diǎn)v0并置訪(fǎng)問(wèn)標(biāo)志，然后將v0入隊(duì);②廣度優(yōu)先搜索Ⅱ.只要隊(duì)不空，則重復(fù)下述處理：a.隊(duì)頭結(jié)點(diǎn)v出隊(duì)；b.對(duì)v的所有鄰接點(diǎn)w，如果w未被訪(fǎng)問(wèn)，則訪(fǎng)問(wèn)w并置訪(fǎng)問(wèn)標(biāo)志，然后w入隊(duì)。ABCDEFGHI000000000IHGFEDCBAvisited[n]A1ABDE111BDEC1CG1GF1FH1HI1I527.3圖的遍歷第7章圖圖g中v0所在的連通子圖算法②廣度優(yōu)先搜索

voidBreadthFirstSearch(Graphg,intv0)

{visit(v0);

visited[v0]=True;

InitQueue(&Q);

EnterQueue(&Q,v0)；

while(!Empty(Q))

{DeleteQueue(&Q,&v);

w=FirstAdj(g,v);

while(w!=-1)

{if(!visited(w))

{visit(w);visited[w]=True;

EnterQueue(&Q,w);

}

w=NextAdj(g,v,w);

}

}

}537.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題2.有向無(wú)環(huán)圖的應(yīng)用3.最短路徑問(wèn)題547.4圖的應(yīng)用第7章圖可以利用圖的遍歷來(lái)判斷一個(gè)圖是否連通，如果在遍歷的過(guò)程中，不止一次調(diào)用搜索過(guò)程，則說(shuō)明該圖就是一個(gè)非連通圖，并且?guī)状握{(diào)用搜索過(guò)程，表明該圖就有幾個(gè)連通分量。1.圖的連通性問(wèn)題①無(wú)向圖的連通分量AJCFEGBIDHABDCIEFGHJ557.4圖的應(yīng)用第7章圖有條件的圖的遍歷過(guò)程。1.圖的連通性問(wèn)題②圖中兩個(gè)頂點(diǎn)之間的簡(jiǎn)單路徑求從頂點(diǎn)B到頂點(diǎn)K的一條簡(jiǎn)單路徑。ABGCDEFHK例如：從頂點(diǎn)B出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。第一個(gè)鄰接點(diǎn)是CABCDEKHABEKBCHDAEKFG第一個(gè)鄰接點(diǎn)是ABADHCEKFG結(jié)論:1.從頂點(diǎn)i到頂點(diǎn)s,若存在路徑，則從頂點(diǎn)i出發(fā)進(jìn)行深度優(yōu)先搜索，必能搜索到頂點(diǎn)s。2.遍歷過(guò)程中搜索到的頂點(diǎn)不一定是路徑上的頂點(diǎn)。3.由它出發(fā)進(jìn)行的深度優(yōu)先遍歷已經(jīng)搜索完所有鄰接點(diǎn)而未到達(dá)終點(diǎn)的頂點(diǎn)不是路徑上的頂點(diǎn)。7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題②圖中兩個(gè)頂點(diǎn)之間的簡(jiǎn)單路徑voidDFS-p(Graphg,intu,intv)/*深度優(yōu)先搜索策略找u到v的簡(jiǎn)單路徑,數(shù)組pre[i]

記錄訪(fǎng)問(wèn)路徑,已初始化pre[i]=-1表示vi未訪(fǎng)問(wèn)*/{intj;for(j=firstadj(g,u);j>0;j=nextadj(g,u,j))ifpre[j]==-1{pre[j]=u;

if(j==v)print-path(pre,v);

/*輸出路徑*/elseDFS-p(g,j,v);}}7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題②圖中兩個(gè)頂點(diǎn)之間的簡(jiǎn)單路徑求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑

若兩個(gè)頂點(diǎn)之間存在多條路徑，則其中必有一條路徑長(zhǎng)度最短的路徑。如何求得這條路徑?abchdekfg

因此，求路徑長(zhǎng)度最短的路徑可以用廣度優(yōu)先遍歷，但需要用鏈隊(duì)列并修改它的結(jié)點(diǎn)結(jié)構(gòu)(增加一個(gè)指向上一層鄰接點(diǎn)的指針)及其入隊(duì)列和出隊(duì)列的算法。

深度優(yōu)先搜索訪(fǎng)問(wèn)頂點(diǎn)的次序取決于圖的存儲(chǔ)結(jié)構(gòu)，而廣度優(yōu)先搜索訪(fǎng)問(wèn)頂點(diǎn)的次序是按“路徑長(zhǎng)度”漸增的次序。0312475例:求圖中頂點(diǎn)3至5的一條長(zhǎng)度最短的路徑。鏈隊(duì)列的狀態(tài)如下所示:321475689q.frontq.rearq.frontq.rearq.rearq.rearq.rearq.rearq.rearq.frontq.frontq.frontq.rearq.rearq.rearq.rear

從q.rear沿鏈隊(duì)列前驅(qū)域向前直到頂點(diǎn)3即得長(zhǎng)度最短的路徑。3)修改出隊(duì)列的操作。出隊(duì)列時(shí)，僅移動(dòng)隊(duì)頭指針，而不將隊(duì)頭結(jié)點(diǎn)從鏈表中刪除。1)將鏈隊(duì)列的結(jié)點(diǎn)改為“雙鏈”結(jié)點(diǎn)。即結(jié)點(diǎn)中包含next和pred兩個(gè)指針；2)修改入隊(duì)列的操作。插入新的隊(duì)尾結(jié)點(diǎn)時(shí)，令其pred域的指針指向剛剛出隊(duì)列的結(jié)點(diǎn)，即當(dāng)前的隊(duì)頭指針?biāo)附Y(jié)點(diǎn)；

連通圖的極小連通子圖稱(chēng)為圖的生成樹(shù),顯然頂點(diǎn)數(shù)為n的連通圖,生成樹(shù)邊數(shù)為n-1。

非連通圖,對(duì)每個(gè)連通分量,通過(guò)遍歷可得到一棵生成樹(shù)。各個(gè)連通分量的生成樹(shù)可組成非連通圖的生成樹(shù)森林。

從連通圖中某一頂點(diǎn)出發(fā)遍歷圖時(shí),圖中所有的頂點(diǎn)加上遍歷時(shí)經(jīng)過(guò)的邊所構(gòu)成的子圖T,恰好就是一棵生成樹(shù),7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)深度優(yōu)先生成樹(shù)achdekfbgchkfedabg7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)森林廣度優(yōu)先生成樹(shù)森林abchdekfg7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)問(wèn)題：

設(shè)在n個(gè)城市之間建立通訊網(wǎng),則要連通n個(gè)城市最少需要修建n-1條線(xiàn)路，現(xiàn)要拿出最節(jié)省經(jīng)費(fèi)的通訊網(wǎng)建設(shè)方案。

假設(shè)無(wú)向圖的每條邊表示兩城市之間一條線(xiàn)路,權(quán)值表示修建費(fèi)用,則該問(wèn)題歸結(jié)為求權(quán)值之和最小的生成樹(shù)問(wèn)題。7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)例如:195141827168213127abcdegf所得生成樹(shù)權(quán)值和=3+5+8+14+16+21=67148531621aedcbgf7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)

在e條帶權(quán)的邊中選取n-1條邊(不構(gòu)成回路)，使“權(quán)值之和”為最小!算法一：普里姆算法(Prim)該問(wèn)題為構(gòu)造網(wǎng)的最小生成樹(shù)問(wèn)題算法二：克魯斯卡爾算法(Kruskal)即:生成樹(shù)各邊權(quán)值之和為生成樹(shù)代價(jià)，其代價(jià)最小的生成樹(shù)為最小生成樹(shù)。7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)最小生成樹(shù)(MST)的性質(zhì)：

求最小生成樹(shù)的算法較多，主要利用最小生成樹(shù)性質(zhì)。

設(shè)N=（V,{E}）是一個(gè)連通圖，U是V的非空子集，若(u,v)是滿(mǎn)足u∈U且v∈V-U的具有最小權(quán)值的邊,則必存在一棵包含(u,v)的最小生成樹(shù)。

可用反證法證明之。7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)

設(shè)N=(V,{E})是連通網(wǎng)，prim算法步驟為：（1）初始U={u0}(u0∈V),TE=φ；（2）在所有u∈U,v∈V-U的邊中選一條代價(jià)最小的邊（u0，v0）并入集合TE，同時(shí)將v0并入U(xiǎn)；（3）重復(fù)（2）,直到U=V,TE含有n-1條邊。

此時(shí)T=(V,{TE})為N的最小生成樹(shù)。

7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)算法一：普里姆算法(Prim)步驟:707.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)算法一：普里姆算法(Prim)實(shí)例:abcdegf191827211271431658abcdegf所得生成樹(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)值最小的邊。UV-U7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)算法一：普里姆算法(Prim)算法思想727.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)算法一：普里姆算法(Prim)算法思想

連通網(wǎng)用帶權(quán)的鄰接矩陣表示,并設(shè)置一個(gè)輔助數(shù)組closedge[],

數(shù)組元素下標(biāo)對(duì)應(yīng)當(dāng)前V-U集中的頂點(diǎn)序號(hào)，元素值則記錄該頂點(diǎn)和U集中相連接的代價(jià)最小(最近)邊的頂點(diǎn)序號(hào)adjvex和權(quán)值lowcost.

即對(duì)v∈V-U的每個(gè)頂點(diǎn)，

closedge[v]記錄所有與v鄰接的、從U到V-U的那組邊中的最小邊的信息。737.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)算法一：普里姆算法(Prim)算法思想輔助數(shù)組：

min{cost(u,v)|u∈U,v∈V-U}closedge[v].lowcost=0v∈Uclosedge[v].adjvex

存放U中與v最近的頂點(diǎn)序號(hào)。

struct{vertexDataadjvex;intlowcost;}closedge[MAX_VERTEX_NUM];747.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)算法一：普里姆算法(Prim)算法思想演示abcdegf191827211271431658abcdegf∞19∞∞14∞1819

∞

5712∞∞∞5

∞

3

∞

∞∞∞73∞821∞1412∞8∞

∞16∞∞

∞

21

∞

∞

2718∞∞∞1627

∞lowcostadjvex7g6f5e4d3c2b1aclosedge[v]01a191a141a1805e125e85e1604d74d34d2103c5000普里姆算法MiniSpanTree_Prim(AdjMatrixgn,VertexDatau){k=LocateVertex(gn,u);closedge[k].low=0;

for(i=0;i<gn.vnum;i++)

if(i!=k){closedge[i].vex=u;closedge[i].low=gn.arcs[k][i].adj;}for(e=1;e<=gn.vnum-1;e++){k0=Min(closedge);u0=closedge[k0].vex;v0=gn.vexs[k0];printf(u0,v0);

closedge[k0].low=0;for(i=0;i<gn.vnum;i++)if(gn.arcs[k0][i].adj<closedge[i].low){closedge[i].low=gn.arcs[k0][i].adj;closedge[i].vex=v0;}}}時(shí)間復(fù)雜度O(n2)767.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)算法二：克魯斯卡爾算法(Kruskal)基本思路:

為使生成樹(shù)邊的權(quán)值之和達(dá)到最小,則盡可能地選取權(quán)值小的邊作為生成樹(shù)中的邊。（1）將n個(gè)頂點(diǎn)看成n個(gè)集合；（2）按權(quán)值由小到大的順序選擇邊，所選邊應(yīng)滿(mǎn)足兩個(gè)頂點(diǎn)不在同一個(gè)頂點(diǎn)集合內(nèi)，將該邊放到生成樹(shù)邊的集合中。同時(shí)將該邊的兩個(gè)頂點(diǎn)所

在的頂點(diǎn)集合合并；（3）重復(fù)（2）,直到所有的頂點(diǎn)在同一頂點(diǎn)集合內(nèi)。假設(shè)N=(V,{E})是連通網(wǎng)777.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)算法二：克魯斯卡爾算法(Kruskal)實(shí)例fabcdeg191827211271431658211431658算法描述:構(gòu)造非連通圖SG=(V,TE);初值邊集TE=

k=i=0;{i為邊的序號(hào),k為已選中的邊數(shù)}while(k<n-1){i=i+1;

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

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

則{輸出邊(u,v);

k=k+1;}}時(shí)間復(fù)雜度O(eloge)7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)算法二：克魯斯卡爾算法(Kruskal)兩種算法的比較普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法適應(yīng)范圍7.4圖的應(yīng)用第7章圖1.圖的連通性問(wèn)題③圖的生成樹(shù)與最小生成樹(shù)807.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用①拓?fù)渑判蚣僭O(shè)以有向圖表示一個(gè)工程的施工圖或程序的數(shù)據(jù)流圖,每個(gè)頂點(diǎn)代表一個(gè)活動(dòng),弧<vi,vj>表示活動(dòng)i必須先于活動(dòng)

j進(jìn)行,稱(chēng)為AOV-網(wǎng)

(activityonvertex),圖中不允許出現(xiàn)回路。檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判颉?17.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用①拓?fù)渑判蚝沃^“拓?fù)渑判颉?？?duì)有向圖進(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ì)于有回路的有向圖得不到拓?fù)溆行蛐蛄小?27.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用①拓?fù)渑判蚶纾嚎汕蟮猛負(fù)溆行蛐蛄校篈BCD或

ACBDBDAC存在回路，活動(dòng)互為前驅(qū)。無(wú)法執(zhí)行！837.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用①拓?fù)渑判蛉绾芜M(jìn)行拓?fù)渑判?？?從有向圖中選取一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，并輸出之；Ⅱ.從有向圖中刪去此頂點(diǎn)以及所有以它為尾的??；重復(fù)上述兩步，直至圖空，或者圖不空但找不到無(wú)前驅(qū)的頂點(diǎn)為止。847.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用①拓?fù)渑判蚶纾篊DAGFBHECDAGFBHEACBHDGFE沒(méi)有前驅(qū)的頂點(diǎn)

入度為零的頂點(diǎn)刪除頂點(diǎn)及它的出弧

弧頭頂點(diǎn)的入度減1

對(duì)于有向圖的不同存儲(chǔ)結(jié)構(gòu)，拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)是不同的?；卩徑泳仃嚤硎镜挠邢驁D拓?fù)渑判蚍椒ㄈ缦拢?/p>

設(shè)A為有向圖G的鄰接矩陣，則（1）找G中無(wú)前驅(qū)的頂點(diǎn)

—在A中找到值全為0的列；（2）刪除以i為起點(diǎn)的所有弧

—將矩陣中i對(duì)應(yīng)的行全部置為0。7.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用①拓?fù)渑判?、沒(méi)有前驅(qū)的頂點(diǎn)

入度為零的頂點(diǎn)2、刪除頂點(diǎn)及它的出弧

弧頭頂點(diǎn)的入度-1輔助數(shù)組記錄各頂點(diǎn)的入度；建棧記錄入度為零的頂點(diǎn)；基于鄰接表表示的有向圖拓?fù)渑判蚍椒ㄈ缦拢?.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用①拓?fù)渑判騛bcghdfeb

abhcdgfea

c

d

g

h

f

e

棧S:

10

a

3

7

20b 7831c

441d 57 52e 62f

573g 681h 6

2110010000拓?fù)渑判蛩惴╥ntTopoSort(AdjListG){FindID(G,indegree);/*求各頂點(diǎn)入度*/count=0;InitStack(&S);for(i=0;i<G.vexnum;i++) if(indegree[i]==0)Push(&S,i);

while(!StackEmpty(S)){Pop(&S,&i);printf("%c",G.vertex[i].data);count++;p=G.vertexes[i].firstarc;

while(p!=NULL) {k=p->adjvex;indegree[k]--; if(indegree[k]==0)Push(&S,k); p=p->nextarc;} }if(count<G.vexnum)return(Error);elsereturn(Ok);}時(shí)間復(fù)雜度為:O(n+e)求各頂點(diǎn)入度的函數(shù)voidFindID(AdjListG,intindegree[MAX]){inti;ArcNode*p;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++)

{p=G.vertexes[i].firstarc;

while(p!=NULL)

{indegree[p->adjvex]++;

p=p->nextarc;}}}

在有向圖中，用頂點(diǎn)表示事件，用弧表示活動(dòng)，弧的權(quán)值表示活動(dòng)所需要的時(shí)間。我們稱(chēng)此方法構(gòu)造的有向無(wú)環(huán)圖為邊表示活動(dòng)的網(wǎng)（ActivityOnEdgeNetwork）,簡(jiǎn)稱(chēng)AOE-網(wǎng)。

AOE-網(wǎng)常用于工程管理，人們最關(guān)心的是：1、整個(gè)工程需要多少時(shí)間完成？

2、哪些子活動(dòng)是影響工程進(jìn)度的“關(guān)鍵活動(dòng)”？7.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用②關(guān)鍵路徑AOE-網(wǎng)中的基本概念：源點(diǎn)：存在唯一的、入度為零的頂點(diǎn)，叫源點(diǎn)。匯點(diǎn)：存在唯一的、出度為零的頂點(diǎn)，叫匯點(diǎn)。關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的最長(zhǎng)帶權(quán)路徑長(zhǎng)度即為完成整個(gè)工程任務(wù)所需的時(shí)間，該路徑叫做關(guān)鍵路徑。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)叫做關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)的權(quán)值增加(活動(dòng)延期),將使AOE-網(wǎng)的最長(zhǎng)路徑長(zhǎng)度增加(整個(gè)工程延期)。

7.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用②關(guān)鍵路徑例如:6174c64521187244源點(diǎn)匯點(diǎn)abegkhfd求關(guān)鍵路徑的幾個(gè)重要定義：設(shè)：每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)事件,每條弧對(duì)應(yīng)一個(gè)活動(dòng),權(quán)值表示該活動(dòng)所需的時(shí)間,第i條弧<j,k>,其活動(dòng)持續(xù)時(shí)間記為dut(<j,k>)?，F(xiàn)定義:

1)“事件vj”的最早發(fā)生時(shí)間ve(j):

從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度。它表示：從源點(diǎn)到頂點(diǎn)j所有路徑的活動(dòng)均已完成,vj才能發(fā)生,它確定了所有以vj為尾的弧(活動(dòng))最早開(kāi)始的時(shí)間。7.4圖的應(yīng)用第7章圖2.有向無(wú)環(huán)圖的應(yīng)用②關(guān)鍵路徑2)“事件vk”的最晚發(fā)生時(shí)間vl(k):

在保證匯點(diǎn)最早發(fā)生時(shí)間不變的前提下，事件vk的最晚發(fā)生時(shí)間。表示：在不推遲整個(gè)工程工期的前提下,vk最遲必須發(fā)生的時(shí)間?？砂赐?fù)湫蛄星髒e(j)：

ve(0)=0；

ve(j)=Max{ve(t)＋dut(<t,j>)}

<t,j>∈以j為頭的弧的集合可按逆拓?fù)湫蛄星髒l(t)：

vl(n-1)=ve(n-1)；

vl(t)=Min{vl(j)-dut(<t,j>)}<t,j>∈以t為尾的弧的集合3)“活動(dòng)(i)”的最早開(kāi)始時(shí)間e(i):

若活動(dòng)(i)對(duì)應(yīng)弧<j,k>,則e(i)等于事件j的最早發(fā)生時(shí)間,即e(i)=ve(j)；它表示：活動(dòng)(i)的前驅(qū)活動(dòng)均結(jié)束，活動(dòng)(i)可以開(kāi)始進(jìn)行。4)“活動(dòng)(i)”的最晚開(kāi)始時(shí)間l(i):

若活動(dòng)(i)對(duì)應(yīng)弧<j,k>,則l(i)等于事件k的最遲發(fā)生時(shí)間減去活動(dòng)(i)的持續(xù)時(shí)間,即

l(i)=vl(k)–dut(<j,k>)。它表示：在不推遲整個(gè)工程工期的前提下,活動(dòng)(i)最晚可以開(kāi)始進(jìn)行的時(shí)間。5)活動(dòng)ai的松弛時(shí)間（時(shí)間余量）：

活動(dòng)ai的最晚開(kāi)始時(shí)間與ai的最早開(kāi)始時(shí)間之差：l(i)-e(i)。顯然:松弛時(shí)間（時(shí)間余量）為0的活動(dòng)為關(guān)鍵活動(dòng)。ve(j):

以它為頭的活動(dòng)結(jié)束,以它為尾的活動(dòng)可開(kāi)始;vl(k):

在不影響工期的情況下,它的發(fā)生時(shí)間;e(i):i的前趨已全部結(jié)束,i可以開(kāi)始;l(i):

在不影響工期的情況下,i最晚可以開(kāi)始的時(shí)間;事件發(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>)}3、求關(guān)鍵路徑的基本步驟：（1）求每個(gè)事件的最早發(fā)生時(shí)間ve(j)；（2）求每個(gè)事件的最晚發(fā)生時(shí)間vl(k)；（3）求每個(gè)活動(dòng)ai的最早開(kāi)始時(shí)間e(i)；（4）求每個(gè)活動(dòng)ai的最晚開(kāi)始時(shí)間l(i)；找出e(i)=l(i)的活動(dòng)ai，即為關(guān)鍵活動(dòng)。求關(guān)鍵路徑步驟的要點(diǎn)：

顯然求ve的順序應(yīng)該是按拓?fù)溆行虻拇涡?然而求vl的順序則應(yīng)是按拓?fù)淠嫘虻拇涡?；由于拓?fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄械哪嫘蛄?，所以?yīng)該在拓?fù)渑判虻倪^(guò)程中，另設(shè)一個(gè)“?！庇浵峦?fù)溆行蛐蛄?。例?0000000064571157151418181818181818181818161486610807拓?fù)溆行蛐蛄?a-d-f-c-b-e-h-g-k64521187244abcdefghk4、修改后的拓?fù)渑判蛩惴╥ntve[MAX_V];/*記每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間*/intTopoOrder(AdjListG,Stack*T)

/*G為有向網(wǎng)，T為返回拓?fù)湫蛄械臈?，S為存放入度為0的頂點(diǎn)的棧*/{intcount,i,j,k;ArcNode*p;intindegree[MAX_V];/*各頂點(diǎn)入度數(shù)組*/StackS;

InitStack(T);InitStack(&S);

/*初始化棧T,S*/

FindID(G,indegree);

/*求各個(gè)頂點(diǎn)的入度*/

for(i=0;i<G.vexnum;i++)if(indegree[i]==0)Push(&S,i);count=0;for(i=0;i<G.vexnum;i++)ve[i]=0;

/*初始化最早發(fā)生時(shí)間*/

while(!StackEmpty(S)){Pop(&S,&j);Push(T,j);count++;p=G.vertex[j].firstarc;

while(p!=NULL) {k=p->adjvex;if(--indegree[k]==0)Push(&S,k);

if(ve[j]+p->weight>ve[k])

/*球各頂點(diǎn)的ve值*/

ve[k]=ve[j]+p->weight;

p=p->nextarc;}}if(count<G.vexnum)return(Error);elsereturn(Ok);} 5、求關(guān)鍵路徑算法intCriticalPath(AdjListG){ArcNode*p;inti,j,k,dut,ei,li;chartag;intvl[MAX_V];StackT;if(!TopoOrder(G,&T))return(Error);for(i=0;i<G.vexnum;i++) vl[i]=ve[G.vexnum-1];while(!StackEmpty(T)){Pop(&T,&j);

p=G.vertex[j].firstarc;while(p!=NULL)/*求各頂點(diǎn)的vl值*/ {k=p->adjvex;dut=p->weight; if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;p=p->nextarc;}} for(j=0;j<G.vexnum;j++)/*求ei,li和關(guān)鍵活動(dòng)*/{p=G.vertex[j].firstarc;while(p!=NULL){k=p->Adjvex;dut=p->weight; ei=ve[j];li=vl[k]-dut;tag=(ei==li)?'*':'';printf("%c,%c,%d,%d,%d,%c\n",G.vertex[j].data,G.vertex[k].data,dut,ei,li,tag);

/*輸出關(guān)鍵活動(dòng)*/ p=p->nextarc;}}return(Ok);}算法的時(shí)間復(fù)雜度為O(n+e)。例見(jiàn)p233-2340645771514181814161078660000645777151414160236688710

從某頂點(diǎn)(源點(diǎn))出發(fā)到另一頂點(diǎn)(目的點(diǎn))的路徑中,有一條各邊(或弧)權(quán)值之和最小的路徑稱(chēng)為最短路徑。求最短路徑問(wèn)題可歸為:◆

從單源點(diǎn)到其余各點(diǎn)的最短路徑?！裘恳粚?duì)頂點(diǎn)之間的最短路徑。7.4圖的應(yīng)用第7章圖3.最短路徑問(wèn)題①求某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑

依最短路徑的長(zhǎng)度遞增的次序,逐個(gè)產(chǎn)生各最短路徑。迪杰斯特拉(Dijkstra)算法基本思想:

設(shè)有帶權(quán)的有向圖D=(V,{E})，D中的邊權(quán)為W(e)。已知源點(diǎn)為v0，求v0到其它各頂點(diǎn)的最短路徑。7.4圖的應(yīng)用第7章圖3.最短路徑問(wèn)題①求某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑源點(diǎn)vi…

若從源點(diǎn)v0到頂點(diǎn)vi的弧是v0到各點(diǎn)(最短)路徑集合中長(zhǎng)度最短者。vj則首先可確認(rèn)<v0,vi>是源點(diǎn)v0到頂點(diǎn)vi的最短路徑！7.4圖的應(yīng)用第7章圖3.最短路徑問(wèn)題①求某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑迪杰斯特拉(Dijkstra)算法基本思想:1)第一條(長(zhǎng)度最短的)最短路徑的特點(diǎn)：

在這條路徑上，必定只含一條弧,并且這條弧的權(quán)值最小。(設(shè)為v0

→vi)2)下一條(長(zhǎng)度次短的)最短路徑的特點(diǎn)：

它只可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)vj(只含一條弧);或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)vi,再到達(dá)vj(由兩條弧組成)。7.4圖的應(yīng)用第7章圖3.最短路徑問(wèn)題①求某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑迪杰斯特拉(Dijkstra)算法基本思想:3)再下一條長(zhǎng)度次短的最短路徑特點(diǎn):4)其余最短路徑的特點(diǎn)：

它可能有兩種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)vi、vj再到達(dá)該頂點(diǎn)(由多條弧組成)。

它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。7.4圖的應(yīng)用第7章圖3.最短路徑問(wèn)題①求某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑迪杰斯特拉(Dijkstra)算法基本思想:例：051234

帶權(quán)有向圖993060101055020終點(diǎn)第一次1∞210（0-2）3∞430（0-4）599（0-5）頂點(diǎn)0到各點(diǎn)的最短路徑已求出最短路徑的終點(diǎn)的集合S={12345}例：051234

帶權(quán)有向圖993060101055020終點(diǎn)第二次1∞210（0-2）3∞430（0-4）599（0-5）頂點(diǎn)0到各點(diǎn)的最短路徑已求出最短路徑的終點(diǎn)的集合S={12345}60(0-2-3)例：051234

帶權(quán)有向圖993060101055020終點(diǎn)第三次1∞210（0-2）360(0-2-3)430（0-4）599（0-5）頂點(diǎn)0到各點(diǎn)的最短路徑已求出最短路徑的終點(diǎn)的集合S={12345}50(0-4-3)90(0-4-5)例：051234

帶權(quán)有向圖993060101055020終點(diǎn)第四次1∞210（0-2）350(0-4-3)430（0-4）590(0-4-5)頂點(diǎn)0到各點(diǎn)的最短路徑已求出最短路徑的終點(diǎn)的集合S={12345}60(0-4-3-5)例：051234

帶權(quán)有向圖993060101055020終點(diǎn)第五次1∞210（0-2）350(0-4-3)430（0-4）560(0-4-3-5)頂點(diǎn)0到各點(diǎn)的最短路徑已求出最短路徑的終點(diǎn)的集合S={12345}例：051234

帶權(quán)有向圖993060101055020

最短路徑長(zhǎng)度（v0,v2）10（v0,v4）30（v0,v4,v3）50（v0,v4,v3,v5)60v0→v1∞7.4圖的應(yīng)用第7章圖3.最短路徑問(wèn)題①求某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑

迪杰斯特拉算法的實(shí)現(xiàn)帶權(quán)鄰接矩陣數(shù)組g.arcs

:

用g.arcs

[i][j]表示弧<vi,vj>上的權(quán)。(2)頂點(diǎn)分為兩組:S，V-SS中存放已求得最短路徑的終點(diǎn)的集合。(3)輔助一維數(shù)組dist:

若vi∈S,dist[i]表示源點(diǎn)到vi的最短路徑長(zhǎng)度若vi∈V-S,dist[i]表示源點(diǎn)到vi的只經(jīng)過(guò)S中的頂點(diǎn)的最短路徑。(4)路徑數(shù)組path:path[j]表示從v0到vj經(jīng)過(guò)的點(diǎn).1)存儲(chǔ)結(jié)構(gòu)7.4圖的應(yīng)用第7章圖3.最短路徑問(wèn)題①求某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑2）主要步