第7章-圖n幻燈片課件

第七章圖7.1抽象數(shù)據(jù)類型圖的定義7.2圖的存儲表示7.3圖的遍歷7.4最小生成樹7.5重（雙）連通圖和關(guān)節(jié)點(diǎn)7.6拓?fù)渑判?.7關(guān)鍵路徑學(xué)習(xí)目標(biāo)

掌握圖的概念、存儲結(jié)構(gòu)、操作實(shí)現(xiàn)及算法復(fù)雜度；掌握圖的深度、廣度優(yōu)先搜索遍歷算法；掌握圖的生成樹概念，普里姆算法、克魯斯卡算法。掌握圖的拓?fù)渑判蚍椒?/p>

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

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

謂詞P(v,w)定義了弧<v,w>的意義或信息。圖的結(jié)構(gòu)定義:若<v,w>VR必有<w,v>VR,則稱(v,w)為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊。

BCADFE由頂點(diǎn)集和邊集構(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>}名詞和術(shù)語網(wǎng)、子圖

完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹、生成森林ABECFAEFBBC設(shè)圖G=(V,{VR})和圖G=(V,{VR}),且VV,VRVR,則稱G為G的子圖。1597211132

弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。假設(shè)圖中有

n

個頂點(diǎn)，e

條邊，則

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

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

有向完全圖；若邊或弧的個數(shù)e<nlogn，則稱作稀疏圖，否則稱作稠密圖。

假若頂點(diǎn)v和頂點(diǎn)w之間存在一條邊，則稱頂點(diǎn)v和w互為鄰接點(diǎn)，ACDFE例如:ID(B)=3ID(A)=2邊(v,w)

和頂點(diǎn)v和w相關(guān)聯(lián)。

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

若任意兩個頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。ABECFABECF對有向圖，否則，其各個強(qiáng)連通子圖稱作它的強(qiáng)連通分量。

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

//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在//圖中“位置”

；否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對v賦值value。對鄰接點(diǎn)的操作FirstAdjVex(G,v);

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

//返回v的（相對于w的）“下一個鄰接//點(diǎn)”。若w是v的最后一個鄰接點(diǎn)，則//返回“空”。插入或刪除頂點(diǎn)InsertVex(&G,v);

//在圖G中增添新頂點(diǎn)v。DeleteVex(&G,v);//刪除G中頂點(diǎn)v及其相關(guān)的弧。插入和刪除弧InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是無向的，//則還增添對稱弧<w,v>。DeleteArc(&G,v,w);

//在G中刪除弧<v,w>，若G是無向的，//則還刪除對稱弧<w,v>。遍歷DFSTraverse(G,v,Visit());//從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對每//個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());

//從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對每//個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。7.2圖的存儲表示一、圖的數(shù)組(鄰接矩陣)存儲表示二、圖的鄰接表存儲表示Aij={0(i,j)VR1(i,j)VR一、圖的數(shù)組(鄰接矩陣)存儲表示BACDFE定義:矩陣的元素為有向圖的鄰接矩陣為非對稱矩陣ABECF網(wǎng)的鄰接矩陣可定義為：v2v1v3v4v5v65489755613v1

v2

v3

v4

v5v6v1

v2v3v4v5v6typedefstructArcCell{//弧的定義VRTypeadj;//VRType是頂點(diǎn)關(guān)系類型。對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{//圖的定義VertexType//頂點(diǎn)信息vexs[MAX_VERTEX_NUM];AdjMatrixarcs;//弧的信息

intvexnum,arcnum;//頂點(diǎn)數(shù)，弧數(shù)GraphKindkind;//圖的種類標(biāo)志

}MGraph;0A141B0452C353D254E015F123BACDFE二、圖的鄰接表存儲表示142301201234ABCDE有向圖的鄰接表

ABECF可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。ABECD有向圖的逆鄰接表ABCDE303420

