數(shù)據結構課件第一頁，共九十八頁，編輯于2023年，星期三7.1圖的定義和術語7.2圖的存儲結構7.3圖的遍歷7.4圖的連通性7.5拓撲排序和關鍵路徑7.6最短路徑問題第二頁，共九十八頁，編輯于2023年，星期三

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

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

謂詞P(v,w)定義了弧<v,w>的意義或信息。7.1圖的定義和術語第三頁，共九十八頁，編輯于2023年，星期三

由于“弧”是有方向的，因此稱由頂點集和弧集構成的圖為有向圖。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>}第四頁，共九十八頁，編輯于2023年，星期三若<v,w>VR

必有<w,v>VR,則稱(v,w)為頂點v和頂點w之間存在一條邊。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)}第五頁，共九十八頁，編輯于2023年，星期三名詞和術語網、子圖

完全圖、稀疏圖、稠密圖鄰接點、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強連通圖、強連通分量生成樹、生成森林第六頁，共九十八頁，編輯于2023年，星期三ABECFAEFBBC設圖G=(V,{VR})和圖

G=(V,{VR}),且

VV,VRVR,則稱

G為G的子圖。1597211132

弧或邊帶權的圖分別稱作有向網或無向網。第七頁，共九十八頁，編輯于2023年，星期三假設圖中有

n

個頂點，e

條邊，則

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

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

有向完全圖;若邊或弧的個數(shù)e<nlogn，則稱作稀疏圖，否則稱作稠密圖。第八頁，共九十八頁，編輯于2023年，星期三

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

和w

互為鄰接點，例如:TD(B)=3TD(A)=2

邊(v,w)

和頂點v和w

相關聯(lián)。

和頂點v相關聯(lián)的邊的數(shù)目定義為頂點v的度，記為TD（v）。ACDFEB右側圖中第九頁，共九十八頁，編輯于2023年，星期三頂點的出度:以頂點v為弧尾的弧的數(shù)目;ABECF對有向圖來說，頂點的入度:以頂點v為弧頭的弧的數(shù)目。頂點的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3由于弧有方向性，則有入度和出度之分第十頁，共九十八頁，編輯于2023年，星期三設圖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長度為3的路徑{A,B,C,F}簡單路徑:指序列中頂點不重復出現(xiàn)的路徑。簡單回路:指序列中第一個頂點和最后一個頂點相同的路徑。第十一頁，共九十八頁，編輯于2023年，星期三若圖G中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖;若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BACDFEBACDFE第十二頁，共九十八頁，編輯于2023年，星期三

若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為強連通圖。ABECFABECF對有向圖，否則，其各個強連通子圖稱作它的強連通分量。第十三頁，共九十八頁，編輯于2023年，星期三

假設一個連通圖有n個頂點和e條邊，其中n-1條邊和n個頂點構成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。BACDFE第十四頁，共九十八頁，編輯于2023年，星期三結構的建立和銷毀插入和刪除頂點對鄰接點的操作對頂點的訪問操作遍歷插入和刪除弧基本操作第十五頁，共九十八頁，編輯于2023年，星期三CreatGraph(&G,V,VR)；

//按定義(V,VR)構造圖DestroyGraph(&G)；

//銷毀圖結構的建立和銷毀第十六頁，共九十八頁，編輯于2023年，星期三對頂點的訪問操作LocateVex(G,u);

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

//圖中“位置”

；否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對v賦值value。第十七頁，共九十八頁，編輯于2023年，星期三對鄰接點的操作FirstAdjVex(G,v);

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

//返回v的（相對于w的）“下一個鄰接//點”。若w是v的最后一個鄰接點，則//返回“空”。第十八頁，共九十八頁，編輯于2023年，星期三插入和刪除頂點InsertVex(&G,v);

//在圖G中增添新頂點v。DeleteVex(&G,v);//刪除G中頂點v及其相關的弧。第十九頁，共九十八頁，編輯于2023年，星期三插入和刪除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是無向的，

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

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

//則還刪除對稱弧<w,v>。第二十頁，共九十八頁，編輯于2023年，星期三遍歷DFSTraverse(G,v,Visit());//從頂點v起深度優(yōu)先遍歷圖G，并對每//個頂點調用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());

