數據結構-第七章圖

第7章圖7.1圖的定義與基本術語7.2圖的存儲結構7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖的應用7.6最短路徑圖結構與表結構和樹結構的不同表現在結點之間的關系上，線性表中結點之間的關系是一對一的；樹是按分層關系組織的結構，樹結構之間是一對多；對于圖結構，圖中頂點之間的關系可以是多對多，即一頂點和其它頂點間的關系是任意的，可以有關也可以無關。因此，圖G

樹TL，圖是一種比較復雜的非線性數據結構。圖作為一種非線性結構，被廣泛應用于多個技術領域。在本章中，主要是應用圖論的理論知識來討論如何在計算機上表示和處理圖，以及如何利用圖來解決一些實際問題。7.1圖的定義與基本術語7.1.1圖的定義圖（Graph）是一種網狀數據結構，其形式化定義如下：Graph=（V，R）V={x∣x∈DataObject}R={VR}VR={<x，y>∣P（x，y）∧（x，y∈V）}

DataObject為一個集合，該集合中的所有元素具有相同的特性。V中的數據元素通常稱為頂點（vertex），VR是兩個頂點之間的關系的集合。P（x，y）表示x和y之間有特定的關聯屬性P。

?。喝?lt;x，y>∈VR，則<x，y>表示從頂點x到頂點y的一條?。╝rc），并稱x為弧尾（tail）或起始點，稱y為弧頭（head）或終端點。有向圖：若圖中的邊是有方向的，稱這樣的圖為有向圖。無向圖：若<x，y>∈VR，必有<y，x>∈VR，即VR是對稱關系，這時以無序對（x，y）來代替兩個有序對，表示x和y之間的一條邊（edge），此時的圖稱為無向圖。

例如：下圖G1是有向圖，G2是無向圖2134G12145G23在圖中，我們可以將任一頂點看成是圖的第一個頂點，同理，對于任一頂點而言，它的鄰接點之間也不存在順序關系。為了操作的方便，我們需要將圖中的頂點按任意序列排列起來。頂點在這個人為的隨意排列中的位置序號稱為頂點在圖中的位置。圖的基本操作和其它數據結構一樣，也有創(chuàng)建、插入、刪除、查找等。圖的抽象類型定義：ADTGraph數據對象V：一個集合，該集合中的所有元素具有相同的特性。數據關系R：R={VR}VR={<x，y>∣P（x，y）∧（x，y∈V）}基本操作：（1）GreateGraph(G)：創(chuàng)建圖G。（2）DestoryGraph(G)：銷毀圖G。（3）LocateVertex(G,v)：確定頂點v在圖G中的位置。若圖G中沒有頂點v，則函數值為“空”。（4）GetVertex(G,I)：取出圖G中的第i個頂點的值。若i>圖G中頂點數，則函數值為“空”。

（5）FirstAdjVertex(G,v)：求圖G中頂點v的第一個鄰接點。若v無鄰接點或圖G中無頂點v，則函數值為“空”。

（6）NextAdjVertex(G,v,w)：已知w是圖G中頂點v的某個鄰接點，求頂點v的下一個鄰接點（緊跟在w后面）。若w是v的最后一個鄰接點，則函數值為“空”。

（7）InsertVertex(G,u)：在圖G中增加一個頂點u。

（8）DeleteVertex（G，v）：刪除圖G的頂點v及與頂點v相關聯的弧。

（9）InsertArc（G，v，w）：在圖G中增加一條從頂點v到頂點w的弧。

（10）DeleteArc（G，v，w）：刪除圖G中從頂點v到頂點w的弧。

（11）TraverseGraph（G）：按照某種次序，對圖G的每個結點訪問一次且最多一次。

7.1.2基本術語設用n表示圖中頂點的個數，用e表示圖中邊或弧的數目，并且不考慮圖中每個頂點到其自身的邊或弧。無向完全圖：有n（n-1）/2條邊（圖中每個頂點和其余n-1個頂點都有邊相連）的無向圖為無向完全圖。有向完全圖：有n（n-1）條邊（圖中每個頂點和其余n-1個頂點都有弧相連）的有向圖為有向完全圖。稀疏圖：對于有很少條邊的圖（e<nlogn）稱為稀疏圖，反之稱為稠密圖。

子圖：設有兩個圖G=（V，{E}）和圖G/=（V/，{E/}）,若V/V且E/

E，則稱圖G/為G的子圖。

圖G1和圖G2的子圖見p155的圖7.2所示。對于無向圖

G=（V，{E}），如果邊（v，v/）∈E，則稱頂點v，v/互為鄰接點，即v，v/相鄰接。邊（v，v/）依附于頂點v和v/，或者說邊（v，v/）與頂點v和v/相關聯。對于有向圖G=（V，{A}）而言，若弧<v，v/>∈A，則稱頂點v鄰接到頂點v/，頂點v/鄰接自頂點v，或者說弧<v，v/>與頂點v，v/相關聯。

鄰接點：度、入度和出度對于無向圖而言，頂點v的度是指和v相關聯的邊的數目，記作TD（v）。

對于有向圖而言，頂點v的度有出度和入度兩部分：以頂點v為弧頭的弧的數目稱為該頂點的入度，記作ID（v），以頂點v為弧尾的弧的數目稱為該頂點的出度，記作OD（v）則頂點v的度為：

TD（v）=ID（v）+OD（v）。