01234在有向圖的鄰接表中，對每個頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。typedefstructArcNode{

intadjvex;//該弧所指向的頂點(diǎn)的位置

structArcNode*nextarc;//指向下一條弧的指針I(yè)nfoType*info;//該弧相關(guān)信息的指針}ArcNode;adjvexnextarcinfo弧的結(jié)點(diǎn)結(jié)構(gòu)typedefstructVNode{

VertexTypedata;//頂點(diǎn)信息ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧

}VNode,AdjList[MAX_VERTEX_NUM];datafirstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)typedefstruct{

AdjListvertices;

intvexnum,arcnum;

intkind;//圖的種類標(biāo)志}ALGraph;圖的結(jié)構(gòu)定義鄰接表與鄰接矩陣有什么異同之處？聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個數(shù)等于一行中非零元素的個數(shù)。2.區(qū)別：①

對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點(diǎn)編號一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號無關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（e<<n2)7.3圖的遍歷

從圖中某個頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個頂點(diǎn)僅被訪問一次的過程。深度優(yōu)先搜索廣度優(yōu)先搜索遍歷應(yīng)用舉例

從圖中某個頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)，然后依次從V0的各個未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。一、深度優(yōu)先搜索遍歷圖連通圖的深度優(yōu)先搜索遍歷例：

V1V1V2V4V5V3V7V6V8頂點(diǎn)訪問次序：V2V4V8V5V3V6V7

V1V2V5V8V4V3V6V7

V1V2V4V8V5V3V7V6

V1V2V5V8V4V3V7V6

V1V3V6V7V2V4V8V5

連通圖的深度優(yōu)先遍歷類似于樹的先根遍歷Vw1SG1SG2SG3W1、W2和W3

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

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

若該鄰接點(diǎn)W未被訪問，

