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

數(shù)據(jù)結(jié)構(gòu)課件第七章圖第一頁，共一百頁，2022年，8月28日

圖是由一個頂點集V和一個弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。Graph=(V,R)其中，R＝{<v,w>|v,w∈V且P(v,w)}

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

圖的結(jié)構(gòu)定義:VW第二頁，共一百頁，2022年，8月28日

由于“弧”是有方向的，因此稱由頂點集和弧集構(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>}第三頁，共一百頁，2022年，8月28日若<v,w>VR

必有<w,v>VR,則稱(v,w)為頂點v和頂點w之間存在一條邊。

BCADFE由頂點集和邊集構(gòu)成的圖稱作無向圖。例如: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)}第四頁，共一百頁，2022年，8月28日名詞和術(shù)語網(wǎng)、子圖

完全圖、稀疏圖、稠密圖鄰接點、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強連通圖、強連通分量生成樹、生成森林第五頁，共一百頁，2022年，8月28日ABECFAEABBC設(shè)圖G=(V,{VR})和圖

G=(V,{VR}),且

VV,VRVR,則稱

G為G的子圖。1597211132

弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。第六頁，共一百頁，2022年，8月28日假設(shè)圖中有

n

個頂點，e

條邊，則

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

含有e=n(n-1)條弧的有向圖稱作

有向完全圖；若邊或弧的個數(shù)e<nlogn，則稱作稀疏圖，否則稱作稠密圖。第七頁，共一百頁，2022年，8月28日

假若頂點v和頂點w之間存在一條邊，則稱頂點v

和w

互為鄰接點，ACDFE例如:ID(B)=3ID(A)=2邊(v,w)

和頂點v和w

相關(guān)聯(lián)。

和頂點v關(guān)聯(lián)的邊的數(shù)目定義為頂點v的度。B第八頁，共一百頁，2022年，8月28日頂點的出度:以頂點v為弧尾的弧的數(shù)目；ABECF對有向圖來說，頂點的入度:以頂點v為弧頭的弧的數(shù)目。頂點的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3第九頁，共一百頁，2022年，8月28日設(shè)圖G=(V,{VR})中的一個頂點序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,則稱從頂點u到頂點w之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長度。ABECF如:長度為3的路徑{A,B,C,F}簡單路徑:序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路:序列中第一個頂點和最后一個頂點相同的路徑。第十頁，共一百頁，2022年，8月28日若圖G中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖；若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BACDFEBACDFE第十一頁，共一百頁，2022年，8月28日

若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為強連通圖。ABECFABECF對有向圖，否則，其各個強連通子圖稱作它的強連通分量。第十二頁，共一百頁，2022年，8月28日

假設(shè)一個連通圖有n個頂點和e條邊，其中n-1條邊和n個頂點構(gòu)成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。BACDFE第十三頁，共一百頁，2022年，8月28日結(jié)構(gòu)的建立和銷毀插入或刪除頂點對鄰接點的操作對頂點的訪問操作遍歷插入和刪除弧基本操作第十四頁，共一百頁，2022年，8月28日CreatGraph(&G,V,VR)://按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷毀圖結(jié)構(gòu)的建立和銷毀第十五頁，共一百頁，2022年，8月28日對頂點的訪問操作LocateVex(G,u);

//若G中存在頂點u，則返回該頂點在

//圖中“位置”

；否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對v賦值value。第十六頁，共一百頁，2022年，8月28日對鄰接點的操作FirstAdjVex(G,v);

//返回v的“第一個鄰接點”。若該頂點//在G中沒有鄰接點，則返回“空”。NextAdjVex(G,v,w);

//返回v的（相對于w的）“下一個鄰接//點”。若w是v的最后一個鄰接點，則//返回“空”。第十七頁，共一百頁，2022年，8月28日插入或刪除頂點InsertVex(&G,v);