一般地，若圖G中有n個頂點，e條邊或弧，則圖中頂點的度與邊的關系如下：e=TD(Vi)2ni=1權與網

:

在實際應用中，有時圖的邊或弧上往往與具有一定意義的數有關，即每一條邊都有與它相關的數，稱為權，這些權可以表示從一個頂點到另一個頂點的距離或耗費等信息。我們將這種帶權的圖叫做賦權圖或網。圖例見p156的圖7.3所示。路徑與回路無向圖G=（V，{E}）中從頂點v到v/的路徑是一個頂點序列vi0，vi1，vi2，…，vin，其中（vij-1，vij）∈E，1≤j≤n。如果圖G是有向圖，則路徑也是有向的，頂點序列應滿足<vij-1，vij>∈A，1≤j≤n。

路徑長度：指路徑上經過的弧或邊的數目。

回路或環(huán)：在一個路徑中，若其第一個頂點和最后一個頂點是相同的，即v=v/，則稱該路徑為一個回路或環(huán)。簡單路徑：若表示路徑的頂點序列中的頂點各不相同，則稱這樣的路徑為簡單路徑。簡單回路：除了第一個和最后一個頂點外，其余各頂點均不重復出現的回路為簡單回路。

連通圖

連通圖：在無向圖G=（V，{E}）中，若從vi到vj有路徑相通，則稱頂點vi與vj是連通的。如果對于圖中的任意兩個頂點vi、vj∈V，vi，vj都是連通的，則稱該無向圖G為連通圖。

連通分量：無向圖中的極大連通子圖稱為該無向圖的連通分量。

強連通圖：在有向圖G=（V，{A}）中，若對于每對頂點vi、vj∈V且vi≠vj，從vi到vj和vj到vi都有路徑，則稱該有向圖為強連通圖。強連通分量：有向圖的極大強連通子圖稱作有向圖的強連通分量。圖G1和圖G3的連通分量見p157的圖7.4所示生成樹一個連通圖的生成樹是指一個極小連通子圖，它含有圖中的全部頂點，但只有足已構成一棵樹的n-1條邊。如圖p157的圖7.5所示。7.2圖的存儲結構圖的存儲結構方法有：①鄰接矩陣表示法；②鄰接表；③鄰接多重表；④十字鏈表

鄰接矩陣表示法

圖的鄰接矩陣表示法（AdjacencyMatrix）也稱作數組表示法。它采用兩個數組來表示圖：一個是用于存儲頂點信息的一維數組，另一個是用于存儲圖中頂點之間關聯關系的二維數組，這個關聯關系數組被稱為鄰接矩陣。

若G是一具有n個頂點的無權圖，G的鄰接矩陣是具有如下性質的n×n矩陣A：

A[i,j]=若<vi,vj>或（vi,vj)VR0反之G1和G2的鄰接矩陣見p158的圖7.6所示若圖G是一個有n個頂點的網，則它的鄰接矩陣是具有如下性質的n×n矩陣A：A[i,j]=Wij

若<vi,vj>或（vi,vj)VR∞反之有向網及其鄰接矩陣見p158的圖7.7所示。鄰接矩陣表示法的C語言類型描述為：#defineMAX_VERTEX_NUM10/*最多頂點個數*/#defineINFINITY32768/*最多頂點個數*/typedef

enum{DG,DN,UDG,UDN}GraphKind;/*圖的種類：DG表示有向圖,DN表示有向網,UDG表示無向圖,UDN表示無向網*/typedefcharVertexData;/*假設頂點數據為字符型*/typedef

struct

ArcNode{

AdjType

adj;/*對于無權圖，用1或0表示是否相鄰；對帶權圖，則為權值類型*/

OtherInfoinfo;}ArcNode;typedef

struct{

VertexData

vexs[MAX_VERTEX_NUM];/*頂點向量*/

ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*鄰接矩陣*/

int

vexnum,arcnum;/*圖的頂點數和弧數*/

GraphKindkind;/*圖的種類標志*/}AdjMatrix;/*（AdjacencyMatrixGraph）*/

鄰接矩陣法的特點：1.存儲空間：對于無向圖而言，它的鄰接矩陣是對稱矩陣，所以可采用壓縮存儲法（下三角），其存儲空間只需n(n-1)/2。但對于有向圖而言，因為它的弧是有方向的，它的鄰接矩陣不一定是對稱矩陣，所以需要n2個存儲空間。2.便于運算：采用鄰接矩陣表示法，便于判定圖中任意兩個頂點之間是否有邊相連，即根據A[i，j]=0或1來判斷。另外還便于求得各個頂點的度。

對于無向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個頂點的度：TD(vi)=A[i,j]j=1n對于有向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個頂點的出度，第i列元素之和就是圖中第i個頂點的入度。

OD(vi)=A[i,j]j=1nID(vi)=A[j,i]j=1n頂點i的出度：頂點i的入度：采用鄰接矩陣存儲法表示圖，很便于實現圖的一些基本操作，如FirstAdjVertex（G，v）：（1）首先，由LocateVertex（G，v）找到v在圖中的位置，即v在一維數組vexs中的序號i。

（2）二維數組arcs中第i行上第一個adj域非零的分量所在的列號j，便是v的第一個鄰接點在圖G中的位置。

（3）取出一維數組vexs[j]中的數據信息，即與頂點v鄰接的第一個鄰接點的信息。