//從頂點v起廣度優(yōu)先遍歷圖G，并對每//個頂點調用函數(shù)Visit一次且僅一次。第二十一頁，共九十八頁，編輯于2023年，星期三7.2圖的存儲結構一、圖的數(shù)組(鄰接矩陣)存儲表示二、圖的鄰接表存儲表示三、有向圖的十字鏈表存儲表示四、無向圖的鄰接多重表存儲表示第二十二頁，共九十八頁，編輯于2023年，星期三Aij={0(i,j)VR1(i,j)VR一、圖的數(shù)組(鄰接矩陣)存儲表示BACDFE定義:矩陣的元素為第二十三頁，共九十八頁，編輯于2023年，星期三有向圖的鄰接矩陣為非對稱矩陣ABECD第二十四頁，共九十八頁，編輯于2023年，星期三#defineMAXVERTEXNUM20typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcCell{//弧的定義

VRTypeadj;//VRType是頂點關系類型。

//對無權圖，用1或0表示相鄰否；

//對帶權圖，則為權值類型。

InfoType*info;//該弧相關信息的指針}ArcCell,AdjMatrix[MAXVERTEXNUM][MAXVERTEXNUM];第二十五頁，共九十八頁，編輯于2023年，星期三typedefstruct{//圖的定義

VertexTypevexs[MAXVERTEXNUM];//頂點信息

AdjMatrixarcs;//弧的信息

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

GraphKindkind;//圖的種類標志

}MGraph;第二十六頁，共九十八頁，編輯于2023年，星期三DBACFE二、圖的鄰接表存儲表示

A14

B045

C35

D25

E01

F123012345第二十七頁，共九十八頁，編輯于2023年，星期三有向圖的鄰接表142301201234

ABCDEABECD可見，在有向圖的鄰接表中不易找到指向該頂點的弧第二十八頁，共九十八頁，編輯于2023年，星期三ABECD有向圖的逆鄰接表在有向圖的逆鄰接表中，對每個頂點，鏈接的是指向該頂點的弧01234ABCDE3032041第二十九頁，共九十八頁，編輯于2023年，星期三typedefstructArcNode{

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

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

InfoType*info;//該弧相關信息的指針}ArcNode;adjvexnextarcinfo弧的結點結構第三十頁，共九十八頁，編輯于2023年，星期三typedefstructVNode{

VertexTypedata;//頂點信息

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

}VNode,AdjList[MAXVERTEXNUM];

datafirstarc頂點的結點結構第三十一頁，共九十八頁，編輯于2023年，星期三typedefstruct{

AdjListvertices;

intvexnum,arcnum;

intkind;//圖的種類標志

}ALGraph;圖的結構定義(鄰接表)第三十二頁，共九十八頁，編輯于2023年，星期三三、有向圖的十字鏈表存儲表示

ABCABC012∧02∧∧0121∧20∧∧第三十三頁，共九十八頁，編輯于2023年，星期三弧的結點結構弧尾頂點位置弧頭頂點位置弧的相關信息指向下一個有相同弧尾的結點指向下一個有相同弧頭的結點typedefstructArcBox{//弧的結構表示

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

}

ArcBox;tailvexheadvexhlinktlinkinfo第三十四頁，共九十八頁，編輯于2023年，星期三頂點的結點結構頂點信息數(shù)據指向該頂點的第一條入弧指向該頂點的第一條出弧typedefstructVexNode{//頂點的結構表示

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;datafirstinfirstout第三十五頁，共九十八頁，編輯于2023年，星期三typedefstruct{VexNodexlist[MAXVERTEXNUM];//頂點結點(表頭向量)

intvexnum,arcnum;//有向圖的當前頂點數(shù)和弧數(shù)}OLGraph;有向圖的結構表示(十字鏈表)第三十六頁，共九十八頁，編輯于2023年，星期三四、無向圖的鄰接多重表存儲表示typedefstructEbox{VisitIfmark;//訪問標記

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

structEBox*ilink,*jlink;InfoType*info;//該邊信息指針}EBox;邊的結構表示第三十七頁，共九十八頁，編輯于2023年，星期三typedefstruct{//鄰接多重表

VexBoxadjmulist[MAXVERTEXNUM];

intvexnum,edgenum;

}AMLGraph;頂點的結構表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一條依附該頂點的邊}VexBox;無向圖的結構表示第三十八頁，共九十八頁，編輯于2023年，星期三7.3圖的遍歷

從圖中某個頂點出發(fā)游歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次的過程。深度優(yōu)先搜索廣度優(yōu)先搜索第三十九頁，共九十八頁，編輯于2023年，星期三

從圖中某個頂點V0

出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到。一、深度優(yōu)先搜索遍歷圖連通圖的深度優(yōu)先搜索遍歷第四十頁，共九十八頁，編輯于2023年，星期三SG1SG2SG3W1、W2和W3

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

