數(shù)據(jù)結(jié)構(gòu)中的圖課件

第7章圖（Graph）主講：李耀國數(shù)據(jù)結(jié)構(gòu)（DataStructure）

第七章圖

圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個元素最多只有一個直接前驅(qū)和一個直接后繼。在樹型結(jié)構(gòu)中，數(shù)據(jù)元素之間存在明顯的層次關(guān)系，并且每層的元素可能和下一層的多個元素相鄰，但只能和上一層的一個元素相鄰。而在圖形結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是任意的，圖中的任意兩個元素之間都可能相鄰。圖是計算機應(yīng)用過程中對實際問題進(jìn)行數(shù)學(xué)抽象和描述的強有力的工具，數(shù)據(jù)結(jié)構(gòu)中對圖的討論側(cè)重于在計算機中如何表示圖以及如何實現(xiàn)圖的操作和應(yīng)用等。第七章圖圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。第七章圖和廣義表7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應(yīng)用7.5.1拓?fù)渑判?.5.2關(guān)鍵路徑7.6最短路徑第七章圖和廣義表7.1圖的定義和術(shù)語7.1圖的定義和術(shù)語圖由一個頂點的有窮非空集合V(G)和一個弧的集合E(G)組成，通常記做G=(V,E)。圖中的頂點即為數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，弧的集合E實際上是定義在頂點集合上的一個關(guān)系。用有序?qū)?lt;v,w>表示從v到w的一條弧?；【哂蟹较蛐?，以帶箭頭的線段表示，通常稱v為弧尾或始點，稱w為弧頭或終點，此時的圖稱為有向圖。若圖中從v到w有一條弧，同時從w到v也有一條弧，則以無序?qū)?v,w)代替這兩個有序?qū)?lt;v,w>和<w,v>,表示v和w之間的一條邊。此時的圖在頂點之間不再強調(diào)方向性的特征，稱為無向圖。7.1圖的定義和術(shù)語圖由一個頂點的有窮非空集合V(G)和一7.1圖的定義和術(shù)語圖G1是一個有向圖，G1=(V1,{A1})。其中:V1={A,C,B,F,D,E,G}A1={<A,B>,<B,C>,<B,F>,<B,E>,<C,E>,<E,D>,<D,C>,<E,B>,<F,G>}ACBFDGE有向圖G17.1圖的定義和術(shù)語圖G1是一個有向圖，G1=(V1,{A7.1圖的定義和術(shù)語圖G2是一個無向圖，G2=(V2,{E2})。其中：

V2={A,B,C,D,E,F}E2={(A,B),(A,C),(B,C),(B,E),(B,F),(C,F),(C,D),(E,F),(C,E)}ABCDEF無向圖G27.1圖的定義和術(shù)語圖G2是一個無向圖，G2=(V2,{E7.1圖的定義和術(shù)語

在實際應(yīng)用中，圖的弧或邊往往與具有一定意義的數(shù)相關(guān)，稱這些數(shù)為權(quán)(weight)。分別稱帶權(quán)的有向圖和無向圖為有向網(wǎng)和無向網(wǎng)。123456712345671918212756103311706475806018069584331324430無向網(wǎng)有向網(wǎng)7.1圖的定義和術(shù)語在實際應(yīng)用中，圖的弧或邊往往與具有7.1圖的定義和術(shù)語

稀疏圖和稠密圖假設(shè)用n表示圖中頂點數(shù)目，用e表示邊或弧的數(shù)目。若不考慮頂點到其自身的弧或邊，則對于無向圖，邊數(shù)e的取值范圍是0到n(n-1)/2。稱具有n(n-1)/2條邊的無向圖為完全圖。對于有向圖，弧的數(shù)目e的取值范圍是0到n(n-1)。稱具有n(n-1)條弧的有向圖為有向完全圖。若e<nlogn，則稱為稀疏圖，反之稱為稠密圖。

子圖假設(shè)有兩個圖G=(V,{E})和G’=(V’,{E’})，若V’V且E’E，則稱G’為G的子圖。7.1圖的定義和術(shù)語稀疏圖和稠密圖假設(shè)用n表示圖中頂點7.1圖的定義和術(shù)語度、入度和出度若u->v是圖中的一條弧，則稱u鄰接到v，或v鄰接自u。圖中所鄰接到某頂點v的弧的數(shù)目，稱為該頂點的入度，記作:ID(v)；反之，從某頂點u出發(fā)的弧的數(shù)目，稱為該頂點的出度，記作:OD(u)。頂點v的入度和出度之和稱為該頂點的總度，簡稱為度，記作:TD(v)。例如圖G1中頂點B的入度ID(B)=2，出度OD(B)=3，度TD(B)=5。無向圖中頂點的度定義為與該頂點相連的邊的數(shù)目。一般情況下，如果頂點vi的度記作TD(vi)，則一個含有n個頂點，e條邊或弧的圖，滿足如下關(guān)系：ACBFDGE7.1圖的定義和術(shù)語度、入度和出度若u->v是圖中的一條7.1圖的定義和術(shù)語路徑和回路若有向圖G中k+1個頂點之間都有弧存在，則這個頂點的序列{v0,v1,…vk}為從頂點v0到頂點vk的一條有向路徑，路徑中弧的數(shù)目定義為路徑長度。若序列中的頂點都不相同，則為簡單路徑。對無向圖，相鄰頂點之間存在邊的k+1個頂點序列構(gòu)成一條長度為k的無向路徑。如若v0和vk是同一個頂點，則是一條由某個頂點出發(fā)又回到自身的路徑，稱這種路徑為回路或環(huán)。7.1圖的定義和術(shù)語路徑和回路若有向圖G中k+1個頂點7.1圖的定義和術(shù)語連通圖和連通分量若無向圖中任意兩個頂點之間都存在一條無向路徑，則稱該無向圖為連通圖。對有向圖而言，若圖中任意兩個頂點之間都存在一條有向路徑，則稱該有向圖為強連通圖。非連通圖中的各個極大連通子圖稱為該圖的連通分量。ABCDEFACBFDGE非強連通圖和強連通分量非連通圖和連通分量7.1圖的定義和術(shù)語連通圖和連通分量若無向圖中任意兩個7.1圖的定義和術(shù)語圖的抽象數(shù)據(jù)類型ADTGraph{

數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關(guān)系R:R={VR}VR={<v,w>|v,w∈P(v,w),<v,w>表示從到的弧,

謂詞P(v,w)定義了弧<v,w>的意義或信息}

基本操作：CreateGraph(&G,V,VR)初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。DestoryGraph(&G)初始條件：圖G存在。操作結(jié)果：銷毀圖G。LocateVex(G,u)初始條件：圖G存在，u和G中頂點有相同特征。操作結(jié)果：若G中存在頂點u，則返回該頂點在圖中的位置；否則返回其他信息。more7.1圖的定義和術(shù)語圖的抽象數(shù)據(jù)類型more7.1圖的定義和術(shù)語GetVex(G,v)初始條件：圖G存在，v是G中的某個頂點。操作結(jié)果：返回v的值。PutVex(&G,v,value)初始條件：圖G存在，v是G中的某個頂點。操作結(jié)果：對v賦值value。FirstAdjVex(G,v)初始條件：圖G存在，v是G中的某個頂點。操作結(jié)果：返回v的第一個鄰接點，若該頂點在G中無鄰接點，則返回空。NextAdjVex(G,v,w)初始條件：圖G存在，v是G中的某個頂點，w是v的鄰接頂點。操作結(jié)果：返回v的(相對于w的)下一個鄰接點。若w是v的最后一個鄰接點，則返回空。more7.1圖的定義和術(shù)語GetVex(G,v)more7.1圖的定義和術(shù)語InsertVex(&G,v)

初始條件：圖G存在，v和圖中頂點有相同特征。操作結(jié)果：在圖G中增添新頂點v。

DeleteVex(&G,v)

初始條件：圖G存在，v是G中的某個頂點。操作結(jié)果：刪除G中頂點v及其相關(guān)的弧。

InsertArc(&G,v,w)

初始條件：圖G存在，v和w是G中的兩個頂點。操作結(jié)果：在圖G中增添弧<v,w>，若G是無向的，則還增添對稱弧<w,v>。

DeleteArc(&G,v,w)

初始條件：圖G存在，v和w是G中的兩個頂點。操作結(jié)果：在圖G中刪除弧<v,w>，若G是無向的，則還刪除對稱弧<w,v>。more7.1圖的定義和術(shù)語InsertVex(&G,v)mo7.1圖的定義和術(shù)語DFSTraverse(G,v,visit())

初始條件：圖G存在，v是G中的某個頂點，visit是針對頂點的應(yīng)用函數(shù)。操作結(jié)果：從頂點v起深度優(yōu)先遍歷圖G，并對每個頂點調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。

BFSTraverse(G,v,visit())

初始條件：圖G存在，v是G中的某個頂點，visit是針對頂點的應(yīng)用函數(shù)。操作結(jié)果：從頂點v起廣度優(yōu)先遍歷圖G，并對每個頂點調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。}ADTGraph7.1圖的定義和術(shù)語DFSTraverse(G,v,v7.2圖的存儲結(jié)構(gòu)圖是一種典型的復(fù)雜結(jié)構(gòu)，圖中頂點可能同任意一個其他頂點之間存在關(guān)系。因此，圖沒有順序映象的存儲結(jié)構(gòu)。圖有兩種常用的存儲結(jié)構(gòu)。7.2.1圖的數(shù)組(鄰接矩陣)存儲表示鄰接矩陣是用于描述圖中頂點之間的關(guān)系(及弧或邊的權(quán))的矩陣，假設(shè)圖中頂點數(shù)為n，則鄰接矩陣A=(ai,j)m*n定義為：A[i][j]=1若Vi和Vj之間有弧或邊存在0Vi和Vj之間沒有弧或邊存在7.2圖的存儲結(jié)構(gòu)圖是一種典型的復(fù)雜結(jié)構(gòu)，圖中頂點可能同任7.2.1圖的數(shù)組(鄰接矩陣)存儲表示ACBFDGEABCDEF有向圖G1無向圖G2G1的鄰接矩陣G2的鄰接矩陣7.2.1圖的數(shù)組(鄰接矩陣)存儲表示ACBFDGEABC7.2.1圖的數(shù)組(鄰接矩陣)存儲表示一般情況下，圖中沒有鄰接到自身的弧，因此矩陣中主對角線全為零。由于無向圖中一條邊視為一對弧，則無向圖的鄰接矩陣必然是對稱矩陣。網(wǎng)的鄰接矩陣定義中，當(dāng)vi到vj有弧相鄰接時，ai,j的值為該弧上的權(quán)值，否則為∞。12345677064758060180695843313244307.2.1圖的數(shù)組(鄰接矩陣)存儲表示一般情況下，圖中沒有7.2.1圖的數(shù)組(鄰接矩陣)存儲表示有向圖的鄰接矩陣大多為稀疏矩陣，可以采用壓縮存儲表示。用二維數(shù)組表示更為方便，它和頂點信息等其他圖的信息一起構(gòu)成圖的一種存儲表示constINFINITY_INT_MAX=MAX;//最大值∞設(shè)為MAXconstMAX_VERTEX_NUM=20;//最大頂點個數(shù)typedef

enum{DG,DN,AG,AN}GraphKind;//圖類型(有向圖、有向網(wǎng)、無向圖、無向網(wǎng))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];typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM];//描述頂點的數(shù)組

AdjMatrixarcs; //鄰接矩陣

intvexnum,arcnum; //圖的當(dāng)前頂點數(shù)和弧(邊)數(shù)

GraphKindkind; //圖的種類標(biāo)志}MGraph;vexs[0][0].adjvexs[0][0].info……vexs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]arcsvexnumarcnumkind7.2.1圖的數(shù)組(鄰接矩陣)存儲表示有向圖的鄰接矩陣大多7.2.2圖的鄰接表存儲表示鄰接表是圖的一種鏈?zhǔn)酱鎯Ρ硎痉椒ǎ愃朴跇涞暮⒆渔湵怼Ｔ谟邢驁D的鄰接表中，從同一個頂點出發(fā)的弧鏈接在同一鏈表中，鄰接表中結(jié)點的個數(shù)恰好為圖中弧的個數(shù)。在無向圖的鄰接表中，同一條邊有兩個結(jié)點，分別出現(xiàn)在和它相關(guān)的兩個頂點的鏈表中，因此無向圖的鄰接表中結(jié)點個數(shù)是邊的兩倍。7.2.2圖的鄰接表存儲表示鄰接表是圖的一種鏈?zhǔn)酱鎯Ρ硎痉椒?.2.2圖的鄰接表存儲表示ACBFDGE有向圖G1MAX_VERTEX_NUMABCEDFG^……--01234561^3^6^12^4^245^7.2.2圖的鄰接表存儲表示ACBFDGE有向圖G1MAX_7.2.2圖的鄰接表存儲表示MAX_VERTEX_NUMABCEDF……--012345ABCDEF無向圖G22^1024015^345^2^125^124^7.2.2圖的鄰接表存儲表示MAX_VERTEX_NUMAB7.2.2圖的鄰接表存儲表示

鄰接表定義如下：constMAX_VERTEX_NUM=20;typedefstructArcNode{ intadjvex; //該弧所指向的頂點的位置

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

InfoType*info; //指向該弧相關(guān)信息的指針 }ArcNode; typedefstructVNode{ VertexTypedata; //頂點信息

ArcNode*firstarc; //指向第一條依附該頂點的弧}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{ AdjListvertices; intvexnum,arcnum; //圖的當(dāng)前頂點數(shù)和弧數(shù)

intkind; //圖的種類標(biāo)志}ALGraph;7.2.2圖的鄰接表存儲表示鄰接表定義如下：算法7.1voidCreateUDG(ALGraph&G){//采用鄰接表存儲表示，構(gòu)造無向圖G(G.kind=UDG)cin>>G.vexnum>>G.arcnum>>Incinfo;for(i=0;i<G.vexnum;++i){ //構(gòu)造表頭向量

cin>>G.vertices[i].data; //輸入頂點值

G.vertices[i].firstarc=NULL; //初始化鏈表頭指針為空

}//forfor(k=0;k<G.arcnum;++k){ //輸入各邊并構(gòu)造鄰接表

cin>>v1>>v2; //輸入一條弧的始點和終點

i=LocateVex(G,v1);j=LocateVex(G,v2);

//確定v1和v2在G中的位置，即頂點在G.Vertices中的序號

pi=newArcNode;pi->adjvex=j;//對弧結(jié)點賦鄰接點“位置”信息

pi->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=pi;

//插入鏈表G.vertices[i]pj=newArcNode;pj->adjvex=i;//對弧結(jié)點賦鄰接點“位置”信息

pj->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=pj;

//插入鏈表G.vertices[j]if(IncInfo){ //若弧含有相關(guān)信息，則輸入

cin>>pj->info;pi->info=pj->info;}}//for}//CreateUDG算法7.17.3圖的遍歷與二叉樹和樹的遍歷類似，圖結(jié)構(gòu)也有遍歷操作，即從某個頂點出發(fā)，沿著某條路徑對圖中其余頂點進(jìn)行訪問，且使每一個頂點只被訪問一次。但圖的遍歷要比樹的遍歷更復(fù)雜，因為圖中和同一頂點有弧或邊相通的頂點之間可能也有弧或邊，那么在訪問了某個頂點之后，可能沿著某條回路又回到了該頂點。為了避免同一頂點被重復(fù)訪問，則在遍歷過程中，必須為已經(jīng)訪問過的頂點加上標(biāo)識，以便再次途徑這樣的頂點時不再重復(fù)訪問。為此，需附設(shè)一維數(shù)組visited[0..n-1]，令其每個分量對應(yīng)圖中一個頂點，各分量的初值均設(shè)為FALSE或0，一旦訪問了某個頂點，便將visited中相應(yīng)分量的值置為TRUE或被訪問時的序號。通常，對圖進(jìn)行遍歷可有兩種搜索路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。7.3圖的遍歷與二叉樹和樹的遍歷類似，圖結(jié)構(gòu)也有遍歷操作，7.3.1深度優(yōu)先搜索遍歷圖深度優(yōu)先搜索遍歷類似于樹的先根遍歷，可以看成是先根遍歷的推廣。假設(shè)初始狀態(tài)是圖中所有頂點均未被訪問，則從某個頂點v出發(fā)，首先訪問該頂點，然后依次從它的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到，若此時尚有其他頂點未被訪問到，則另選一個未被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。顯然，深度優(yōu)先搜索是一個遞歸的過程。7.3.1深度優(yōu)先搜索遍歷圖深度優(yōu)先搜索遍歷類似于樹的先根7.3.1深度優(yōu)先搜索遍歷圖例如，從v3出發(fā)對下圖進(jìn)行深度優(yōu)先搜索，首先訪問頂點v3，然后從v3的鄰接頂點v2出發(fā)進(jìn)行深度優(yōu)先搜索，先后訪問v4、v9和v1，由于v3的第二個鄰接頂點v1已經(jīng)被訪問過，則不再從v1出發(fā)進(jìn)行搜索，而v3的下一個鄰接點v6未被訪問，則再從v6出發(fā)進(jìn)行搜索。124987563搜索過程中訪問頂點的次序為：v3->v2->v4->v9->v1->v6->v5->v8->v7

7.3.1深度優(yōu)先搜索遍歷圖例如，從v3出發(fā)對下圖進(jìn)行深度7.3.1深度優(yōu)先搜索遍歷圖算法7.2

Booleanvisit[MAX];voidDFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum;v++)visit[v]=False;for(v=0;v<G.vexnum;v++)if(!visit[v])DFS(G,v);}voidDFS(GraphG,intv){

//從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖Gvisited[v]=TRUE;VisitFunc(v);//訪問第v個頂點

for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visit[w])DFS(w);//對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS}//DFSFirstAdjVex(G,v)返回圖G中頂點v的第一個鄰接點，NextAdjVex(G,v,w)返回圖G中v相對于w的下一個鄰接點，w!=0說明尚有鄰接點存在。7.3.1深度優(yōu)先搜索遍歷圖算法深度優(yōu)先搜索遍歷圖在實際應(yīng)用中，首先要為圖選定存儲結(jié)構(gòu)，假設(shè)采用鄰接表表示圖，則算法7.2具體化為算法7.3。算法7.3voidDFS(ALGraphG,intv){//從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖Gvisit[v]=TRUE;VisitFunc(G.vertices[v].data);for(p=G.vertices[v].firstarc;p;p=p->nextarc;){w=p->adjvex;if(!visited[w])DFS(G,W);//對v未訪問過的鄰接頂點w遞歸調(diào)用DFS}//for}//DFS7.3.1深度優(yōu)先搜索遍歷圖在實際應(yīng)用中，首先要為圖選定存7.3.1深度優(yōu)先搜索遍歷圖查找的順序為：1、2、4、8、5、6、3、7213456781211241248124851248612483612480000000012345678111111111248563761248371243861248612481241217.3.1深度優(yōu)先搜索遍歷圖查找的順序為：1、2、4、8、57.3.2廣度優(yōu)先搜索遍歷圖

廣度優(yōu)先搜索的基本思想是：從圖中某頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使得“先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起點，由近至遠(yuǎn)，依次訪問和v有路徑相通且路徑長度為1,2...的頂點。7.3.2廣度優(yōu)先搜索遍歷圖廣度優(yōu)先搜索的基本思7.3.2廣度優(yōu)先搜索遍歷圖例如，從v3開始對下圖進(jìn)行廣度優(yōu)先搜索遍歷的過程為：首先訪問v3和v3的鄰接點v2、v1和v6，然后依次訪問v2的鄰接點v4和v6的鄰接點v5，接著訪問v4的鄰接點v9，最后訪問v5的鄰接點v8和v7。由于這些頂點的鄰接點都已經(jīng)被訪問，并且圖中所有頂點都已被訪問到，廣度優(yōu)先遍歷至此結(jié)束。124987563一層二層三層訪問序列為：v3->v2->v1->v6->v4->v5->v9->v8->v7

3216459877.3.2廣度優(yōu)先搜索遍歷圖例如，從v3開始對下圖進(jìn)行廣度7.3.2廣度優(yōu)先搜索遍歷圖

可見，圖的廣度優(yōu)先搜索過程類似于樹的層次遍歷。和深度優(yōu)先搜索類似，在遍歷的過程中也需要借助于訪問標(biāo)志數(shù)組visited。并且為了實現(xiàn)按照頂點被訪問的先后次序查詢它們的鄰接點，需附設(shè)一個隊列依訪問次序存儲已被訪問的頂點。對以鄰接矩陣表示方法存儲的圖進(jìn)行廣度優(yōu)先遍歷的算法如7.5所示。7.3.2廣度優(yōu)先搜索遍歷圖可見，圖的廣度優(yōu)7.3.2廣度優(yōu)先搜索遍歷圖算法7.5voidBFSTraverse(MGraphG){boolvisited[G.vexnum];//附設(shè)訪問標(biāo)志數(shù)組

SqQueueQ;//附設(shè)循環(huán)隊列Qfor(v=0;v<G.vexnum;++v)visited[v]=FALSE;InitQueve(Q,G.vexnum);for(v=0;v<G.vexnum;++v)if(!visited[v]){visited[v]=TRUE;VisitFunc(G.vex[v]);//訪問第v個頂點

EnQueue_Sq(Q,v);//v入隊列

while(!QueueEmpty_Sq(Q)){DeQueue_Sq(Q,u);//隊頭元素出隊并置為ufor(w=0;w<G.vexnum;w++)if(G.arcs[u,w].adj&&!visited[w]){visited[w]=TRUE;VisitFunc(w);//訪問圖中第w個頂點

EnQueue_Sq(Q,w);//當(dāng)前訪問的頂點w入隊列Q}//if}//while}//if}//BFSTraverse7.3.2廣度優(yōu)先搜索遍歷圖算法廣度優(yōu)先搜索遍歷圖從以上幾個算法中可以看出，遍歷圖的過程實質(zhì)上是通過邊或弧找鄰接點的過程，其消耗時間取決于所采用的存儲結(jié)構(gòu)。因此若采用同樣的存儲結(jié)構(gòu)，廣度優(yōu)先遍歷的時間復(fù)雜度和深度優(yōu)先搜索相同。由于算法7.5中的存儲結(jié)構(gòu)為鄰接矩陣，因此算法7.5的時間復(fù)雜度為O(n2)。圖遍歷是圖的基本操作，也是一些圖的應(yīng)用問題求解算法的基礎(chǔ)，以此為框架可以派生出許多應(yīng)用算法。7.3.2廣度優(yōu)先搜索遍歷圖從以上幾個算法中可以看出，遍歷7.4圖的連通性問題7.4.1

無向圖的連通分量和生成樹

7.4.2

有向圖的強連通分量

7.4.3

連通網(wǎng)的最小生成樹7.4圖的連通性問題7.4.1無向圖的連通分量和生成7.4.1無向圖的連通分量和生成樹

對于連通圖從任一頂點出發(fā)進(jìn)行深度（廣度）優(yōu)先遍歷，即可訪問到圖的所有頂點；對于非連通圖需要從多個頂點出發(fā)進(jìn)行遍歷。(a)非連通圖(b)非連通圖的兩個極大連通分量ABCDEFACDBEF7.4.1無向圖的連通分量和生成樹對于連通圖從任7.4.1無向圖的連通分量和生成樹

設(shè)連通圖G邊的集合為E(G)，將E(G)分為兩個集合T(G)和B(G)，T(G)為遍歷圖過程中經(jīng)歷的邊的集合，B(G)為剩余的邊。T(G)和G中所有頂點一起構(gòu)成連通圖G的極大連通子圖，是連通圖的生成樹。如果遍歷采用深度優(yōu)先搜索，則得到的深度優(yōu)先生成樹；如果遍歷采用廣度優(yōu)先搜索，則得到的廣度優(yōu)先生成樹。而非連通圖只有生成樹林。(a)連通圖12345678（b）深度優(yōu)先生成樹12485673(c)廣度優(yōu)先生成樹765482317.4.1無向圖的連通分量和生成樹設(shè)連通圖G邊的集合為7.4.2有向圖的強連通分量(a)非強連通圖(b)非強連通圖兩個強連通分量

在有向圖G中，如果對于每一對vi,vj∈V，vi,≠vj

，從vi到vj和從vj到vi都存在路徑，則G是強連通圖。有向圖中的最大連通子圖稱作有向圖的強連通分量。ACBFDGECBDEAF7.4.2有向圖的強連通分量(a)非強連通圖(b)非7.4.3連通網(wǎng)的最小生成樹

在一個含有n個頂點的連通圖中，必能從中選出n-1條邊構(gòu)成一個極小連通子圖，它含有圖中全部n個頂點，但只有足以構(gòu)成一棵樹的n-1條邊，稱這棵樹為連通圖的生成樹。例如，對下圖(a)進(jìn)行深度優(yōu)先搜索遍歷過程中經(jīng)過的邊和全部頂點構(gòu)成的極小連通子圖(b)即為(a)的一棵生成樹。124987563124987563(a)(b)7.4.3連通網(wǎng)的最小生成樹在一個含有n個頂點7.4連通網(wǎng)的最小生成樹

在含有n個頂點的連通網(wǎng)中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權(quán)值之和達(dá)到最小，則稱其為連通網(wǎng)的最小生成樹。例如，對于如右圖所示的連通網(wǎng)可以有多棵權(quán)值總和不相同的生成樹。abcdefg1216431489106527abcdefg1639627abcdefg1243827abcdefg1216414810(a)權(quán)值總和為43(b)權(quán)值總和為36(a)權(quán)值總和為647.4連通網(wǎng)的最小生成樹在含有n個頂點的連通網(wǎng)中選擇權(quán)值序列：23456789101214167.4連通網(wǎng)的最小生成樹構(gòu)造連通網(wǎng)的最小生成樹的算法主要有兩種。1.克魯斯卡爾(Kruskal)算法基本思想：按照權(quán)值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構(gòu)成回路。具體做法：首先構(gòu)造一個只含n個頂點的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中，并使森林中不產(chǎn)生回路，直至森林變成一棵樹為止。abcdefg1216431489106527abcdefg1243827(c,e)產(chǎn)生回路(c,f)產(chǎn)生回路(f,g)產(chǎn)生回路(b,c)產(chǎn)生回路已選出n-1條邊權(quán)值序列：2345678917.4連通網(wǎng)的最小生成樹2.普里姆(Prim)算法

假設(shè)G=(V,E)為一網(wǎng)，其中V為網(wǎng)中所有頂點的集合，E為網(wǎng)中所有帶權(quán)邊的集合。設(shè)置兩個新的集合U和T，其中U用于存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。令U的初值為U={u0}(假設(shè)從頂點u0出發(fā)構(gòu)造最小生成樹)，令T的初值為空，T={}。普里姆算法的思想是：從所有u?U，v?V-U的邊中選取權(quán)值最小的邊(u,v)，將頂點v加入集合U中，將邊(u,v)加入集合T中，如此不斷重復(fù)，直到U=V為止，最小生成樹構(gòu)造完畢，這時集合T中包含了最小生成樹中的所有邊。7.4連通網(wǎng)的最小生成樹2.普里姆(Prim)算法7.4連通網(wǎng)的最小生成樹例如，利用Prim算法對下圖從頂點a開始構(gòu)造最小生成樹。abcdefg1216431489106527abcdefgU:{a}T:{}(a,b):12(a,f):16(a,g):1412U:{a,b}T:{(a,b)}(a,f):16(a,g):14(b,c):10(b,f):77U:{a,b,f}T:{(a,b),(b,f)}(a,g):14(b,c):10(f,c):6(f,e):2(f,g):92U:{a,b,e,f}T:{(a,b),(b,f),(f,e)}(a,g):14(b,c):10(e,c):5(e,d):4(e,g):8(f,c):6(f,g):94U:{a,b,d,e,f}T:{(a,b),(b,f),(f,e),(e,d)}(a,g):14(e,g):8(f,g):9(b,c):10(d,c):3(e,c):5(f,c):63U:{a,b,c,d,e,f}T:{(a,b),(b,f),(f,e),(e,d),(d,c)}(a,g):14(e,g):8(f,g):98U:{a,b,c,d,e,f,g}T:{(a,b),(b,f),(f,e),(e,d),(d,c),(e,g)}此時，所有頂點都已加入集合U，即U＝V，最小生成樹構(gòu)造完畢。7.4連通網(wǎng)的最小生成樹例如，利用Prim算法對下圖從頂點7.4連通網(wǎng)的最小生成樹比較以上兩種算法可見：Kurskal算法主要對邊進(jìn)行操作，又稱為“加邊法”，其時間復(fù)雜度為O(e)。這種方法比較適用于稀疏圖。Prim算法主要對頂點進(jìn)行操作，又稱為“加點法”，其時間復(fù)雜度為O(n2)。比較適用于稠密圖。7.4連通網(wǎng)的最小生成樹比較以上兩種算法可見：7.5有向無環(huán)圖及其應(yīng)用一個無環(huán)的有向圖稱為有向無環(huán)圖（directedacyclinegraph），簡稱DAG。abced有向無環(huán)圖是描述一項系統(tǒng)或工程的進(jìn)行過程的有效工具，常用來判斷工程能否順利進(jìn)行及估算完成時間。7.5有向無環(huán)圖及其應(yīng)用一個無環(huán)的有向圖稱為有向無環(huán)圖（7.5.1拓?fù)渑判?/p>

有向無環(huán)圖在工程計劃和管理方面有著廣泛的應(yīng)用。一項工程往往可以分解為一些具有相對獨立性的子工程，稱這些子工程為活動。子工程之間在進(jìn)行的時間上有著一定的相互制約關(guān)系?？梢杂糜邢驁D表示子工程及其相互制約關(guān)系，其中以頂點表示活動，弧表示活動之間的優(yōu)先制約關(guān)系，稱這種有向圖為活動在頂點上的網(wǎng)絡(luò)，簡稱活動頂點網(wǎng)絡(luò)(ActivityOnVertexNetwork)，或AOV網(wǎng)。7.5.1拓?fù)渑判蛴邢驘o環(huán)圖在工程計劃和管理方面有著廣泛7.5.1拓?fù)渑判蚴裁词峭負(fù)渑判?？若集合X上的關(guān)系R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關(guān)系。設(shè)R是集合X上的偏序，如果對每個x,y∈X必有xRy或yRx，則稱R是集合X上的全序關(guān)系。由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱為拓?fù)渑判?。v2v1v4v3v2v1v4v37.5.1拓?fù)渑判蚴裁词峭負(fù)渑判?？v2v1v4v3v2v17.5.1拓?fù)渑判蚶?，在課程計劃中，每門課程的學(xué)習(xí)就是一項活動，一門課程可能以其他某幾門課程為先修基礎(chǔ)，而它本身又可能是另一些課程的先修基礎(chǔ)，各課程之間的先修關(guān)系可用活動頂點網(wǎng)絡(luò)表示。C2C1C9C3C11C4C6C12C8C7C5C13C10課程號課程名先修課C1C語言程序設(shè)計無C2計算機導(dǎo)論無C3數(shù)據(jù)結(jié)構(gòu)C1，C13C4計算機系統(tǒng)結(jié)構(gòu)C2C5編譯原理C3C6操作系統(tǒng)C3，