注意：稀疏圖不適于用鄰接矩陣來存儲，因為這樣會造成存儲空間的浪費。用鄰接矩陣法創(chuàng)建有向網的算法如下：int

LocateVertex(AdjMatrix*G,VertexDatav)/*求頂點位置函數*/{intj=Error,k;

for(k=0;k<G->vexnum;k++)

if(G->vexs[k]==v) {j=k;break;}

return(j);}int

CreateDN(AdjMatrix*G)/*創(chuàng)建一個有向網*/{int

i,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=INFINITY;

for(i=0;i<G->vexnum;i++)

scanf("%c",&G->vexs[i]);/*輸入圖的頂點*/

for(k=0;k<G->arcnum;k++) {scanf("%c,%c,%d",&v1,&v2,&weight);/*輸入一條弧的兩個頂點及權值*/ i=LocateVex_M(G,v1); j=LocateVex_M(G,v2); G->arcs[i][j].adj=weight;/*建立弧*/ }

return(Ok);}分析：該算法的時間復雜度為O（n2+e×n），其中O（n2）時間耗費在對二維數組arcs的每個分量的arj域初始化賦值上。O（e×n）的時間耗費在有向網中邊權的賦值上。

鄰接表表示法鄰接表（AdjacencyList）表示法實際上是圖的一種鏈式存儲結構。

它的基本思想是只存有關聯的信息，對于圖中存在的邊信息則存儲，而對于不相鄰接的頂點則不保留信息。在鄰接表中，對圖中的每個頂點建立一個帶頭結點的邊鏈表，每個邊鏈表的頭結點又構成一個表頭結點表。這樣，一個n個頂點的圖的鄰接表表示由表頭結點表與邊表兩部分構成。（1）表頭結點表：由所有表頭結點以順序結構（向量）的形式存儲，以便可以隨機訪問任一頂點的單鏈表。表頭結點有兩部分構成，其中數據域（vexdata）用于存儲頂點的名或其它有關信息；鏈域（firstarc）用于指向鏈表中第一個頂點（即與頂點vi鄰接的第一個鄰接點）。表頭結點結構為：vexdatafirstarc（2）邊表：由表示圖中頂點間鄰接關系的n個邊鏈表組成。它由三部分組成，其中鄰接點域（adjvex）用于存放與頂點vi相鄰接的頂點在圖中的位置；鏈域（nextarc）用于指向與頂點vi相關聯的下一條邊或弧的結點；數據域（info）用于存放與邊或弧相關的信息（如賦權圖中每條邊或弧的權值等）。

adjvexinfonextarc弧結點結構為：圖例p161的圖7.9所示是圖G1、G2的鄰接表表示法鄰接表存儲結構的形式化說明如下：#defineMAX_VERTEX_NUM10/*最多頂點個數*/typedef

enum{DG,DN,UDG,UDN}GraphKind;/*圖的種類*/typedef

struct

ArcNode{int

adjvex;/*該弧指向頂點的位置*/

struct

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

OtherInfoinfo;/*與該弧相關的信息*/}ArcNode;

typedef

struct

VertexNode{

VertexDatadata;/*頂點數據*/

ArcNode*firstarc;/*指向該頂點第一條弧的指針*/}VertexNode;

typedef

struct{

VertexNode

vertex[MAX_VERTEX_NUM];

int

vexnum,arcnum;/*圖的頂點數和弧數*/

GraphKindkind;/*圖的種類標志*/}AdjList;/*基于鄰接表的圖(AdjacencyListGraph)*/

●存儲空間：對于有n個頂點，e條邊的無向圖而言，若采取鄰接表作為存儲結構，則需要n個表頭結點和2e個表結點。

●無向圖的度：在無向圖的鄰接表中，頂點vi的度恰好就是第i個邊鏈表上結點的個數。

●有向圖的度：在有向圖中，第i個邊鏈表上頂點的個數是頂點vi的出度。要想求得該頂點的入度，則必須遍歷整個鄰接表。在所有單鏈表中查找鄰接點域的值為i的結點并計數求和。由此可見，對于用鄰接表方式存儲的有向圖，求頂點的入度并不方便，因此需要有一種解決的方法－逆鄰接表法。對圖中的每一頂點vi建立一個遞鄰接表，即對每個頂點vi建立一個所有以頂點vi為弧頭的弧的表，這樣求頂點vi的入度即是計算逆鄰接表中第i個頂點的邊鏈表中結點個數。

圖G1的逆鄰接表表示法見p162的圖7.10十字鏈表十字鏈表(OrthogonalList)是有向圖的另一種鏈式存儲結構。我們也可以把它看成是將有向圖的鄰接表和逆鄰接表結合起來形成的一種鏈表。有向圖中的每一條弧對應十字鏈表中的一個弧結點，同時有向圖中的每個頂點在十字鏈表中對應有一個結點，叫做頂點結點。

這兩類結點的結構見p162的圖7.11所示。圖G1的十字鏈表表示見p163的圖7.12所示。12

∧

13∧

∧4

1∧

∧1

3

2

∧4

34∧∧1234建立一個有向圖的十字鏈表的算法如下：