//在圖G中增添新頂點v。DeleteVex(&G,v);//刪除G中頂點v及其相關(guān)的弧。第十八頁，共一百頁，2022年，8月28日插入和刪除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是無向的，

//則還增添對稱弧<w,v>。DeleteArc(&G,v,w);

//在G中刪除弧<v,w>，若G是無向的，

//則還刪除對稱弧<w,v>。第十九頁，共一百頁，2022年，8月28日遍歷DFSTraverse(G,v,Visit());//從頂點v起深度優(yōu)先遍歷圖G，并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());

//從頂點v起廣度優(yōu)先遍歷圖G，并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。第二十頁，共一百頁，2022年，8月28日7.2圖的存儲表示一、圖的數(shù)組(鄰接矩陣)存儲表示二、圖的鄰接表存儲表示三、有向圖的十字鏈表存儲表示四、無向圖的鄰接多重表存儲表示第二十一頁，共一百頁，2022年，8月28日Aij={0(i,j)VR1(i,j)VR一、圖的數(shù)組(鄰接矩陣)存儲表示BACDFE定義:矩陣的元素為無向圖的鄰接矩陣為對稱矩陣ABCDEFABCDEF第二十二頁，共一百頁，2022年，8月28日有向圖的鄰接矩陣為非對稱矩陣ABDCEABCDEABCDE第二十三頁，共一百頁，2022年，8月28日鄰接矩陣表示法特點：1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；2）頂點v的度：在無向圖中等于二維數(shù)組對應(yīng)行（或列）中1的個數(shù)；在有向圖中,統(tǒng)計第i行1的個數(shù)可得頂點i的出度，統(tǒng)計第j列1的個數(shù)可得頂點j的入度。3）判斷兩頂點v、u是否為鄰接點：只需判二維數(shù)組對應(yīng)分量是否為1；4）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦值1或清0；5）設(shè)存儲頂點的一維數(shù)組大小為n(圖的頂點數(shù)n),G占用存儲空間：n+n2；G占用存儲空間只與它的頂點數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密的圖；第二十四頁，共一百頁，2022年，8月28日typedefstructArcCell{//弧的定義

VRTypeadj;//VRType是頂點關(guān)系類型

//對無權(quán)圖，用1或0表示相鄰否；

//對帶權(quán)圖，則為權(quán)值類型。

InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];第二十五頁，共一百頁，2022年，8月28日typedefstruct{//圖的定義

VertexType//頂點信息

vexs[MAX_VERTEX_NUM];AdjMatrixarcs;//弧的信息

intvexnum,arcnum;//頂點數(shù)，弧數(shù)

GraphKindkind;//圖的種類標志

}MGraph;第二十六頁，共一百頁，2022年，8月28日網(wǎng)絡(luò)的鄰接矩陣ABDCE1597211132第二十七頁，共一百頁，2022年，8月28日0A141B0452C353D254E015F123BACDFE二、圖的鄰接表存儲表示

同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點代表一條邊(邊結(jié)點),結(jié)點中有另一頂點的下標adjvex

和指針nextedge。第二十八頁，共一百頁，2022年，8月28日142301201234

ABCDE有向圖的鄰接表ABECD可見，在有向圖的鄰接表中不易找到指向該頂點的弧。第二十九頁，共一百頁，2022年，8月28日ABECD有向圖的逆鄰接表ABCDE30342001234在有向圖的鄰接表中，對每個頂點，鏈接的是指向該頂點的弧。第三十頁，共一百頁，2022年，8月28日鄰接表表示法特點：1）無向圖鄰接表邊結(jié)點數(shù)是邊數(shù)的兩倍.2）頂點vi的度：在無向圖中等于第i個鏈表中的結(jié)點數(shù)；在有向圖鄰接表中,第i行的結(jié)點數(shù)等于頂點i的出度，在有向圖逆鄰接表中,第i行的結(jié)點數(shù)等于頂點i的入度。3）在鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點4）設(shè)存儲頂點的一維數(shù)組大小為n(圖的頂點數(shù)n),G占用存儲空間：n+e；G占用存儲空間與它的頂點數(shù)和邊數(shù)有關(guān)；適用于邊稀疏的圖；第三十一頁，共一百頁，2022年，8月28日typedefstructArcNode{

intadjvex;//該弧所指向的頂點的位置

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

InfoType*info;//該弧相關(guān)信息的指針}ArcNode;adjvexnextarcinfo弧的結(jié)點結(jié)構(gòu)第三十二頁，共一百頁，2022年，8月28日typedefstructVNode{

VertexTypedata;//頂點信息

ArcNode*firstarc;//指向第一條依附該頂點的弧

}VNode,AdjList[MAX_VERTEX_NUM];