C4C7計算機網(wǎng)絡(luò)C5C8數(shù)據(jù)庫C5，

C6C9高等數(shù)學(xué)無C10數(shù)值分析C1，C9C11C++語言C1C12軟件工程C7，C8C13離散數(shù)學(xué)C97.5.1拓?fù)渑判蚶?，在課程計劃中，每門課程的學(xué)習(xí)就是一7.5.1拓?fù)渑判蛟诨顒泳W(wǎng)絡(luò)中不允許出現(xiàn)回路，因為回路意味著某項活動的開始將以自己工作的完成為先決條件，這種情況稱為死鎖現(xiàn)象。檢測有向圖中是否存在回路的方法之一是求有向圖中頂點的一個排列，這個排列滿足：若在有向圖中從u到v有一條弧，則在此序列中u一定排在v之前，稱有向圖的這個操作為拓?fù)渑判?，所得頂點序列為拓?fù)溆行蛐蛄小?.5.1拓?fù)渑判蛟诨顒泳W(wǎng)絡(luò)中不允許出現(xiàn)回路，因為回路意味7.5.1拓?fù)渑判駽2C1C9C3C11C4C6C12C8C7C5C13C10例如，下面兩個序列就是左圖的拓?fù)溆行蛐蛄校篊1,C9,C10,C13,C3,C11,C2,C4,C5,C6,C7,C8,C12C2,C4,C1,C9,C13,C3,C6,C5,C8,C7,C10,C11,C12通常，頂點的拓?fù)溆行蛐蛄惺遣晃ㄒ坏?。但如果AOV網(wǎng)中存在回路，則不可能得到拓?fù)溆行蛐蛄小?.5.1拓?fù)渑判駽2C1C9C3C11C4C6C12C87.5.1拓?fù)渑判?/p>