voidCrtOrthList（OrthListg）/*從終端輸入n個頂點的信息和e條弧的信息，以建立一個有向圖的十字鏈表*/{scanf(“%d,%d”,&n,&e);/*鍵盤輸入圖的頂點個數和弧的個數*/for(i=0;i<n;i++){scanf(“%c”,g.vertex[i].data）；

g.vertex[i].firstin=NULL；g.vertex[i].firsout=NULL；

}for(k=0;k<e;k++){scanf(“%c,%c”,&vt,&vh);i=LocateVertex（g，vt）；j=LocateVertex（g，vh）；

p=alloc(sizeof(ArcNode));p->tailvex=i；p->headvex=j；

p->tlink=g.vertex[i].firstout；g.vertex[i].firstout=p；

p->hlink=

g.vertex[j].firstin；g.vertex[j].firstin=p；

}}/*CrtOrthList*/

十字鏈表的優(yōu)點：在十字鏈表中既能夠很容易地找到以vi為尾的弧，也能夠容易地找到以vi為頭的弧，因此對于有向圖，若采用十字鏈表作為存儲結構，則很容易求出頂點vi的度。

鄰接多重表鄰接多重表(AdjacencyMulti_list)是無向圖的另外一種存儲結構。使用鄰接多重表這種存儲結構是因為它能夠提供更為方便的邊處理信息。

鄰接多重表是指將圖中關于一條邊的信息用一個結點來表示。鄰接多重表中的邊結點結構和頂點結點結構見p164的圖7.13所示。鄰接多重表的結構類型說明如下：typedef

struct

EdgeNode{int

mark,ivex,jvex;struct

EdgeNode*ilink,*jlink;}EdgeNode;typedef

struct{

VertexDatadata;

EdgeNode*firstedge;}VertexNode;typedef

struct{

VertexNode

vertex[MAX_VERTEX_NUM];

int

vexnum,arcnum;/*圖的頂點數和弧數*/

GraphKindkind;/*圖的種類*/}AdjMultiList;/*基于圖的鄰接多重表表示法(AdjacencyMulti_list)*/圖G2的鄰接多重表見p165的圖7.14所示。7.4圖的遍歷圖的遍歷：從圖中的某個頂點出發(fā)，按某種方法對圖中的所有頂點訪問且僅訪問一次。

為了保證圖中的各頂點在遍歷過程中訪問且僅訪問一次，需要為每個頂點設一個訪問標志，用以標示圖中每個頂點是否被訪問過，訪問標志用數組visited[n]來表示。

圖的遍歷方法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索深度優(yōu)先搜索：深度優(yōu)先搜索（Depth_FirstSearch）是指按照深度方向搜索，它類似于樹的先根遍歷。深度優(yōu)先算法的基本思想是：（1）從圖中某個頂點v0出發(fā)，首先訪問v0。

（2）找出剛訪問過的頂點vi的第一個未被訪問的鄰接點，然后訪問該頂點。重復此步驟，直到當前的頂點沒有未被訪問的鄰接點為止。（3）返回前一個訪問過的頂點，找出該頂點的下一個未被訪問的鄰接點，訪問該頂點。轉2。

采用遞歸的形式說明，則深度優(yōu)先搜索連通子圖的的基本思想可表示為：

（1）訪問出發(fā)點v0。

（2）依次以v0的未被訪問的鄰接點為出發(fā)點，深度優(yōu)先搜索圖，直至圖中所有與v0有路徑相通的頂點都被訪問。若此時圖中還有頂點未被訪問，則另選圖中一個未被訪問的頂點作為起始點，重復上述深度優(yōu)先搜索過程，直至圖中所有頂點均被訪問過為止。

深度優(yōu)先搜索的過程示例見p167的7.15圖所示。其中實箭頭代表訪問方向，虛箭頭代表回溯方向，箭頭旁邊的數字代表搜索順序，A為起始頂點。8ADGBEHCFI1236710114155149131216訪問序列為：A、B、C、F、E、G、D、H、I。圖的深度優(yōu)先搜索的算法描述如下：#defineTrue1#defineFalse0#defineError–1/*出錯*/#defineOk1int

visited[MAX_VERTEX_NUM];/*訪問標志數組*/

voidTraverseGraph(Graphg)/*對圖g進行深度優(yōu)先搜索，Graph表示圖的一種存儲結構，如數組表示法或鄰接表等*/{for(vi=0;vi<g.vexnum;vi++)visited[vi]=False;/*訪問標志數組初始*/for(vi=0;vi<g.vexnum;vi++) /*調用深度遍歷連通子圖的操作*//*若圖g是連通圖，則此循環(huán)只執(zhí)行一次*/ if(！visited[vi])DepthFirstSearch(g，vi)；}/*TraverseGraph*/

深度遍歷v0所在地連通子圖算法如下：voidDepthFirstSearch（Graphg,intv0）/*深度遍歷v0所在的連通子圖*/{visit（v0）；visited[v0]=True；/*訪問頂點v0，并置訪問標志數組相應分量值*/w=FirstAdjVertex(g,v0);while(w!=-1)/*鄰接點存在*/{if(!visited[w])DepthFirstSearch(g,w);/*遞歸調用DepthFirstSearch*/w=NextAdjVertex(g,v0,w);/*找下一個鄰接點*/}}/*DepthFirstSearch*/

上述算法中對于FirstAdjVertex（g，v0）以及NextAdjVertex（g，v0，w）并沒有具體實現。因為對于圖的不同存儲方法，兩個操作的實現方法不同，時間耗費也不同。

下面的算法是在鄰接矩陣與鄰接表方式下實現上面算法的功能。1）用鄰接矩陣方式實現深度優(yōu)先搜索voidDepthFirstSearch(AdjMatrixg,intv0)/*圖g為鄰接矩陣類型AdjMatrix*/

{visit(v0);visited[v0]=True;for(vj=0;vj<n;vj++)if(!visited[vj]&&g.arcs[v0][vj].adj==1)

DepthFirstSearch(g,vj);}/*DepthFirstSearch*/

2）用鄰接表方式實現深度優(yōu)先搜索voidDepthFirstSearch(AdjListg,intv0)/*圖g為鄰接表類型AdjList*/{visit(v0)；visited[v0]=True；p=g.vertex[v0].firstarc；while(p!=NULL){if(!visited[p->adjvex])

DepthFirstSearch（g，p->adjvex）；

p=p->nextarc；

}}/*DepthFirstSearch*/

分析算法：以鄰接表作為存儲結構，查找每個頂點的鄰接點的時間復雜度為O(e)，

其中e是無向圖中的邊數或有向圖中弧數,則深度優(yōu)先搜索圖的時間復雜度為O(n+e)。

3）用非遞歸過程實現深度優(yōu)先搜索voidDepthFirstSearch(Graphg,intv0)/*從v0出發(fā)深度優(yōu)先搜索圖g*/{

InitStack(S);/*初始化空棧*/Push(S,v0)；while(!Empty(S)){v=Pop(S);if(!visited(v))/*棧中可能有重復結點*/{visit(v);visited[v]=True;}w=FirstAdj(g,v);/*求v的第一個鄰接點*/while(w!=-1){ if(!visited(w))Push(S,w);w=NextAdj(g,v,w);/*求v相對于w的下一個鄰接點*/}}}

7.3.2廣度優(yōu)先搜索廣度優(yōu)先搜索（Breadth_FirstSearch）是指按照廣度方向搜索，它類似于樹的按層次遍歷。廣度優(yōu)先搜索的基本思想是：（1）從圖中某個頂點v0出發(fā)，首先訪問v0。

（2）依次訪問v0的各個未被訪問的鄰接點。

（3）分別從這些鄰接點（端結點）出發(fā)，依次訪問它們的各個未被訪問的鄰接點（新的端結點）。

訪問時應保證：如果Vi和Vk為當前端結點，且Vi在Vk之前被訪問，則Vi的所有未被訪問的鄰接點應在Vk的所有未被訪問的鄰接點之前訪問。重復（3），直到所有端結點均沒有未被訪問的鄰接點為止。

若此時還有頂點未被訪問，則選一個未被訪問的頂點作為起始點，重復上述過程，直至所有頂點均被訪問過為止。

廣度優(yōu)先搜索過程示例見p169的圖7.16所示。其中箭頭代表搜索方向，箭頭旁邊的數字代表搜索順序，A為起始頂點。ADGBEHCFI14657823訪問序列為：A、B、E、D、C、G、F、H、I。廣度優(yōu)先搜索連通子圖的算法如下：voidBreadthFirstSearch(Graphg,intv0)/*廣度優(yōu)先搜索圖g中v0所在的連通子圖*/{visit(v0);visited[v0]=True;InitQueue(&Q);/*初始化空隊*/

EnterQueue(&Q,v0)；/*v0進隊*/while(!Empty(Q)){DeleteQueue(&Q,&v);/*隊頭元素出隊*/w=FirstAdj(g,v);/*求v的第一個鄰接點*/while(w!=-1){ if(!visited(w)){visit(w);visited[w]=True;

EnterQueue(&Q,w);}

w=NextAdj(g,v,w);/*求v相對于w的下一個鄰接點*/}}}

7.4圖的連通性問題無向圖的連通分量在對圖遍歷時，對于連通圖，無論是廣度優(yōu)先搜索還是深度優(yōu)先搜索，僅需要調用一次搜索過程，即從任一個頂點出發(fā)，便可以遍歷圖中的各個頂點。對于非連通圖，則需要多次調用搜索過程，而每次調用得到的頂點訪問序列恰為各連通分量中的頂點集。調用搜索過程的次數就是該圖連通分量的個數。例如：p171的圖7.17(a)是一個非連通圖，按照它的鄰接表進行深度優(yōu)先搜索遍歷，三次調用深度優(yōu)先搜索（DepthFirstSearch）過程得到的訪問頂點序列為：1，2，4，3，95，6，78，10因此有三個連通分量。如p171的圖7.17(c).最小生成樹在一個連通網的所有生成樹中，各邊的代價之和最小的那棵生成樹稱為該連通網的最小代價生成樹（MinimumCostSpanningTree），簡稱為最小生成樹。

最小生成樹的重要性質如下：設N=(V,{E})是一連通網，U是頂點集V的一個非空子集。若（u,v）是一條具有最小權值的邊，其中u∈U，v∈V-U，則存在一棵包含邊（u,v）的最小生成樹。

用反證法來證明這個最小生成樹（MST）的性質：假設不存在這樣一棵包含邊（u,v）的最小生成樹。任取一棵最小生成樹T，將（u,v）加入T中。根據樹的性質，此時T中必形成一個包含（u,v）的回路，且回路中必有一條邊（u’,v’）的權值大于或等于（u,v）的權值。刪除（u,v），則得到一棵代價小于等于T的生成樹T’，且T’為一棵包含邊（u,v）的最小生成樹。這與假設矛盾。

一個連通網的最小生成樹算法：普里姆算法假設N=(V,{E})是連通網，TE為最小生成樹中邊的集合。（1）初始U={u0}(u0∈V),TE=φ；

（2）在所有u∈U,v∈V-U的邊中選一條代價最小的邊（u0，v0）并入集合TE，同時將v0并入U；

（3）重復（2），直到U=V為止。

此時，TE中必含有n-1條邊，則T=（V，{TE}）為N的最小生成樹。

普里姆算法是逐步增加U中的頂點，可稱為“加點法”注意：選擇最小邊時，可能有多條同樣權值的邊可供選擇，此時任選其一。為了實現這個算法需設一個輔助數組closedge[]，以記錄從U道V-U具有最小代價的邊。對每個頂點v∈V-U，在輔助數組中存在一個分量closedge[v]，它包括兩個域vex和lowcost，其中l(wèi)owcost存儲該邊上的權，顯然有

closedge[v].lowcoast=Min({cost(u,v)|u∈U})普里姆算法可描述為：struct{VertexData

adjvex;

int

lowcost;}closedge[MAX_VERTEX_NUM];/*求最小生成樹時的輔助數組*/MiniSpanTree_Prim(AdjMatrix

gn,VertexData

u)/*從頂點u出發(fā)，按普里姆算法構造連通網gn

的最小生成樹，并輸出生成樹的每條邊*/{k=LocateVertex(gn,u);closedge[k].lowcost=0;/*初始化，U={u}*/for(i=0;i<gn.vexnum;i++)if(i!=k)/*對V-U中的頂點i，初始化closedge[i]*/{closedge[i].adjvex=u;closedge[i].lowcost=gn.arcs[k][i].adj;}for(e=1;e<=gn.vexnum-1;e++)/*找n-1條邊(n=gn.vexnum)*/{k0=Minium(closedge);/*closedge[k0]中存有當前最小邊（u0,v0）的信息*/u0=closedge[k0].adjvex;/*u0∈U*/v0=gn.vexs[k0]/*v0∈V-U*/printf(u0,v0);/*輸出生成樹的當前最小邊（u0,v0）*/closedge[k0].lowcost=0;/*將頂點v0納入U集合*/for(i=0;i<vexnum;i++)/*在頂點v0并入U之后，更新closedge[i]*/if(gn.arcs[k0][i].adj<closedge[i].lowcost){closedge[i].lowcost=gn.arcs[k0][i].adj;

closedge[i].adjvex=v0;}}}

P173的圖7.18(a)是一個連通網，由普里姆算法構造最小生成樹的過程見圖7.18(b)~(f)所示。算法中各參量的變化見p173的表7－1。2.克魯斯卡爾算法假設N=(V,{E})是連通網，將N中的邊按權值從小到大的順序排列；（1）將n個頂點看成n個集合；

（2）按權值由小到大的順序選擇邊，所選邊應滿足兩個頂點不在同一個頂點集合內，將該邊放到生成樹邊的集合中。同時將該邊的兩個頂點所在的頂點集合合并；（3）重復（2），直到所有的頂點都在同一個頂點集合內?？唆斔箍査惴ㄊ侵鸩皆黾由蓸涞倪?，故稱為“加邊法”以p174的連通圖7.19(a)為例，說明克魯斯卡爾算法的執(zhí)行過程。7.5有向無環(huán)圖的應用拓撲排序（TopologicalSort）

AOV-網：用頂點表示活動，用弧表示活動間的優(yōu)先關系的有向無環(huán)圖，稱為頂點表示活動的網（ActivityOnVertexNetwork），簡稱為AOV-網。

如p175的表7-2課程關系，用頂點表示課程，弧表示先決條件，則表7－2可用一個有向無環(huán)圖表示。見圖p175的圖7.21。拓撲序列：在有向圖G=（V，{E}）中，

V中頂點的線性序列（vi1,,vi1,,vi3,…，vin）稱為拓撲序列。此序列必須滿足：對序列中任意兩個頂點vi、vj，在G中有一條從vi到vj的路徑，則在序列中vi必排在vj之前。

如p175的圖7.21的一個拓撲序列為：C1,C2,C3,C4,C5,C8,C9,C7,C6。

AOV-網的特性如下：

若vi為vj的先行活動，vj為vk的先行活動，則vi必為vk的先行活動，即先行關系具有可傳遞性。AOV-網的拓撲序列不是唯一的。如p175的圖7.21的另一個拓撲序列為：C1,C2,C3,C8,C4,C5,C9,C7,C6。

求拓撲排序的基本思想：（1）從有向圖中選一個無前驅的頂點輸出；（2）將此頂點和以它為起點的弧刪除；（3）重復（1）、（2），直到不存在無前驅的頂點；（4）若此時輸出的頂點數小于有向圖中的頂點數，則說明有向圖中存在回路，否則輸出的頂點的順序即為一個拓撲序列。

例如p176的圖7.22所示的AOV－網，其拓撲序列為：v1,v6,v4,v3,v2,v5或v1,v3,v2,v6,v4,v5對于有向圖的不同存儲形式，有不同實現的拓撲排序算法。1）基于鄰接矩陣表示的存儲結構A為有向圖G的鄰接矩陣，則有（1）找G中無前驅的頂點—在A中找到值全為0的列；（2）刪除以i為起點的所有弧—將矩陣中i對應的行全部置為0。

算法步驟為：（1）取1作為第一新序號；（2）找一個未新編號的、值全為0的列j，若找到則轉（3）；否則，若所有的列全部都編過號，拓撲排序結束；若有列未曾被編號，則該圖中有回路；（3）輸出列號對應的頂點j，把新序號賦給所找到的列；（4）將矩陣中j對應的行全部置為0;（5）新序號加1，轉（2）；

2）基于鄰接表的存儲結構

入度為零的頂點即沒有前趨的頂點，因此我們可以附設一個存放各頂點入度的數組indegree[]，于是有

（1）找G中無前驅的頂點——查找indegree[i]為零的頂點vi；（2）刪除以i為起點的所有弧——對鏈在頂點i后面的所有鄰接頂點k，將對應的indegree[k]減1。

為了避免重復檢測入度為零的頂點，可以再設置一個輔助棧，若某一頂點的入度減為0，則將它入棧。每當輸出某一頂點時，便將它從棧中刪除。

拓撲排序的實現算法int

TopoSort(AdjListG){StackS;int

indegree[MAX_VERTEX_NUM];inti,count,k;

ArcNode*p;

FindID(G,indegree);/*求各頂點入度*/

InitStack(&S);/*初始化輔助棧*/

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

if(indegree[i]==0)Push(&S,i);/*將入度為0的頂點入棧*/count=0;

while(!StackEmpty(S)){Pop(&S,&i);

printf("%c",G.vertex[i].data); count++;/*輸出i號頂點并計數*/p=G.vertexes[i].firstarc;

while(p!=NULL) {k=p->adjvex;

indegree[k]--;/*i號頂點的每個鄰接點的入度減1*/

if(indegree[k]==0)Push(&S,k);/*若入度減為0，則入棧*/ p=p->nextarc; } }/*while*/if(count<G.vexnum)return(Error);/*該有向圖含有回路*/elsereturn(Ok);}求各頂點入度的函數voidFindID(AdjListG,int

indegree[MAX_VERTEX_NUM])/*求各頂點的入度*/{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; }}/*for*/}P176的圖7.22所示的AOV-網的鄰接表如圖p178的圖7.23所示，用拓撲排序算法求出的拓撲序列為：v6，v1，v3，v2，v4，v5。