datafirstarc頂點的結(jié)點結(jié)構(gòu)第三十三頁，共一百頁，2022年，8月28日typedefstruct{

AdjListvertices;

intvexnum,arcnum;

intkind;//圖的種類標志

}ALGraph;圖的結(jié)構(gòu)定義第三十四頁，共一百頁，2022年，8月28日三、有向圖的十字鏈表存儲表示

弧的結(jié)點結(jié)構(gòu)弧尾頂點位置弧頭頂點位置弧的相關(guān)信息指向下一個有相同弧尾的結(jié)點指向下一個有相同弧頭的結(jié)點typedefstructArcBox{//弧的結(jié)構(gòu)表示

inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;

}VexNode;第三十五頁，共一百頁，2022年，8月28日頂點的結(jié)點結(jié)構(gòu)頂點信息數(shù)據(jù)指向該頂點的第一條入弧指向該頂點的第一條出弧typedefstructVexNode{//頂點的結(jié)構(gòu)表示

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;第三十六頁，共一百頁，2022年，8月28日typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//頂點結(jié)點(表頭向量)

intvexnum,arcnum;//有向圖的當前頂點數(shù)和弧數(shù)}OLGraph;有向圖的結(jié)構(gòu)表示(十字鏈表)第三十七頁，共一百頁，2022年，8月28日ABCDABCD010220233031320123第三十八頁，共一百頁，2022年，8月28日四、無向圖的鄰接多重表存儲表示typedefstructEbox{VisitIfmark;//訪問標記

intivex,jvex;//該邊依附的兩個頂點的位置

structEBox*ilink,*jlink;InfoType*info;//該邊信息指針}EBox;邊的結(jié)構(gòu)表示第三十九頁，共一百頁，2022年，8月28日typedefstruct{//鄰接多重表

VexBoxadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

}AMLGraph;頂點的結(jié)構(gòu)表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一條依附該頂點的邊}VexBox;無向圖的結(jié)構(gòu)表示第四十頁，共一百頁，2022年，8月28日ABCDE01234ABCDE010321232441第四十一頁，共一百頁，2022年，8月28日7.3圖的遍歷

從圖中某個頂點出發(fā)游歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。深度優(yōu)先搜索廣度優(yōu)先搜索遍歷應(yīng)用舉例第四十二頁，共一百頁，2022年，8月28日

從圖中某個頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到。一、深度優(yōu)先搜索遍歷圖連通圖的深度優(yōu)先搜索遍歷第四十三頁，共一百頁，2022年，8月28日Vw1SG1SG2SG3W1、W2和W3

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

的子圖。訪問頂點V：for(W1、W2、W3)

若該鄰接點W未被訪問，