的子圖。訪問頂點V

;for(W1、W2、W3)

若該鄰接點W未被訪問，

則從它出發(fā)進行深度優(yōu)先搜索遍歷。Vw1w3w2第四十一頁，共九十八頁，編輯于2023年，星期三從上頁的圖解可見:1.從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;解決的辦法是:為每個頂點設立一個“訪問標志visited[w]”;2.如何判別V的鄰接點是否被訪問？第四十二頁，共九十八頁，編輯于2023年，星期三如圖G4：深到底回退深到底V1V2V4V8V5（V2V8均已訪問）深到底V3V6V7回退訪問V1V2V3V4V5V6V7V8

visited[0..n-1]是一個輔助數(shù)組，記載頂點是否被訪問過visited[i]=TRUE,已訪問過FALSE,未訪問過（初值）注意：DFS序列不唯一，它與算法、圖的存儲結構及初始出發(fā)點有關。第四十三頁，共九十八頁，編輯于2023年，星期三深度優(yōu)先搜索遞歸過程（采用鄰接矩陣存儲圖）：

voidDFS(MGraphG,inti)){cout<<G.vex[i]<<“--->”;visited[i]=TRUE;for(j=0;j<G.vexnum;++j){if(!visited[j]&&G.arcs[i][j].adj)

DFS(G,j);}}第四十四頁，共九十八頁，編輯于2023年，星期三深度優(yōu)先搜索遞歸過程（采用鄰接表存儲圖）：voidDFS(ALGraphG,inti){cout<<G.vertices[i].data<<“--->”;visited[i]=TRUE;p=G.vertices[i].firstarc;while(p){if(!visited[p->adjvex])DFS(G,p->adjvex);

p=p->nextarc;}}第四十五頁，共九十八頁，編輯于2023年，星期三首先將圖中每個頂點的訪問標志設為FALSE,之后搜索圖中每個頂點，如果未被訪問，則以該頂點為起始點，進行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點。非連通圖的深度優(yōu)先搜索遍歷第四十六頁，共九十八頁，編輯于2023年，星期三voidDFSTraverse(GraphG)

{

//對圖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);//對尚未訪問的頂點調用DFS}思考：DFSTraverse調用DFS的次數(shù)由什么決定？第四十七頁，共九十八頁，編輯于2023年，星期三abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg訪問標志:訪問次序:例如:achdkfe第四十八頁，共九十八頁，編輯于2023年，星期三二、廣度優(yōu)先搜索遍歷圖Vw1w8w3w7w6w2w5w4對連通圖，從起始點V到其余各頂點必定存在路徑。其中，V->w1,V->w2,V->w8

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

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

的路徑長度為3。w1Vw2w7w6w3w8w5w4第四十九頁，共九十八頁，編輯于2023年，星期三從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。第五十頁，共九十八頁，編輯于2023年，星期三廣度優(yōu)先搜索（breadth-first-search)首先訪問指定頂點v0，將v0作為當前頂點;

訪問當前頂點的所有未訪問過的鄰接點，并依次將訪問的這些鄰接點作為當前頂點;

重復2），直到所有頂點被訪問為止。對右圖廣度優(yōu)先搜索，訪問頂點序列為：

V1V2V3V4V5V6V7V8V8V1V2V3V4V5V6V7注意：BFS序列不唯一，它與算法、圖的存儲結構及初始出發(fā)點有關。第五十一頁，共九十八頁，編輯于2023年，星期三廣度優(yōu)先搜索算法（以鄰接矩陣作存儲結構）：voidBFSTraverse(MGraphG){for(i=0;i<G.vexnum;++i)visited[i]=FALSE;InitQueue(Q);for(i=0;i<G.vexnum;++i)if(!visited[i]){visited[i]=TRUE;cout<<G.vexs[i];EnQueue(Q,i);while(!QueueEmpty(Q)){DeQueue(Q,k);for(j=0;j<G.vexnum;++j)if(!visited[j]&&G.arcs[k][j].adj){cout<<G.vexs[j];visited[j]=TRUE;EnQueue(Q,j)；

}}}}第五十二頁，共九十八頁，編輯于2023年，星期三廣度優(yōu)先搜索算法（以鄰接表作存儲結構）：voidBFSTraverse(ALGraphG){for(i=0;i<G.vexnum;++i)visited[i]=FALSE;InitQueue(Q);for(i=0;i<G.vexnum;++i)if(!visited[i]){visited[i]=TRUE;cout<<G.vertices[i].data;EnQueue(Q,i);while(!QueueEmpty(Q)){DeQueue(Q,k);p=G.vertices[k].firstarc;while(p){if(!visited[p->adjvex]){cout<<G.vertices[p->adjvex].data;visited[p->adjvex]=TRUE;EnQueue(Q,p->adjvex);}p=p->nextarc;}}}}第五十三頁，共九十八頁，編輯于2023年，星期三7.4圖的連通性問題