則從它出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。w2w3w2從上頁的圖解可見:1.從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；解決的辦法是：為每個頂點(diǎn)設(shè)立一個“訪問標(biāo)志visited[w]”。2.如何判別V的鄰接點(diǎn)是否被訪問？voidDFS(GraphG,intv){//從頂點(diǎn)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的尚未訪問的鄰接頂點(diǎn)w//遞歸調(diào)用DFS}//DFS首先將圖中每個頂點(diǎn)的訪問標(biāo)志設(shè)為FALSE,之后搜索圖中每個頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先搜索遍歷voidDFSTraverse(GraphG,

Status(*Visit)(intv)){

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

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

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

if(!visited[v])DFS(G,v);//對尚未訪問的頂點(diǎn)調(diào)用DFS}abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg訪問標(biāo)志:訪問次序:例如:012345678abcdefghk從圖中的某個頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。二、廣度優(yōu)先搜索遍歷圖Vw1w8w3w7w6w2w5w4對連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑。其中，V->w1,V->w2,V->w8

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

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

的路徑長度為3。w1Vw2w7w6w3w8w5w4

1340V1V2V3V4V5V6實(shí)現(xiàn)：V1V2V4V5V3V7V6V801234567V1V2V3V4V5V6V7V82^10101223354^6^7^7^6^5^4^00000000012345672V75V8FRRFRRFRRF67FFFFFRRR111111112^10101223354^6^7^7^6^5^4^2^10101223354^6^7^7^6^5^4^2^10101223354^6^7^7^6^5^4^

voidBFSTraverse(GraphG,

Status(*Visit)(intv)){

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

InitQueue(Q);

//置空的輔助隊(duì)列Q

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

if(

!visited[v]){

//v尚未訪問

}

}//BFSTraverse……visited[v]=TRUE;Visit(v);//訪問vEnQueue(Q,v);

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

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

if(!visited[w])

{

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

//訪問的頂點(diǎn)w入隊(duì)列}//if}//while三、遍歷應(yīng)用舉例1.求一條從頂點(diǎn)i到頂點(diǎn)s的簡單路徑2.

求兩個頂點(diǎn)之間的一條路徑長度最短的路徑1.

求一條從頂點(diǎn)i到頂點(diǎn)s的簡單路徑abchdekfg求從頂點(diǎn)b到頂點(diǎn)k的一條簡單路徑。從頂點(diǎn)b出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。例如:假設(shè)找到的第一個鄰接點(diǎn)是a，則得到的結(jié)點(diǎn)訪問序列為:b

adhce

kfg。假設(shè)找到的第一個鄰接點(diǎn)是c，則得到的結(jié)點(diǎn)訪問序列為:

b

chdae

kfg，1.從頂點(diǎn)i到頂點(diǎn)s,若存在路徑，則從頂點(diǎn)i出發(fā)進(jìn)行深度優(yōu)先搜索，必能搜索到頂點(diǎn)s。2.

遍歷過程中搜索到的頂點(diǎn)不一定是路徑上的頂點(diǎn)。結(jié)論:3.

由它出發(fā)進(jìn)行的深度優(yōu)先遍歷已經(jīng)完成的頂點(diǎn)不是路徑上的頂點(diǎn)。voidDFSearch(intv,ints,char*PATH){//從第v個頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G，//求得一條從v到s的簡單路徑，并記錄在PATH中visited[v]=TRUE;//訪問第v個頂點(diǎn)

Append(PATH,getVertex(v));

//第v個頂點(diǎn)加入路徑

for(w=FirstAdjVex(v);w!=0&&!found;

w=NextAdjVex(v))

if(w==s){found=TRUE;Append(PATH,w);}

else

if(!visited[w])DFSearch(w,s,PATH);if(!found)Delete(PATH);

//從路徑上刪除頂點(diǎn)v

}2.

求兩個頂點(diǎn)之間的一條路徑長度最短的路徑

若兩個頂點(diǎn)之間存在多條路徑，則其中必有一條路徑長度最短的路徑。如何求得這條路徑?abchdekfg因此，求路徑長度最短的路徑可以基于廣度優(yōu)先搜索遍歷進(jìn)行，但需要修改鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)及其入隊(duì)列和出隊(duì)列的算法。深度優(yōu)先搜索訪問頂點(diǎn)的次序取決于圖的存儲結(jié)構(gòu)，而廣度優(yōu)先搜索訪問頂點(diǎn)的次序是按“路徑長度”漸增的次序。例如:求下圖中頂點(diǎn)3至頂點(diǎn)5的一條最短路徑。鏈隊(duì)列的狀態(tài)如下所示:

312475

Q.front

Q.rear321475689采用雙向鏈隊(duì)列如下所示:

312475

Q.front

Q.rear3214756891)將鏈隊(duì)列的結(jié)點(diǎn)改為“雙鏈”結(jié)點(diǎn)。即結(jié)點(diǎn)中包含next和priou兩個指針；2)修改入隊(duì)列的操作。插入新的隊(duì)尾結(jié)點(diǎn)時(shí)，令其priou域的指針指向剛剛出隊(duì)列的結(jié)點(diǎn)，即當(dāng)前的隊(duì)頭指針?biāo)附Y(jié)點(diǎn)；3)修改出隊(duì)列的操作。出隊(duì)列時(shí)，僅移動隊(duì)頭指針，而不將隊(duì)頭結(jié)點(diǎn)從鏈表中刪除。typedef

DuLinkListQueuePtr;