則從它出發(fā)進行深度優(yōu)先搜索遍歷。w2w3w2第四十四頁，共一百頁，2022年，8月28日從上頁的圖解可見:1.從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；解決的辦法是：為每個頂點設(shè)立一個“訪問標志visited[w]”。2.如何判別V的鄰接點是否被訪問？第四十五頁，共一百頁，2022年，8月28日acbdegfFFFFFFFTTTTTTTacbdgfeacbgfed訪問標志:訪問次序:例如:01234560234516第四十六頁，共一百頁，2022年，8月28日voidDFS(GraphG,intv){//從頂點v出發(fā)，深度優(yōu)先搜索遍歷連通圖Gvisited[v]=TRUE;VisitFunc(v);

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

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

//對v的尚未訪問的鄰接頂點w//遞歸調(diào)用DFS}//DFS第四十七頁，共一百頁，2022年，8月28日首先將圖中每個頂點的訪問標志設(shè)為FALSE,之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。非連通圖的深度優(yōu)先搜索遍歷第四十八頁，共一百頁，2022年，8月28日abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg訪問標志:訪問次序:例如:012345678021345678第四十九頁，共一百頁，2022年，8月28日voidDFSTraverse(GraphG,

Status(*Visit)(intv)){

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

VisitFunc=Visit;

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

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

if(!visited[v])DFS(G,v);//對尚未訪問的頂點調(diào)用DFS}第五十頁，共一百頁，2022年，8月28日二、廣度優(yōu)先搜索遍歷圖Vw1w8w3w7w6w2w5w4對連通圖，從起始點V到其余各頂點必定存在路徑。其中，V->w1,V->w2,V->w8

的路徑長度為1；V->w7,V->w3,V->w5

的路徑長度為2；V->w6,V->w4

的路徑長度為3。w1Vw2w7w6w3w8w5w4第五十一頁，共一百頁，2022年，8月28日從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有和V0有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。第五十二頁，共一百頁，2022年，8月28日Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w4FFFFFFFFFTTTTTTTTT012345678VisitedQV訪問次序:w1w2w8w4w7w3w5w6第五十三頁，共一百頁，2022年，8月28日

voidBFSTraverse(GraphG,

Status(*Visit)(intv)){

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

InitQueue(Q);

//置空的輔助隊列Q

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

if(

!visited[v]){

//v尚未訪問

}

}//BFSTraverse……第五十四頁，共一百頁，2022年，8月28日visited[u]=TRUE;Visit(u);//訪問uEnQueue(Q,v);

//v入隊列while(!QueueEmpty(Q)){

DeQueue(Q,u);//隊頭元素出隊并置為ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))

if(!visited[w])

{

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

//訪問的頂點w入隊列

}//if}//while第五十五頁，共一百頁，2022年，8月28日

連通分量(Connectedcomponent)

當無向圖為非連通圖時,從圖中某一頂點出發(fā),利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點,只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點。圖的連通性問題LEDHGABFICJKM第五十六頁，共一百頁，2022年，8月28日

若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷,可求得無向圖的所有連通分量。求連通分量的算法需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量。對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。EDHGIKLABFCJMHGIKLABFCJMED第五十七頁，共一百頁，2022年，8月28日非連通無向圖DFS訪問序列:ALMJBFCDEGKHILABFCJMHGIKLABFCJMEDEDHGIKHGIKLABFCJMED第五十八頁，共一百頁，2022年，8月28日7.4(連通網(wǎng)的)最小生成樹

假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？問題：第五十九頁，共一百頁，2022年，8月28日構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）該問題等價于：算法一：（普里姆算法）第六十頁，共一百頁，2022年，8月28日假設(shè)N={V,{E})是連通網(wǎng)，TE是N上最小生成樹邊的集合。算法從U＝{u0}(u0∈V)，TE={}開始，重復(fù)執(zhí)行下述操作：在所有u∈V，v∈V-U的邊(u,v)∈E中找一條代價最小的邊（u0，v0）并入集合TE,同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=(V,{TE})為N的最小生成樹。普里姆算法的基本思想:第六十一頁，共一百頁，2022年，8月28日在生成樹的構(gòu)造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U

和尚未落在生成樹上的頂點集V-U

，則應(yīng)在所有連通U中頂點和V-U中頂點的邊中選取權(quán)值最小的邊。

一般情況下所添加的頂點應(yīng)滿足下列條件:第六十二頁，共一百頁，2022年，8月28日abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67第六十三頁，共一百頁，2022年，8月28日設(shè)置一個輔助數(shù)組，對每個頂點，記錄從頂點集U到V－U具有代價最小的邊：struct{VertexTypeadjvex;//U集中的頂點

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

adjvexlowcost第六十四頁，共一百頁，2022年，8月28日abcdegf195141827168213ae12dcb7aaa19141814e12ee8168d3dd7213c550123456U:V-U:abcdefgfg1621019∞∞14∞181905712∞∞∞503∞∞∞∞730821∞1412∞80∞16∞∞∞21∞02718∞∞∞16270abcdefgabcdefg第六十五頁，共一百頁，2022年，8月28日voidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法從頂點u出發(fā)構(gòu)造網(wǎng)G的最小生成樹

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ù)向生成樹上添加頂點;第六十六頁，共一百頁，2022年，8月28日

k=minimum(closedge);

//求出加入生成樹的下一個頂點(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};

第六十七頁，共一百頁，2022年，8月28日具體做法:先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止?？紤]問題的出發(fā)點:為使生成樹上邊的權(quán)值之和達到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。克魯斯卡爾算法的基本思想：第六十八頁，共一百頁，2022年，8月28日abcdegf195141827168213ae12dcbgf7148531621例如:7121819第六十九頁，共一百頁，2022年，8月28日算法描述:構(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++;}第七十頁，共一百頁，2022年，8月28日普里姆算法克魯斯卡爾算法時間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法第七十一頁，共一百頁，2022年，8月28日7.7拓撲排序