一、無向圖的連通分量和生成樹對連通圖，僅需從圖的任一頂點出發(fā)進行DFS或BFS，可訪問到圖中所有頂點；對非連通圖，則需從多個頂點出發(fā)進行搜索，每一次從一個新起點出發(fā)進行搜索得到的頂點序列恰為其各個連通分量中頂點集。第五十四頁，共九十八頁，編輯于2023年，星期三若設以孩子兄弟鏈表作生成森林的存儲結構，則下面算法生成非連通圖的深度優(yōu)先生成森林：voidDFSForest(GraphG,CSTree&T){T=NULL;for(i=0;i<G.vexnum;++i)visited[i]=FALSE;for(i=0;i<G.vexnum;++i)if(!visited[i]){p=newCSNode;p->data=GetVex(G,i);//分配根結點

p->firstchild=p->nextsibling=NULL;if(!T)T=p;//是第一棵生成樹的根

elseq->nextsibling=p;//是其它生成樹的根

q=p;//q指示當前生成樹的根

DFSTree(G,i,p);//建立以p為根的生成樹

}}第五十五頁，共九十八頁，編輯于2023年，星期三voidDFSTree(GraphG,intv,CSTree&T){visited[v]=TRUE;first=TRUE;for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w]){p=newCSNode;p->data=GetVex(G,w);p->firstchild=p->nextsibling=NULL;if(first)//w是v的第一個未被訪問的鄰接點

{T->lchild=p;first=FALSE;}//是根的左孩子

elseq->nextsibling=p;//是上一鄰接點的右兄弟

q=p;DFSTree(G,w,q);}}第五十六頁，共九十八頁，編輯于2023年，星期三二、(連通網的)最小生成樹

假設要在n個城市之間建立通訊聯(lián)絡網，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經費的前提下建立這個通訊網？問題：第五十七頁，共九十八頁，編輯于2023年，星期三構造網的一棵最小生成樹，即：在e條帶權的邊中選取n-1條邊（不構成回路），使“權值之和”為最小。算法二：（克魯斯卡爾算法）該問題等價于：算法一：（普里姆算法）第五十八頁，共九十八頁，編輯于2023年，星期三

取圖中任意一個頂點v作為生成樹的根，之后往生成樹上添加新的頂點w。在添加的頂點w和已經在生成樹上的頂點v之間必定存在一條邊，并且該邊的權值在所有連通頂點v和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點，直至生成樹上含有n-1個頂點為止。普里姆算法的基本思想:第五十九頁，共九十八頁，編輯于2023年，星期三abcdegf195141827168213127例如:aedcbgf148531621所得生成樹權值和=14+8+3+5+16+21=67第六十頁，共九十八頁，編輯于2023年，星期三在生成樹的構造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U

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

，則應在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。

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

VRTypelowcost;//邊的權值}closedge[MAX_VERTEX_NUM];第六十二頁，共九十八頁，編輯于2023年，星期三abcdegf195141827168213127aedcbaaa19141814例如:e12ee8168d3dd7213c55

19mm14m18195712mmm53mmmm73821m1412m8m16mmm21m2718mmm1627第六十三頁，共九十八頁，編輯于2023年，星期三voidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法從頂點u出發(fā)構造網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=1;i<G.vexnum;++i){}繼續(xù)向生成樹上添加頂點;第六十四頁，共九十八頁，編輯于2023年，星期三

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};

第六十五頁，共九十八頁，編輯于2023年，星期三具體做法:先構造一個只含n個頂點的子圖SG，然后從權值最小的邊開始，若它的添加不使SG中產生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止。考慮問題的出發(fā)點:為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄旱诹?，共九十八頁，編輯于2023年，星期三abcdegf195141827168213127aedcbgf148531621例如:7121819第六十七頁，共九十八頁，編輯于2023年，星期三算法描述:構造非連通圖ST=(V,{});k=i=0;//k計選中的邊數(shù)

while(k<n-1){++i;

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

若(u,v)加入ST后不使ST中產生回路，

則輸出邊(u,v);

且k++;}第六十八頁，共九十八頁，編輯于2023年，星期三普里姆算法克魯斯卡爾算法時間復雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應范圍比較兩種算法第六十九頁，共九十八頁，編輯于2023年，星期三7.5有向無環(huán)圖及其應用一、拓撲排序問題:

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