voidInitQueue(LinkQueue&Q){

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

Q.front->next=Q.rear->next=NULL}voidEnQueue(LinkQueue&Q,QelemTypee){p=(QueuePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;

p->priou=Q.front

Q.rear->next=p;Q.rear=p;}voidDeQueue(LinkQueue&Q,QelemType&e){

Q.front=Q.front->next;e=Q.front->data}7.4(連通網(wǎng)的)最小生成樹

假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個通訊網(wǎng)？問題：V1V6V5V4V3V26513566425V1V6V5V4V3V265134V1V6V5V4V3V2651321917最小生成樹：給定一個無向網(wǎng)絡(luò)，在該網(wǎng)的所有生成樹中，使得各邊權(quán)數(shù)之和最小的那棵生成樹稱為該網(wǎng)的最小生成樹，也叫最小代價(jià)生成樹。構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。算法二：（克魯斯卡爾算法）該問題等價(jià)于：算法一：（普里姆算法）

取圖中任意一個頂點(diǎn)v作為生成樹的根，之后往生成樹上添加新的頂點(diǎn)w。在添加的頂點(diǎn)w和已經(jīng)在生成樹上的頂點(diǎn)v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有n-1個頂點(diǎn)為止。普里姆算法的基本思想:在生成樹的構(gòu)造過程中，圖中n個頂點(diǎn)分屬兩個集合：已落在生成樹上的頂點(diǎn)集U

和尚未落在生成樹上的頂點(diǎn)集V-U，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。

一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件:abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67設(shè)置一個輔助數(shù)組，對當(dāng)前V－U集中的每個頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：struct{VertexTypeadjvex;//U集中的頂點(diǎn)序號VRTypelowcost;//邊的權(quán)值}closedge[MAX_VERTEX_NUM];abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c55abcdefg設(shè)置一個輔助數(shù)組，對當(dāng)前V－U集中的每個頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：struct{VertexTypeadjvex;//U集中的頂點(diǎn)序號VRTypelowcost;//邊的權(quán)值}closedge[MAX_VERTEX_NUM];voidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法從頂點(diǎn)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ù)向生成樹上添加頂點(diǎn);

k=minimum(closedge);

//求出加入生成樹的下一個頂點(diǎn)(k)

printf(closedge[k].adjvex,G.vexs[k]);//輸出生成樹上一條邊closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集for(j=0;j<G.vexnum;++j)//修改其它頂點(diǎn)的最小邊

if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};

具體做法:先構(gòu)造一個只含n個頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止?？紤]問題的出發(fā)點(diǎn):為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。克魯斯卡爾算法的基本思想：abcdegf195141827168213ae12dcbgf7148531621例如:7121819算法描述:構(gòu)造非連通圖ST=(V,{});k=i=0;//k計(jì)選中的邊數(shù)while(k<n-1){++i;檢查邊集E中第i條權(quán)值最小的邊(u,v);

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

則輸出邊(u,v);

且k++;}Flash演示普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法7.5重（雙）連通圖和關(guān)節(jié)點(diǎn)

若從一個連通圖中刪去任何一個頂點(diǎn)及其相關(guān)聯(lián)的邊，它仍為一個連通圖的話，則該連通圖被稱為重（雙）連通圖。問題：

若連通圖中的某個頂點(diǎn)和其相關(guān)聯(lián)的邊被刪去之后，該連通圖被分割成兩個或兩個以上的連通分量，則稱此頂點(diǎn)為關(guān)節(jié)點(diǎn)。沒有關(guān)節(jié)點(diǎn)的連通圖為雙連通圖。如何判別給定的連通圖是否是雙連通圖？ahgcbfdeabcdefgh1234567833111111例如:下列連通圖中，頂點(diǎn)

a

和頂點(diǎn)c

是關(guān)節(jié)點(diǎn)深度優(yōu)先生成樹關(guān)節(jié)點(diǎn)有何特征？

假設(shè)從某個頂點(diǎn)V0出發(fā)對連通圖進(jìn)行深度優(yōu)先搜索遍歷，則可得到一棵深度優(yōu)先生成樹，樹上包含圖的所有頂點(diǎn)。需借助圖的深度優(yōu)先生成樹來分析。

若生成樹的根結(jié)點(diǎn)，有兩個或兩個以上的分支，則此頂點(diǎn)(生成樹的根)必為關(guān)節(jié)點(diǎn)；

對生成樹上的任意一個“頂點(diǎn)”，若其某棵子樹的根或子樹中的其它“頂點(diǎn)”沒有和其祖先相通的回邊，則該“頂點(diǎn)”必為關(guān)節(jié)點(diǎn)。對上述兩個判定準(zhǔn)則在算法中如何實(shí)現(xiàn)？1)設(shè)V0為深度優(yōu)先遍歷的出發(fā)點(diǎn)

p=G.vertices[0].firstarc;v=p->adjvex;

DFSArticul(G,v);

//從第v頂點(diǎn)出發(fā)深度優(yōu)先搜索

if

(count<G.vexnum)