如何進(jìn)行拓?fù)渑判颍?/p>

從其定義可知，在拓?fù)溆行蛐蛄兄械牡谝粋€頂點必定是在AOV網(wǎng)中沒有前驅(qū)的結(jié)點，則首先在AOV網(wǎng)中選取一個沒有前驅(qū)的頂點，輸出它并從AOV網(wǎng)中刪去所有以它為尾的弧，重復(fù)此操作直至所有頂點都被輸出為止。如果在此過程中找不到?jīng)]有前驅(qū)的頂點，則說明尚未輸出的子圖中必有回路。12678543輸出22輸出525輸出7257輸出12571輸出325713輸出4257134輸出62571346輸出8257134687.5.1拓?fù)渑判蛉绾芜M(jìn)行拓?fù)渑判颍?2678543輸出7.5.1拓?fù)渑判蛟谟嬎銠C中實拓?fù)渑判蛩惴〞r，需要以“入度為零”作為“沒有前驅(qū)”的量度，而刪除結(jié)點及以它為尾的弧的操作不必真正對圖的存儲結(jié)構(gòu)進(jìn)行，可用弧頭頂點的入度減1來實現(xiàn)，算法如下所示：建有向圖的鄰接表并統(tǒng)計各頂點的入度;取入度為0的頂點v;while(v<>0){//尚有入度為零的頂點存在

cout<<v;++m;//輸出入度為零的頂點，并記數(shù)

w=FirstAdj(v);//W為V的鄰接點

while(w<>0){//尚有V的鄰接點存在

inDegree[w]--;//W的入度減一

w=nextAdj(v,w);//取V的下一個鄰接點

}

取下一個入度為0的頂點v;}if(m<n)cout<<(“圖中有回路”)7.5.1拓?fù)渑判蛟谟嬎銠C中實拓?fù)渑判蛩惴〞r，需要以“入度7.5.2關(guān)鍵路徑對于一項工程而言，還可以用弧表示活動，用頂點表示事件，所謂事件是一個關(guān)于某(幾)項活動開始或完成的斷言：指向它的弧所表示活動已經(jīng)完成，從它出發(fā)的弧所表示的活動開始進(jìn)行。每條弧可以帶有權(quán)值，以表示活動進(jìn)行需要的時間等。稱這種網(wǎng)絡(luò)為活動在邊上的網(wǎng)絡(luò)，簡稱為活動邊網(wǎng)絡(luò)，或AOE網(wǎng)。源點匯點afdbcehgka1=6a7=8a5=1a3=5a6=2a11=4a9=4a2=4a4=1a8=7a10=2如左圖所示的AOE網(wǎng)，ai表示第i(i=1,2…,11)項活動，弧上的數(shù)字表示完成子工程所需要的天數(shù)。a表示整個工程的開始，其入度為零，通常稱其為源點；k表示整個工程的結(jié)束，其出度為零，通常稱其為匯點。一個工程的AOE網(wǎng)應(yīng)該是一個單源點和單匯點的有向無環(huán)圖。7.5.2關(guān)鍵路徑對于一項工程而言，還可以用弧表示活動，用7.5.2關(guān)鍵路徑在AOE網(wǎng)絡(luò)中，一條路徑上各弧權(quán)值之和稱為該路徑的帶權(quán)路徑長度。由于AOE網(wǎng)絡(luò)中某些活動可以并行進(jìn)行，則完成整個工程的最短時間即為從源點到匯點最長的帶權(quán)路徑長度的值，稱這樣的路徑為關(guān)鍵路徑，關(guān)鍵路徑上的弧稱為關(guān)鍵活動。afdbcehgka1=6a7=8a5=1a3=5a6=2a11=4a9=4a2=4a4=1a8=7a10=2例如，左圖中從源點a到匯點k共有5條路徑，帶權(quán)路徑長度如下：