問題:

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

檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。第七十二頁，共一百頁，2022年，8月28日何謂“拓撲排序”？對有向圖進行如下操作：

按照有向圖給出的次序關(guān)系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點，則可以人為加上任意的次序關(guān)系。第七十三頁，共一百頁，2022年，8月28日例如：對于下列有向圖BDAC可求得拓撲有序序列：

ABCD

或

ACBD由此所得頂點的線性序列稱之為拓撲有序序列第七十四頁，共一百頁，2022年，8月28日BDAC反之，對于下列有向圖不能求得它的拓撲有序序列。因為圖中存在一個回路

{B,C,D}第七十五頁，共一百頁，2022年，8月28日如何進行拓撲排序？一、從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之；

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

有以它為尾的??；第七十六頁，共一百頁，2022年，8月28日abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

沒有前驅(qū)的頂點入度為零的頂點刪除頂點及以它為尾的弧弧頭頂點的入度減1第七十七頁，共一百頁，2022年，8月28日abcghdfe01234567abcdefgh266734645500112231indegree01234567sab輸出次序:b02hh1a01ccd0dgfe000第七十八頁，共一百頁，2022年，8月28日算法描述StatusTopologicalsort(ALGraphG){

FindinDegree(G,indegree);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;}第七十九頁，共一百頁，2022年，8月28日7.8關(guān)鍵路徑問題:

假設(shè)以有向網(wǎng)表示一個施工流圖，弧上的權(quán)值表示完成該項子工程所需時間。問：哪些子工程項是“關(guān)鍵工程”？即：哪些子工程項將影響整個工程的完成期限的。第八十頁，共一百頁，2022年，8月28日abcdefghk64521187244例如:“關(guān)鍵活動”指的是：該弧上的權(quán)值增加

將使有向圖上的最長路徑的長度增加。整個工程完成的時間為：從有向圖的源點到匯點的最長路徑。源點匯點6174第八十一頁，共一百頁，2022年，8月28日

如何求關(guān)鍵活動？“事件(頂點)”的最早發(fā)生時間ve(j)ve(j)=從源點到頂點j的最長路徑長度；“事件(頂點)”的最遲發(fā)生時間vl(k)