算法的時間復雜度分析：若有向無環(huán)圖有n個頂點和e條弧，則在拓撲排序的算法中，for循環(huán)需要執(zhí)行n次，時間復雜度為O(n)；對于while循環(huán)，由于每一頂點必定進一次棧，出一次棧，其時間復雜度為O(e)；故該算法的時間復雜度為O(n+e)。

關鍵路徑AOE-網：在有向圖中，用頂點表示事件，用弧表示活動，弧的權值表示活動所需要的時間。我們把用這種方法構造的有向無環(huán)圖叫做邊表示活動的網（ActivityOnEdgeNetwork）,簡稱AOE-網。

AOE-網用在工程計劃和管理中，人們最關心的是：哪些活動是影響工程進度的關鍵活動？至少需要多長時間能完成整個工程？源點：存在唯一的、入度為零的頂點，叫源點。匯點：存在唯一的、出度為零的頂點，叫匯點。關鍵路徑：從源點到匯點的最長路徑的長度即為完成整個工程任務所需的時間，該路徑叫做關鍵路徑。關鍵活動：關鍵路徑上的活動叫做關鍵活動。

在AOE-網中的基本概念：例如p179的圖7.24所示的AOE-網。V0為源點，表示整個工程可以開始，v8為匯點，表示整個工程結束。幾個重要的定義：事件vi的最早發(fā)生時間ve(i)：從源點到頂點vi的最長路徑的長度，叫做事件vi的最早發(fā)生時間。求ve(i)時可從源點開始，按拓撲順序向匯點遞推：ve(0)=0；