檢查有向圖中是否存在回路的方法之一，是對有向圖進行拓撲排序。第七十頁，共九十八頁，編輯于2023年，星期三何謂“拓撲排序”？對有向圖進行如下操作:

按照有向圖給出的次序關系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關系的頂點，則可以人為加上任意的次序關系。第七十一頁，共九十八頁，編輯于2023年，星期三例如：對于下列有向圖BDAC可求得拓撲有序序列：

ABCD

或

ACBD由此所得頂點的線性序列稱之為拓撲有序序列第七十二頁，共九十八頁，編輯于2023年，星期三BDAC反之，對于下列有向圖不能求得它的拓撲有序序列。因為圖中存在一個回路

{B,C,D}第七十三頁，共九十八頁，編輯于2023年，星期三如何進行拓撲排序？一、從有向圖中選取一個沒有前驅的頂點，并輸出之;

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

有以它為尾的弧;第七十四頁，共九十八頁，編輯于2023年，星期三abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

沒有前驅的頂點入度為零的頂點刪除頂點及以它為尾的弧弧頭頂點的入度減1第七十五頁，共九十八頁，編輯于2023年，星期三取入度為零的頂點v;m=0;while(v!=0){

printf(v);++m;w=FirstAdj(v);

while(w!=

0){inDegree[w]--;w=nextAdj(v,w);

}

取下一個入度為零的頂點v;}ifm<nprintf(“圖中有回路”);算法描述第七十六頁，共九十八頁，編輯于2023年，星期三為避免每次都要搜索入度為零的頂點，在算法中設置一個“?！?，以保存“入度為零”的頂點。CountInDegree(G,indegree);//對各頂點求入度InitStack(S);for(i=0;i<G.vexnum;++i)

if(!indegree[i])Push(S,i);//入度為零的頂點入棧第七十七頁，共九十八頁，編輯于2023年，星期三count=0;//對輸出頂點計數(shù)while(!EmptyStack(S)){

Pop(S,v);++count;printf(v);

for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){

--indegree(w);//弧頭頂點的入度減一

if(!indegree[w])Push(S,w);

//新產生的入度為零的頂點入棧}}if(count<G.vexnum)printf(“圖中有回路”)第七十八頁，共九十八頁，編輯于2023年，星期三二、關鍵路徑問題:

假設以有向網表示一個施工流圖，弧上的權值表示完成該項子工程所需時間。問：哪些子工程項是“關鍵工程”？即：哪些子工程項將影響整個工程的完成期限的。第七十九頁，共九十八頁，編輯于2023年，星期三整個工程完成的時間為：從有向圖的源點到匯點的最長路徑。abcdefghk64521187244例如:“關鍵活動”指的是：該弧上的權值增加

將使有向圖上的最長路徑的長度增加。源點匯點6174第八十頁，共九十八頁，編輯于2023年，星期三

如何求關鍵活動？

什么是“關鍵活動”？該活動的最早開始時間

=該活動的最遲開始時間ijdut第八十一頁，共九十八頁，編輯于2023年，星期三“事件(頂點)”的最早發(fā)生時間ve(j)ve(j)=從源點到頂點j的最長路徑長度;“事件(頂點)”的最遲發(fā)生時間vl(k)vl(k)=從頂點k到匯點的最短路徑長度;第八十二頁，共九十八頁，編輯于2023年，星期三

假設第i條弧為<j,k>

則對第i項活動言“活動(弧)”的最早開始時間ee(i)ee(i)=ve(j);“活動(弧)”的最遲開始時間el(i)el(i)=vl(k)–dut(<j,k>);第八十三頁，共九十八頁，編輯于2023年，星期三

事件發(fā)生時間的計算公式:ve(源點)=0;ve(k)=Max{ve(j)+dut(<j,k>)}vl(匯點)=ve(匯點);vl(j)=Min{vl(k)–dut(<j,k>)}第八十四頁，共九十八頁，編輯于2023年，星期三abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓撲有序序列:a-d-f-c-b-e-h-g-k第八十五頁，共九十八頁，編輯于2023年，星期三0645771514181814161078660000645777151414160236688710第八十六頁，共九十八頁，編輯于2023年，星期三

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

而求vl的順序應該是按拓撲逆序的次序;因為拓撲逆序序列即為拓撲有序序列的逆序列，因此應該在拓撲排序的過程中，另設一個“