{

//生成樹的根有至少兩棵子樹

printf(0,G.vertices[0].data);

//根是關(guān)節(jié)點(diǎn)2)定義函數(shù):low(v)=Min{visited[v],low[w],visited[k]}

其中:頂點(diǎn)w

是生成樹上頂點(diǎn)v

的孩子；頂點(diǎn)k

是生成樹上和頂點(diǎn)v由回邊相聯(lián)接的祖先；visited記錄深度優(yōu)先遍歷時(shí)的訪問次序

若對頂點(diǎn)v，在生成樹上存在一個子樹根w，

且

low[w]≥visited[v]

則頂點(diǎn)v為關(guān)節(jié)點(diǎn)。對深度優(yōu)先遍歷算法作如下修改：1．visited[v]的值改為遍歷過程中頂點(diǎn)的訪問次序count值；

2．遍歷過程中求得

low[v]=Min{visited[v],low[w],visited[k]}3．從子樹遍歷返回時(shí)，判別low[w]≥visited[v]?for(p=G.vertices[v0].firstarc;p;p=p->nextarc){

}voidDFSArticul(ALGraphG,intv0){//從第v0個頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G,

//查找并輸出關(guān)節(jié)點(diǎn)}//DFSArticulmin=visited[v0]=++count;//v0是第count個訪問的頂點(diǎn),并設(shè)low[v0]的初值為min

//檢查v0的每個鄰接點(diǎn)low[v0]=min;

w=p->adjvex;//w為v0的鄰接頂點(diǎn)

if(visited[w]==0){//w未曾被訪問DFSArticul(G,w);//返回前求得low[w]

}

else//w是回邊上的頂點(diǎn)if(low[w]<min)min=low[w];

if(low[w]>=visited[v0])

printf(v0,G.vertices[v0].data);

//輸出關(guān)節(jié)點(diǎn)if(visited[w]<min)min=visited[w];7.6拓?fù)渑判?/p>

問題:

假設(shè)以有向圖表示一個工程的施工圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。除最簡單的情況之外，幾乎所有的工程都可分為若干個稱作“活動”的子工程，并且這些子工程之間通常受著一定條件的約束，例如：其中某些子工程必須在另一些子工程完成之后才能開始。

在工程計(jì)劃和管理方面的應(yīng)用

AOV網(wǎng)：

用一個有向圖表示一個工程的各子工程及其相互制約的關(guān)系，其中以頂點(diǎn)表示活動，弧表示活動之間的優(yōu)先制約關(guān)系，稱這種有向圖為頂點(diǎn)表示活動的網(wǎng)，簡稱AOV(ActivityOnVertexnetwork)網(wǎng)。AOV網(wǎng)鄰接表表示012345C0C1C2C3C4C5C0C1C2C30C4C50countdataadj

1301031

datalink3051500150對整個工程和系統(tǒng)，人們關(guān)心的是兩方面的問題：一是工程能否順利進(jìn)行；二是完成整個工程所必須的最短時(shí)間。對應(yīng)到有向圖即為進(jìn)行拓?fù)渑判蚝颓箨P(guān)鍵路徑。

檢查有向圖中是否存在回路的方法之一，是對有向圖進(jìn)行拓?fù)渑判?。何謂“拓?fù)渑判颉保繉τ邢驁D進(jìn)行如下操作：

按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。例如：對于下列有向圖BDAC可求得拓?fù)溆行蛐蛄校?/p>

ABCD

或

ACBD由此所得頂點(diǎn)的線性序列稱之為拓?fù)溆行蛐蛄蠦DAC反之，對于下列有向圖不能求得它的拓?fù)溆行蛐蛄小Ｒ驗(yàn)閳D中存在一個回路{B,C,D}如何進(jìn)行拓?fù)渑判?？一、從有向圖中選取一個沒有前驅(qū)的頂點(diǎn)，并輸出之；

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

有以它為尾的弧；abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

沒有前驅(qū)的頂點(diǎn)

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

弧頭頂點(diǎn)的入度減1取入度為零的頂點(diǎn)v;while(v<>0){

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

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

}取下一個入度為零的頂點(diǎn)v;}ifm<nprintf(“圖中有回路”);算法描述為避免每次都要搜索入度為零的頂點(diǎn)，在算法中設(shè)置一個“?！?，以保存“入度為零”的頂點(diǎn)。CountInDegree(G,indegree)