ve(i)=Max{ve(k)＋dut(<k,i>)}<k,i>∈T,1≤i≤n-1;其中，T為所有以i為頭的弧<k,i>的集合，dut（<k,i>）表示與弧<k,i>對應的活動的持續(xù)時間。事件vi的最晚發(fā)生時間vl(i)：在保證匯點按其最早發(fā)生時間發(fā)生這一前提下，事件vi的最晚發(fā)生時間。在求出ve(i)的基礎上，可從匯點開始，按逆拓撲順序向源點遞推，求出vl(i)：vl(n-1)=ve(n-1)；

vl(i)=Min{vl(k)＋dut(<i,k>)}<i,k>∈S,0≤i≤n-2;其中，S為所有以i為尾的弧<i,k>的集合，dut（<i,k>）表示與弧<i,k>對應的活動的持續(xù)時間。

活動ai的最早開始時間e(i)：如果活動ai對應的弧為<j,k>，則e(i)等于從源點到頂點j的最長路徑的長度，即：e(i)=ve(j)

活動ai的最晚開始時間l(i)：如果活動ai對應的弧為<j,k>，其持續(xù)時間為dut（<j,k>）則有：l(i)=vl(k)-dut（<j,k>）

活動ai的松弛時間（時間余量）：ai的最晚開始時間與ai的最早開始時間之差：l(i)-e(i)。顯然，松弛時間（時間余量）為0的活動為關鍵活動。