a-b-e-g-k:17 a-b-e-h-k:18 a-c-e-g-k:15 a-c-e-h-k:16 a-d-f-h-k:15其中，{a-b-e-h-k}為關(guān)鍵路徑a1,a4,a8,a11為關(guān)鍵活動7.5.2關(guān)鍵路徑在AOE網(wǎng)絡(luò)中，一條路徑上各弧權(quán)值之和稱7.5.2關(guān)鍵路徑如何求關(guān)鍵路徑？首先定義四個描述量。假設(shè)頂點V1為源點，Vn為匯點，事件V1的發(fā)生時刻作為事件原點(0時刻)。ve(j)：事件Vj可能發(fā)生的最早時刻，它是從V1到Vj的最長帶權(quán)路徑長度

0j=1 ve(j)=max{ve(i)+w(ViàVj)}j=2,3,…,n Vi

àVj

是弧 其中，w(ViàVj)表示該弧的權(quán)值。對于一個特定的頂點Vj(2≤j≤n)，上式表示考察Vj的所有前驅(qū)結(jié)點Vi1，Vi2，…，Vip，在ve(i1)+w(Vi1àVj),…,ve(ip)+w(VipàVj)中選最大值。計算ve時，應(yīng)該按頂點的拓?fù)溆行虼涡驈脑袋c開始向下推算至匯點。7.5.2關(guān)鍵路徑如何求關(guān)鍵路徑？ve(j)：事7.5.2關(guān)鍵路徑vl(i)：在保證不延誤整個工期，即保證Vn在ve(n)時刻發(fā)生的前提下，事件Vi發(fā)生所允許的最晚時刻。它等于ve(n)減去Vi到Vn的最長帶權(quán)路徑長度。