vl(k)=從頂點k到匯點的最短路徑長度。第八十二頁，共一百頁，2022年，8月28日

假設(shè)第i條弧為<j,k>

則對第i項活動言

“活動(弧)”的最早開始時間e(i)e(i)=ve(j)；

“活動(弧)”的最遲開始時間l(i)l(i)=vl(k)–dut(<j,k>)；活動ai的時間余量：l(i)-e(i)

若l[k]==e[k]表示活動ai是關(guān)鍵活動。jkai第八十三頁，共一百頁，2022年，8月28日

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

ve(源點)=0；

ve(k)=Max{ve(j)+dut(<j,k>)}vl(匯點)=ve(匯點)；

vl(j)=Min{vl(k)–dut(<j,k>)}第八十四頁，共一百頁，2022年，8月28日abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓撲有序序列:a-d-f-c-b-e-h-g-k第八十五頁，共一百頁，2022年，8月28日0645771514181814161078660000645777151414160236688710第八十六頁，共一百頁，2022年，8月28日

算法的實現(xiàn)要點:顯然，求ve的順序應(yīng)該是按拓撲有序的次序；

而求vl的順序應(yīng)該是按拓撲逆序的次序；因為拓撲逆序序列即為拓撲有序序列的逆序列，因此應(yīng)該在拓撲排序的過程中，另設(shè)一個“?！庇浵峦負溆行蛐蛄小５诎耸唔?，共一百頁，2022年，8月28日

StatusTopologicalOrder(ALGraphG,Stack&T){

FindinDdegree(G,indegree);InitStack(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)=dut(<j,k>)ve[k]=ve[j]+*(p->info);}}

if(count<G.vexnum)ruturnERROR;elsereturnOK;}第八十八頁，共一百頁，2022年，8月28日StatusCriticalPath(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->vextarc){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);}}第八十九頁，共一百頁，2022年，8月28日7.6兩點之間的

最短路徑問題求從某個源點到其余各點的最短路徑每一對頂點之間的最短路徑

第九十頁，共一百頁，2022年，8月28日求從源點到其余各點的最短路徑的算法的基本思想:依最短路徑的長度遞增的次序求得各條路徑源點v1…其中，從源點到頂點v的最短路徑是所有最短路徑中長度最短者。v2第九十一頁，共一百頁，2022年，8月28日這條路徑必定是直接從源點到該點v1只含一條弧，并且這條弧的權(quán)值最小。下一條路徑長度次短的最短路徑的特點：路徑長度最短的最短路徑的特點：它只可能有兩種情況：或者是直接從源點到該點v2(只含一條弧)；或者是從源點經(jīng)過頂點v1，再到達該頂點v2(由兩條弧組成)。第九十二頁，共一百頁，2022年，8月28日其余最短路徑的特點：再下一條路徑長度次短的最短路徑的特點:它可能有三種情況：或者是直接從源點到該點v3(只含一條弧)；或者是從源點經(jīng)過頂點v1，再到達該頂點(由兩條弧組成)；或者是從源點經(jīng)過頂點v2，再到達該頂點v3。它或者是直接從源點到該點(只含一條弧)；或者是從源點經(jīng)過已求得最短路徑的頂點，再到達該頂點。第九十三頁，共一百頁，2022年，8月28日求最短路徑的迪杰斯特拉算法：一般情況下，Dist[k]=<源點到頂點k的弧上的權(quán)值>或者=<源點到已求出最短路徑的頂點的路徑長度>+<已求出最短路徑的頂點到頂點k的弧上的權(quán)值>。

設(shè)置輔助數(shù)組Dist，其中每個分量Dist[k]表示當前所求得的從源點到其余各頂點k的最短路徑。第九十四頁，共一百頁，2022年，8月28日1）在所有從源點出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。2）修改其它各頂點的Dist[k]值。假設(shè)求得最短路徑的頂點