求關鍵路徑的基本步驟：（1）對圖中頂點進行拓撲排序，在排序過程中按拓撲序列求出每個事件的最早發(fā)生時間ve(i)；（2）按逆拓撲序列求每個事件的最晚發(fā)生時間vl(i)；（3）求出每個活動ai的最早開始時間e(i)和最晚發(fā)生時間l(i)；4)找出e(i)=l(i)的活動ai，即為關鍵活動。

修改后的拓撲排序算法int

ve[MAX_VERTEX_NUM];/*每個頂點的最早發(fā)生時間*/int

TopoOrder(AdjList

G,Stack*T)/*G為有向網，T為返回拓撲序列的棧，S為存放入度為0的頂點的棧*/{int

count,i,j,k;ArcNode*p;int

indegree[MAX_VERTEX_NUM];/*各頂點入度數組*/StackS;

InitStack(T);InitStack(&S);/*初始化棧T,S*/

FindID(G,indegree);/*求各個頂點的入度*/

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ā)生時間*/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);/*若頂點的入度減為0，則入棧*/

if(ve[j]+p->weight>ve[k])ve[k]=ve[j]+p->weight; p=p->nextarc; }/*while*/}/*while*/

if(count<G.vexnum)return(Error);elsereturn(Ok);}求關鍵路徑的實現算法int