ve(n)i=nvl(i)=min{vl(j)-w(ViàVj)}i=n-1,…,2,1ViàVj是弧對于一個特定的頂點Vi(1≤i≤n-1)，上式考察Vi的所有后繼結(jié)點Vj1，Vj2，…

，Vjq，在vl(j1)-w(ViàVj1),…,vl(jq)-w(ViàVjq)中選最小值。計算vl時，順序和ve相反，從匯點開始向回推算至源點。7.5.2關(guān)鍵路徑vl(i)：在保證不延誤整個工期7.5.2關(guān)鍵路徑ee(k)：活動ak(令ak是ViàVj)可能開始的最早時刻。顯然，它應(yīng)該是事件Vi可能發(fā)生的最早時刻ve(i)，即

ee(k)=ve(i)(k=1,2,…,mm為弧的數(shù)目)el(k)：活動ak(令ak是ViàVj)在保證不延誤整個工期的前提下，活動ak開始所允許的最晚時刻。它應(yīng)該是Vj所發(fā)生所允許的最晚時刻vl(j)減去w(ViàVj)，即：

el(k)=vl(j)-w(ViàVj)(k=1,2,…,m)

根據(jù)ve和vl，可以計算出所有弧上的ee和el值，由ee(k)和el(k)的定義可知，如果某條弧ak的ee(k)和el(k)(1≤k≤m)值相等，則為關(guān)鍵活動。反之，對于非關(guān)鍵活動，el(k)-ee(k)的值時該活動的期限余量(或稱松弛時間)，在此范圍內(nèi)的適度延誤不會影響整個工程的工期。7.5.2關(guān)鍵路徑ee(k)：活動ak(令ak是ViàV7.5.2關(guān)鍵路徑afdbcehgka1=6a7=8a5=1a3=5a6=2a11=4a9=4a2=4a4=1a8=7a10=2vevleeelel-ee權(quán)值abcdefghka1a2a3a4a5a6a7a8a9a10a1164511287424從中可以看出，活動a1,a4,a8,a11為關(guān)鍵活動7.5.2關(guān)鍵路徑afdbcehgka1=6a7=8a5=7.5.2關(guān)鍵路徑一個求解關(guān)鍵路徑的AOE網(wǎng)102467358a1=6a5=1a7=9a11=4a9=4a6=2a4=1a8=7a10=2a2=4a3=57.5.2關(guān)鍵路徑一個求解關(guān)鍵路徑的AOE網(wǎng)10246737.5.2關(guān)鍵路徑ak由弧<i,j>表示，設(shè)其持續(xù)時間為dut(<i,j>)，則：E[k]=VE[j];L[k]=VL[j]-dut(<i,j>)求關(guān)鍵路徑的步驟為：（1）從VE[0]=0開始遞推求各頂點的最早發(fā)生時間：VE[j]=MAX(VE[i]+dut(<i,j>))(j=1..n-1)（2）從VL[n-1]=VL[n-1]開始遞推求各頂點的最遲發(fā)生時間：VL[i]=MIN(VL[j]-dut(<i,j>))(i=n-2..0)（3）計算各活動的最早開始時間和最遲開始時間，凡是差為0的均為關(guān)鍵活動。

EE[k]=VE[i];EL[k]=VL[j]-dut(<i,j>)ijak7.5.2關(guān)鍵路徑ak由弧<i,j>表示，設(shè)其持續(xù)時間為d102467358a1=6a5=1a7=9a11=4a9=4a6=2a4=1a8=7a10=2a2=4a3=5EE[5]=4EL[5]=6EE[11]=14EL[11]=14EE[7]=7EL[7]=7EE[9]=7EL[9]=10EE[1]=0EL[1]=0EE[4]=6EL[4]=6EE[2]=0EL[2]=2EE[7]=7EL[7]=7EE[10]=16EL[10]=16EE[3]=0EL[3]=3EE[6]=5EL[6]=8VL[0]=0VL[1]=6VL[3]=8VL[5]=10VL[4]=7VL[6]=16VL[7]=14VL[8]=18VL[2]=6VE[4]=7VE[0]=0VE[1]=6VE[2]=4VE[3]=5VE[5]=7VE[6]=16VE[7]=14VE[8]1=6a5=1a7=9a11=4a9=47.6單源最短路徑最短路徑問題是圖的典型應(yīng)用問題。例如某一地區(qū)的一個公路網(wǎng)，給定了該網(wǎng)內(nèi)的n個城市以及這些城市之間的相通公路的距離，能否找到從某一城市A到另一城市B之間一條距離最近的通路呢？如果將城市用頂點表示，城市間的公路用邊表示，公路的長度作為邊的權(quán)值，這個問題就歸結(jié)為在有向網(wǎng)圖中求頂點A到頂點B的所有路徑中，邊的權(quán)值之和最小的一條路徑，這條路徑就是兩點之間的最短路徑，并稱路徑上的第一個頂點為源點，最后一個頂點為終點。在非網(wǎng)圖中最短路徑是指兩點之間經(jīng)過的邊數(shù)最少的路徑。7.6單源最短路徑最短路徑問題是圖的典型應(yīng)用問題。例如某一7.6單源最短路徑從源點到終點之間的路徑可能存在三種情況：沒有路徑相通只有一條路經(jīng)，則此路徑就是最短路徑存在多條路徑，則必存在一條最短路徑bagfecd30201091851510812bàf:沒有路徑

bàa:只有一條路徑

bàd:存在三條路徑(b-d):30(b-c-e-d):27(b-a-g-c-e-d):64其中，(b->c->e->d)為最短路徑7.6單源最短路徑從源點到終點之間的路徑可能存在三種情況7.6單源最短路徑

如何求得從源點到各終點的最短路徑？Dijkstra提出了一種按路徑長度遞增的次序求從源點到各終點的最短路徑的算法。假設(shè)從源點v0到各終點v1,v2,…,vk之間存在最短路徑，其路徑長度分別為l1,l2,…,lk，并且lp(1<=p<=k)為其中的最小值，即從源點v0到終點vp的最短路徑是從源點到其他終點的最短路徑中長度最短的一條路徑，這條路徑上必定只有一條弧，否則它就不可能是所有最短路徑中的最短者。第二條次短(從源點v0到終點vq)的最短路徑只能產(chǎn)生以下兩種情況：從源點到該點存在弧<v0,vq>

從已求得的最短路徑的頂點vp到該點有弧<vp,vq>存在，且<v0,vp>和<vp,vq>上的權(quán)值之和小于<v0,vq>上的權(quán)值。依此類推，一般情況下，假設(shè)已求得最短路徑的頂點有{vp1,vp2,…vpk}，則下一條最短路徑的產(chǎn)生只可能是已求出的這些最短路徑的延伸，也就是從源點間接到達(dá)終點，或者是從源點直接通過一條弧到達(dá)終點。7.6單源最短路徑如何求得從源點到各終點的最短路徑？7.6單源最短路徑根據(jù)以上思路，Dijkstra算法描述如下：1.

假設(shè)AS[n][n]為有向網(wǎng)的鄰接矩陣，S為已找到最短路徑的終點集合，其初始狀態(tài)只含一個頂點，即源點。另設(shè)一維數(shù)組Dist[n]，其中每個分量表示當(dāng)前所找到的從源點出發(fā)(經(jīng)過集合S中的頂點)到各個終點的最短路徑長度，則Dist的初值為：Dist[k]=AS[i,k]2.

選擇u，使得Dist[u]=min{Dist[w]|w∈V-S}3.

修改Dist數(shù)組中所有尚未找到最短路徑的終點的對應(yīng)分量值，如果Dist[u]+AS[u,w]<Dist[w]

則Dist[w]=Dist[u]+AS[u,w]4.

重復(fù)上述2和3的操作n-1次，即可求得從源點到所有終點的最短路徑。此外，為了記下長度為Dist[w]的最短路徑，還需要附設(shè)路徑矩陣Path[n][n]。7.6單源最短路徑根據(jù)以上思路，Dijkstra算法描述bagfecd30201091851510812bDist[7]Path[7][7]S:V-S:{a,c,d,e,f,g}abcdefgbbcdaDist和Path的初始狀態(tài)，求得從b到c的最短路徑c15S:{b,c}V-S:{a,d,e,f,g}bgcdbbecee修改Dist和Path的值，求得從b到e的最短路徑302729S:{b,c,e}V-S:{a,d,f,g}修改Dist和Path的值，求得從b到a的最短路徑S:{b,c,e,a}V-S:{d,f,g}修改Dist和Path的值，求得從b到d的最短路徑gS:{b,c,e,a,d}V-S:{f,g}修改Dist和Path的值，求得從b到g的最短路徑aS:{b,c,e,a,d,g}V-S:{f}修改Dist和Path的值，可見從b到f沒有路徑至此，從源點b出發(fā)到各終點的最短路徑求解完畢，最短路徑序列如矩陣Path所示abcdefgabcdefgabcdefgbagfecd30201091851510812bDist[

第7章圖（Graph）主講：李耀國數(shù)據(jù)結(jié)構(gòu)（DataStructure）

第七章圖

圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個元素最多只有一個直接前驅(qū)和一個直接后繼。在樹型結(jié)構(gòu)中，數(shù)據(jù)元素之間存在明顯的層次關(guān)系，并且每層的元素可能和下一層的多個元素相鄰，但只能和上一層的一個元素相鄰。而在圖形結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是任意的，圖中的任意兩個元素之間都可能相鄰。圖是計算機應(yīng)用過程中對實際問題進(jìn)行數(shù)學(xué)抽象和描述的強有力的工具，數(shù)據(jù)結(jié)構(gòu)中對圖的討論側(cè)重于在計算機中如何表示圖以及如何實現(xiàn)圖的操作和應(yīng)用等。第七章圖圖是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。第七章圖和廣義表7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應(yīng)用7.5.1拓?fù)渑判?.5.2關(guān)鍵路徑7.6最短路徑第七章圖和廣義表7.1圖的定義和術(shù)語7.1圖的定義和術(shù)語圖由一個頂點的有窮非空集合V(G)和一個弧的集合E(G)組成，通常記做G=(V,E)。圖中的頂點即為數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，弧的集合E實際上是定義在頂點集合上的一個關(guān)系。用有序?qū)?lt;v,w>表示從v到w的一條弧?；【哂蟹较蛐?，以帶箭頭的線段表示，通常稱v為弧尾或始點，稱w為弧頭或終點，此時的圖稱為有向圖。若圖中從v到w有一條弧，同時從w到v也有一條弧，則以無序?qū)?v,w)代替這兩個有序?qū)?lt;v,w>和<w,v>,表示v和w之間的一條邊。此時的圖在頂點之間不再強調(diào)方向性的特征，稱為無向圖。7.1圖的定義和術(shù)語圖由一個頂點的有窮非空集合V(G)和一7.1圖的定義和術(shù)語圖G1是一個有向圖，G1=(V1,{A1})。其中:V1={A,C,B,F,D,E,G}A1={<A,B>,<B,C>,<B,F>,<B,E>,<C,E>,<E,D>,<D,C>,<E,B>,<F,G>}ACBFDGE有向圖G17.1圖的定義和術(shù)語圖G1是一個有向圖，G1=(V1,{A7.1圖的定義和術(shù)語圖G2是一個無向圖，G2=(V2,{E2})。其中：

V2={A,B,C,D,E,F}E2={(A,B),(A,C),(B,C),(B,E),(B,F),(C,F),(C,D),(E,F),(C,E)}ABCDEF無向圖G27.1圖的定義和術(shù)語圖G2是一個無向圖，G2=(V2,{E7.1圖的定義和術(shù)語

在實際應(yīng)用中，圖的弧或邊往往與具有一定意義的數(shù)相關(guān)，稱這些數(shù)為權(quán)(weight)。分別稱帶權(quán)的有向圖和無向圖為有向網(wǎng)和無向網(wǎng)。123456712345671918212756103311706475806018069584331324430無向網(wǎng)有向網(wǎng)7.1圖的定義和術(shù)語在實際應(yīng)用中，圖的弧或邊往往與具有7.1圖的定義和術(shù)語

稀疏圖和稠密圖假設(shè)用n表示圖中頂點數(shù)目，用e表示邊或弧的數(shù)目。若不考慮頂點到其自身的弧或邊，則對于無向圖，邊數(shù)e的取值范圍是0到n(n-1)/2。稱具有n(n-1)/2條邊的無向圖為完全圖。對于有向圖，弧的數(shù)目e的取值范圍是0到n(n-1)。稱具有n(n-1)條弧的有向圖為有向完全圖。若e<nlogn，則稱為稀疏圖，反之稱為稠密圖。

子圖假設(shè)有兩個圖G=(V,{E})和G’=(V’,{E’})，若V’V且E’E，則稱G’為G的子圖。7.1圖的定義和術(shù)語稀疏圖和稠密圖假設(shè)用n表示圖中頂點7.1圖的定義和術(shù)語度、入度和出度若u->v是圖中的一條弧，則稱u鄰接到v，或v鄰接自u。圖中所鄰接到某頂點v的弧的數(shù)目，稱為該頂點的入度，記作:ID(v)；反之，從某頂點u出發(fā)的弧的數(shù)目，稱為該頂點的出度，記作:OD(u)。頂點v的入度和出度之和稱為該頂點的總度，簡稱為度，記作:TD(v)。例如圖G1中頂點B的入度ID(B)=2，出度OD(B)=3，度TD(B)=5。無向圖中頂點的度定義為與該頂點相連的邊的數(shù)目。一般情況下，如果頂點vi的度記作TD(vi)，則一個含有n個頂點，e條邊或弧的圖，滿足如下關(guān)系：ACBFDGE7.1圖的定義和術(shù)語度、入度和出度若u->v是圖中的一條7.1圖的定義和術(shù)語路徑和回路若有向圖G中k+1個頂點之間都有弧存在，則這個頂點的序列{v0,v1,…vk}為從頂點v0到頂點vk的一條有向路徑，路徑中弧的數(shù)目定義為路徑長度。若序列中的頂點都不相同，則為簡單路徑。對無向圖，相鄰頂點之間存在邊的k+1個頂點序列構(gòu)成一條長度為k的無向路徑。如若v0和vk是同一個頂點，則是一條由某個頂點出發(fā)又回到自身的路徑，稱這種路徑為回路或環(huán)。7.1圖的定義和術(shù)語路徑和回路若有向圖G中k+1個頂點7.1圖的定義和術(shù)語連通圖和連通分量若無向圖中任意兩個頂點之間都存在一條無向路徑，則稱該無向圖為連通圖。對有向圖而言，若圖中任意兩個頂點之間都存在一條有向路徑，則稱該有向圖為強連通圖。非連通圖中的各個極大連通子圖稱為該圖的連通分量。ABCDEFACBFDGE非強連通圖和強連通分量非連通圖和連通分量7.1圖的定義和術(shù)語連通圖和連通分量若無向圖中任意兩個7.1圖的定義和術(shù)語圖的抽象數(shù)據(jù)類型ADTGraph{

數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關(guān)系R:R={VR}VR={<v,w>|v,w∈P(v,w),<v,w>表示從到的弧,

謂詞P(v,w)定義了弧<v,w>的意義或信息}

基本操作：CreateGraph(&G,V,VR)初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。DestoryGraph(&G)初始條件：圖G存在。操作結(jié)果：銷毀圖G。LocateVex(G,u)初始條件：圖G存在，u和G中頂點有相同特征。操作結(jié)果：若G中存在頂點u，則返回該頂點在圖中的位置；否則返回其他信息。more7.1圖的定義和術(shù)語圖的抽象數(shù)據(jù)類型more7.1圖的定義和術(shù)語GetVex(G,v)初始條件：圖G存在，v是G中的某個頂點。操作結(jié)果：返回v的值。PutVex(&G,v,value)初始條件：圖G存在，v是G中的某個頂點。操作結(jié)果：對v賦值value。FirstAdjVex(G,v)初始條件：圖G存在，v是G中的某個頂點。操作結(jié)果：返回v的第一個鄰接點，若該頂點在G中無鄰接點，則返回空。NextAdjVex(G,v,w)初始條件：圖G存在，v是G中的某個頂點，w是v的鄰接頂點。操作結(jié)果：返回v的(相對于w的)下一個鄰接點。若w是v的最后一個鄰接點，則返回空。more7.1圖的定義和術(shù)語GetVex(G,v)more7.1圖的定義和術(shù)語InsertVex(&G,v)

初始條件：圖G存在，v和圖中頂點有相同特征。操作結(jié)果：在圖G中增添新頂點v。

DeleteVex(&G,v)

初始條件：圖G存在，v是G中的某個頂點。操作結(jié)果：刪除G中頂點v及其相關(guān)的弧。

InsertArc(&G,v,w)

初始條件：圖G存在，v和w是G中的兩個頂點。操作結(jié)果：在圖G中增添弧<v,w>，若G是無向的，則還增添對稱弧<w,v>。

DeleteArc(&G,v,w)

初始條件：圖G存在，v和w是G中的兩個頂點。操作結(jié)果：在圖G中刪除弧<v,w>，若G是無向的，則還刪除對稱弧<w,v>。more7.1圖的定義和術(shù)語InsertVex(&G,v)mo7.1圖的定義和術(shù)語DFSTraverse(G,v,visit())

初始條件：圖G存在，v是G中的某個頂點，visit是針對頂點的應(yīng)用函數(shù)。操作結(jié)果：從頂點v起深度優(yōu)先遍歷圖G，并對每個頂點調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。

BFSTraverse(G,v,visit())

初始條件：圖G存在，v是G中的某個頂點，visit是針對頂點的應(yīng)用函數(shù)。操作結(jié)果：從頂點v起廣度優(yōu)先遍歷圖G，并對每個頂點調(diào)用函數(shù)visit一次且僅一次。一旦visit()失敗，則操作失敗。}ADTGraph7.1圖的定義和術(shù)語DFSTraverse(G,v,v7.2圖的存儲結(jié)構(gòu)圖是一種典型的復(fù)雜結(jié)構(gòu)，圖中頂點可能同任意一個其他頂點之間存在關(guān)系。因此，圖沒有順序映象的存儲結(jié)構(gòu)。圖有兩種常用的存儲結(jié)構(gòu)。7.2.1圖的數(shù)組(鄰接矩陣)