CriticalPath(AdjListG){ArcNode*p;int

i,j,k,dut,ei,li;chartag;int

vl[MAX_VERTEX_NUM];/*每個頂點的最遲發(fā)生時間*/StackT;

if(!TopoOrder(G,&T))return(Error);

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

vl[i]=ve[i];/*初始化頂點事件的最遲發(fā)生時間*/

while(!StackEmpty(T))/*按逆拓撲順序求各頂點的vl值*/ {Pop(&T,&j); p=G.vertex[j].firstarc; while(p!=NULL) {k=p->adjvex;dut=p->weight;

if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;p=p->nextarc; }/*while*/ }/*while*/

for(j=0;j<G.vexnum;j++)/*求ei,li和關鍵活動*/ {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);/*輸出關鍵活動*/ p=p->nextarc; }/*while*/ }/*for*/return(Ok);}/*CriticalPath*/該算法的時間復雜度為O(n+e)。用該算法求p179的圖7.24中AOE-網的關鍵路徑，結果如p181的圖7.25。7.6最短路徑求某一頂點到其它各頂點的最短路徑設有帶權的有向圖D=(V,{E})，D中的邊權為

W(e)。已知源點為v0，求v0到其它各頂點的最短路徑。

如p184的圖7.26所示的帶權有向圖，其源點v0到其它各頂點的最短路徑如p184的表7－3所示。用迪杰斯特拉（Dijkstra）求最短路徑算法基本思想是：按路徑長度遞增的順序，逐個產生各最短路徑。

首先引進輔助向量dist[]，它的每一個分量dist[i]表示已經找到的且從開始點v0到每一個終點vi的當前最短路徑的長度。它的初態(tài)為：如果從v0到vi有弧，則dist[i]為弧的權值；否則dist[i]為∞。其中，長度為dist[j]=Min{dist[i]|vi∈V}

的路徑是從v0出發(fā)的長度最短的一條最短路徑，此路徑為（v0，vj）。

當我們按長度遞增的順序來產生各個最短路徑時，設S為已經求得的最短路徑的終點集合。我們可以證明：下一條最短路徑或者是?。╲0，vx），或者是中間經過S中的某些頂點，而后到達vx的路徑。一般情況下，下一條長度最短的最短路徑的長度必是dist[j]=Min{dist[i]|vi∈V－S}其中，dist[i]或者是弧（v0，vi）上的權值，或者是dist[k]（vk∈S）和?。╲k，vi）上的權值之和。

我們將圖中的頂點分為兩組：S—已求出的最短路徑的終點集合(開始為{v0})。V-S—尚未求出最短路徑的頂點集合(開始為V－{v0}的全部結點)。按最短路徑長度的遞增順序逐個將第二組的頂點加入到第一組中。

迪杰斯特拉算法的主要步驟：（1）g為用鄰接矩陣表示的帶權圖。

S←—{v0}，dist[i]=g.arcs[v0][vi]；將v0到其余頂點的路徑長度初始化為權值；

（2）選擇vk，使得dist[vk]=min(dist[i]|vi∈V－S)

vk為目前求得的下一條從v0出發(fā)的最短路徑的終點。（3）修改從v0出發(fā)到集合V－S上任一頂點vi的最短路徑的長度。如果

dist[k]+g.arcs[k][i]<dist[i]則將dist[i]修改為：

dist[k]+g.arcs[k][i]（4)重復(2)、(3)n-1次，即可按最短路徑長度的遞增順序，逐個求出v0到圖中其它每個頂點的最短路徑。求圖的最短路徑的迪杰斯特拉算法typedef

SeqList

VertexSet;ShortestPath_DJS(AdjMatrixg,intv0,WeightType

dist[MAX_VERTEX_NUM],VertexSet

path[MAX_VERTEX_NUM])/*path[i]中存放頂點i的當前最短路徑。dist[i]中存放頂點i的當前最短路徑長度*/{VertexSets;/*s為已找到最短路徑的終點集合*/for(i=0;i<g.vexnum;i++)/*初始化dist[i]和path

[i]*/{InitList(&path[i]);dist[i]=g.arcs[v0][i];if(dist[i]<MAX){AddTail(&path[i],g.vexs[v0]);/*AddTail為表尾添加操作*/AddTail(&path[i],g.vexs[i]);}}

InitList(&s);AddTail(&s,g.vexs[v0]);