數(shù)據(jù)結(jié)構(gòu)第三版李春葆第8章 圖

8.1圖的基本概念第8章圖8.2圖的存儲結(jié)構(gòu)8.3圖的遍歷8.4生成樹和最小生成樹8.5最短路徑8.6拓?fù)渑判虮菊滦〗Y(jié)8.7AOE網(wǎng)與關(guān)鍵路徑8.1圖的基本概念8.1.1圖的定義

圖(Graph)G由兩個集合V(Vertex)和E(Edge)組成,記為G=(V,E),其中V是頂點的有限集合,記為V(G),E是連接V中兩個不同頂點(頂點對)的邊的有限集合,記為E(G)。和離散數(shù)學(xué)中采用的方法相同，通過頂點集和邊集來表示一個圖的邏輯結(jié)構(gòu)，實際上就是二元組表示。在圖G中,如果代表邊的頂點對是無序的,則稱G為無向圖,無向圖中代表邊的無序頂點對通常用圓括號括起來,用以表示一條無向邊。如果表示邊的頂點對是有序的,則稱G為有向圖,在有向圖中代表邊的頂點對通常用尖括號括起來。8.1.2圖的基本術(shù)語

1.端點和鄰接點在一個無向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個端點,并稱它們互為鄰接點。在一個有向圖中,若存在一條邊<vi,vj>,則稱此邊是頂點vi的一條出邊,同時也是頂點vj的一條入邊；稱vi和vj分別為此邊的起始端點(簡稱為起點)和終止端點(簡稱終點)；稱vi和vj互為鄰接點。13024(a)13024(b)

2.頂點的度、入度和出度在無向圖中,頂點所具有的邊的數(shù)目稱為該頂點的度。在有向圖中,以頂點vi為終點的入邊的數(shù)目,稱為該頂點的入度。以頂點vi為始點的出邊的數(shù)目,稱為該頂點的出度。一個頂點的入度與出度的和為該頂點的度。若一個圖中有n個頂點和e條邊,每個頂點的度為di(1≤i≤n),則有：13024(a)13024(b)

3.完全圖若無向圖中的每兩個頂點之間都存在著一條邊,有向圖中的每兩個頂點之間都存在著方向相反的兩條邊,則稱此圖為完全圖。顯然,完全無向圖包含有條邊,完全有向圖包含有n(n-1)條邊。例如,圖(a)所示的圖是一個具有4個頂點的完全無向圖,共有6條邊。圖(b)所示的圖是一個具有4個頂點的完全有向圖,共有12條邊。

(b)10231023(a)

4.稠密圖、稀疏圖當(dāng)一個圖接近完全圖時,則稱為稠密圖。相反,當(dāng)一個圖含有較少的邊數(shù)(即當(dāng)e<<n(n-1))時,則稱為稀疏圖。

5.子圖設(shè)有兩個圖G=(V,E)和G’=(V’,E’),若V’是V的子集,即V’V,且E’是E的子集,即E’E,則稱G’是G的子圖。例如圖(b)是圖(a)的子圖,而圖(c)不是圖(a)的子圖。(a)1302413024(b)13024(c)6.路徑和路徑長度在一個圖G=(V,E)中,從頂點vi到頂點vj的一條路徑是一個頂點序列(vi,vi1,vi2,…,vim,vj),若此圖G是無向圖,則邊(vi,vi1),(vi1,vi2),…,(vim-1,vim),(vim,vj)屬于E(G)；若此圖是有向圖,則<vi,vi1>,<vi1,vi2>,…,<vim-1,vim>,<vim,vj>屬于E(G)。

路徑長度是指一條路徑上經(jīng)過的邊的數(shù)目。若一條路徑上除開始點和結(jié)束點可以相同外,其余頂點均不相同,則稱此路徑為簡單路徑。例如,有圖中,(v0,v2,v1)就是一條簡單路徑,其長度為2。1023

7.回路或環(huán)若一條路徑上的開始點與結(jié)束點為同一個頂點,則此路徑被稱為回路或環(huán)。開始點與結(jié)束點相同的簡單路徑被稱為簡單回路或簡單環(huán)。例如,右圖中,(v0,v2,v1,v0)就是一條簡單回路,其長度為3。1023

8.連通、連通圖和連通分量在無向圖G中,若從頂點vi到頂點vj有路徑,則稱vi和vj是連通的。若圖G中任意兩個頂點都連通,則稱G為連通圖,否則稱為非連通圖。無向圖G中的極大連通子圖稱為G的連通分量。顯然,任何連通圖的連通分量只有一個,即本身,而非連通圖有多個連通分量。1023102(b)(a)3

9.強(qiáng)連通圖和強(qiáng)連通分量在有向圖G中,若從頂點vi到頂點vj有路徑,則稱從vi到vj是連通的。若圖G中的任意兩個頂點vi和vj都連通,即從vi到vj和從vj到vi都存在路徑,則稱圖G是強(qiáng)連通圖。例如,右邊兩個圖都是強(qiáng)連通圖。有向圖G中的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。顯然,強(qiáng)連通圖只有一個強(qiáng)連通分量,即本身,非強(qiáng)連通圖有多個強(qiáng)連通分量。1023102(b)(a)10.權(quán)和網(wǎng)圖中每一條邊都可以附有一個對應(yīng)的數(shù)值,這種與邊相關(guān)的數(shù)值稱為權(quán)。權(quán)可以表示從一個頂點到另一個頂點的距離或花費的代價。邊上帶有權(quán)的圖稱為帶權(quán)圖,也稱作網(wǎng)。

例8.1

有n個頂點的有向強(qiáng)連通圖最多需要多少條邊？最少需要多少條邊？

答：有n個頂點的有向強(qiáng)連通圖最多有n(n-1)條邊(構(gòu)成一個有向完全圖的情況)；最少有n條邊(n個頂點依次首尾相接構(gòu)成一個環(huán)的情況)。

8.2圖的存儲結(jié)構(gòu)

8.2.1鄰接矩陣存儲方法

鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n(n＞0)個頂點的圖,頂點的順序依次為(v0,v1,…,vn-1),則G的鄰接矩陣A是n階方陣,其定義如下：

(1)如果G是無向圖,則：

A[i][j]=1:若(vi,vj)∈E(G)0:其他

(2)如果G是有向圖,則：

A[i][j]=1:若<vi,vj>∈E(G)0:其他(3)如果G是帶權(quán)無向圖,則：

A[i][j]=wij:若vi≠vj且(vi,vj)∈E(G)∞:其他(4)如果G是帶權(quán)有向圖,則：

A[i][j]=wij:若vi≠vj且<vi,vj>∈E(G)∞:其他思考題：對于有n個頂點e條邊的無向圖，鄰接矩陣表示時有多少個元素，多少個非0元素？對于有n個頂點e條邊的有向圖，鄰接矩陣表示時有多少個元素，多少個非0元素？鄰接矩陣的特點如下：

(1)圖的鄰接矩陣表示是唯一的。

(2)無向圖的鄰接矩陣一定是一個對稱矩陣。因此,按照壓縮存儲的思想,在具體存放鄰接矩陣時只需存放上(或下)三角形陣的元素即可。

(3)不帶權(quán)的有向圖的鄰接矩陣一般來說是一個稀疏矩陣,因此,當(dāng)圖的頂點較多時,可以采用三元組表的方法存儲鄰接矩陣。

(4)對于無向圖,鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個數(shù)正好是第i個頂點vi的度。

(5)對于有向圖,鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個數(shù)正好是第i個頂點vi的出度(或入度)。

(6)用鄰接矩陣方法存儲圖,很容易確定圖中任意兩個頂點之間是否有邊相連。但是,要確定圖中有多少條邊,則必須按行、按列對每個元素進(jìn)行檢測,所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。鄰接矩陣的數(shù)據(jù)類型定義如下：#defineMAXV<最大頂點個數(shù)> typedef

struct

{intno; //頂點編號

InfoTypeinfo; //頂點其他信息}VertexType; //頂點類型typedef

struct //圖的定義{intedges[MAXV][MAXV]; //鄰接矩陣

int

n,e; //頂點數(shù),弧數(shù)

VertexType

vexs[MAXV]; //存放頂點信息}MGraph;8.2.2鄰接表存儲方法圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲方法。在鄰接表中,對圖中每個頂點建立一個單鏈表,第i個單鏈表中的結(jié)點表示依附于頂點vi的邊(對有向圖是以頂點vi為尾的弧)。每個單鏈表上附設(shè)一個表頭結(jié)點。表結(jié)點表頭結(jié)點advexnextarcinfodatafirstarc

其中,表結(jié)點由三個域組成,adjvex指示與頂點vi鄰接的點在圖中的位置,nextarc指示下一條邊或弧的結(jié)點,info存儲與邊或弧相關(guān)的信息,如權(quán)值等。表頭結(jié)點由兩個域組成,data存儲頂點vi的名稱或其他信息,firstarc指向鏈表中第一個結(jié)點。思考題：對于有n個頂點e條邊的無向圖，鄰接表表示時有多少個表頭結(jié)點，多少個表結(jié)點？對于有n個頂點e條邊的有向圖，鄰接表表示時有多少個表頭結(jié)點，多少個表結(jié)點？鄰接表的特點如下：

(1)鄰接表表示不唯一。這是因為在每個頂點對應(yīng)的單鏈表中,各邊結(jié)點的鏈接次序可以是任意的,取決于建立鄰接表的算法以及邊的輸入次序。

(2)對于有n個頂點和e條邊的無向圖,其鄰接表有n個頂點結(jié)點和2e個邊結(jié)點。顯然,在總的邊數(shù)小于n(n-1)/2的情況下,鄰接表比鄰接矩陣要節(jié)省空間。

(3)對于無向圖,鄰接表的頂點vi對應(yīng)的第i個鏈表的邊結(jié)點數(shù)目正好是頂點vi的度。

(4)對于有向圖,鄰接表的頂點vi對應(yīng)的第i個鏈表的邊結(jié)點數(shù)目僅僅是vi的出度。其入度為鄰接表中所有adjvex域值為i的邊結(jié)點數(shù)目。鄰接表存儲結(jié)構(gòu)的定義如下：typedef

struct

ANode //弧的結(jié)點結(jié)構(gòu)類型{int

adjvex; //該弧的終點位置

struct

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

InfoTypeinfo; //該弧的相關(guān)信息}ArcNode;typedef

struct

Vnode //鄰接表頭結(jié)點的類型{Vertexdata; //頂點信息

ArcNode*firstarc; //指向第一條弧}VNode;typedef

VNode

AdjList[MAXV];//AdjList是鄰接表類型typedef

struct

{AdjList

adjlist; //鄰接表

intn,e; //圖中頂點數(shù)n和邊數(shù)e}ALGraph; //圖的類型

例8.2

給定一個具有n個結(jié)點的無向圖的鄰接矩陣和鄰接表。

(1)設(shè)計一個將鄰接矩陣轉(zhuǎn)換為鄰接表的算法；

(2)設(shè)計一個將鄰接表轉(zhuǎn)換為鄰接矩陣的算法；

(3)分析上述兩個算法的時間復(fù)雜度。解：(1)在鄰接矩陣上查找值不為0的元素,找到這樣的元素后創(chuàng)建一個表結(jié)點并在鄰接表對應(yīng)的單鏈表中采用前插法插入該結(jié)點。算法如下：voidMatToList(MGraph

g,ALGraph*&G)//將鄰接矩陣g轉(zhuǎn)換成鄰接表G{inti,j,n=g.vexnum;ArcNode*p; //n為頂點數(shù)

G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)//給所有頭結(jié)點的指針域置初值

G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++) //檢查鄰接矩陣中每個元素

for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0) {p=(ArcNode*)malloc(sizeof(ArcNode));//創(chuàng)建結(jié)點*p p->adjvex=j; p->nextarc=G->adjlist[i].firstarc;//將*p鏈到鏈表后

G->adjlist[i].firstarc=p; }G->n=n;G->e=g.e;}

(2)在鄰接表上查找相鄰結(jié)點,找到后修改相應(yīng)鄰接矩陣元素的值。算法如下：

voidListToMat(ALGraph*G,MGraph&g){inti,j,n=G->n;ArcNode*p;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL) {g.edges[i][p->adjvex]=1; p=p->nextarc; }}

g.n=n;g.e=G->e;}

(3)算法1的時間復(fù)雜度均為O(n2)。算法2的時間復(fù)雜度為O(n+e),其中e為圖的邊數(shù)。8.3圖的遍歷8.3.1圖的遍歷的概念從給定圖中任意指定的頂點(稱為初始點)出發(fā),按照某種搜索方法沿著圖的邊訪問圖中的所有頂點,使每個頂點僅被訪問一次,這個過程稱為圖的遍歷。如果給定圖是連通的無向圖或者是強(qiáng)連通的有向圖,則遍歷過程一次就能完成,并可按訪問的先后順序得到由該圖所有頂點組成的一個序列。根據(jù)搜索方法的不同,圖的遍歷方法有兩種：一種叫做深度優(yōu)先搜索法(DFS)；另一種叫做廣度優(yōu)先搜索法(BFS)。深度優(yōu)先搜索遍歷的過程是：（1）從圖中某個初始頂點v出發(fā),首先訪問初始頂點v。（2）選擇一個與頂點v相鄰且沒被訪問過的頂點w為初始頂點,再從w出發(fā)進(jìn)行深度優(yōu)先搜索,直到圖中與當(dāng)前頂點v鄰接的所有頂點都被訪問過為止。以鄰接表為存儲結(jié)構(gòu)的深度優(yōu)先搜索遍歷算法如下(其中,v是初始頂點編號,visited[]是一個全局?jǐn)?shù)組,初始時所有元素均為0表示所有頂點尚未訪問過)：8.3.2深度優(yōu)先搜索遍歷體現(xiàn)出先進(jìn)先出的特點：用?；蜻f歸方式實現(xiàn)。voidDFS(ALGraph*G,intv){ArcNode*p;intw;

visited[v]=1; //置已訪問標(biāo)記

printf("%d",v); //輸出被訪問頂點的編號

p=G->adjlist[v].firstarc; //p指向頂點v的第一條弧的弧頭結(jié)點

while(p!=NULL){w=p->adjvex; if(visited[w]==0)

DFS(G,w); //若w頂點未訪問,遞歸訪問它

p=p->nextarc; //p指向頂點v的下一條弧的弧頭結(jié)點

}}思考題：為什么visited數(shù)組需要設(shè)置為全局變量？DFS序列：21034思考題：用棧求解迷宮問題，有DFS算法有什么關(guān)聯(lián)？廣度優(yōu)先搜索遍歷的過程是：（1）訪問初始點v,接著訪問v的所有未被訪問過的鄰接點v1,v2,…,vt。（2）按照v1,v2,…,vt的次序,訪問每一個頂點的所有未被訪問過的鄰接點。（3）依次類推,直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。體現(xiàn)先進(jìn)先出的特點，用隊列實現(xiàn)。以鄰接表為存儲結(jié)構(gòu),用廣度優(yōu)先搜索遍歷圖時,需要使用一個隊列,以類似于按層次遍歷二叉樹遍歷圖。對應(yīng)的算法如下(其中,v是初始頂點編號)：8.3.3廣度優(yōu)先搜索遍歷voidBFS(ALGraph*G,intv){ArcNode*p;intw,i;

intqueue[MAXV],front=0,rear=0; //定義循環(huán)隊列

intvisited[MAXV];//定義存放結(jié)點的訪問標(biāo)志的數(shù)組

for(i=0;i<G->n;i++)visited[i]=0;//訪問標(biāo)志數(shù)組初始化

printf("%2d",v); //輸出被訪問頂點的編號

visited[v]=1; //置已訪問標(biāo)記

rear=(rear+1)%MAXV;

queue[rear]=v; //v進(jìn)隊思考題：為什么visited數(shù)組不需要設(shè)置為全局變量？

while(front!=rear) //若隊列不空時循環(huán)

{front=(front+1)%MAXV; w=queue[front]; //出隊并賦給w p=G->adjlist[w].firstarc; //找w的第一個的鄰接點

while(p!=NULL) { if(visited[p->adjvex]==0) {printf(“%2d”,p->adjvex);//訪問之

visited[p->adjvex]=1; rear=(rear+1)%MAXV; //該頂點進(jìn)隊

queue[rear]=p->adjvex;}p=p->nextarc; //找下一個鄰接頂點

} }

printf("\n");}例如,以上圖的鄰接表為例調(diào)用BFS()函數(shù),假設(shè)初始頂點編號v=2,給出調(diào)用BFS()的執(zhí)行過程。BFS序列：21340思考題：用隊列求解迷宮問題，有BFS算法有什么關(guān)聯(lián)？8.3.4非連通圖的遍歷對于無向圖來說,若無向圖是連通圖,則一次遍歷能夠訪問到圖中的所有頂點；但若無向圖是非連通圖,則只能訪問到初始點所在連通分量中的所有頂點,其他連通分量中的頂點是不可能訪問到的。為此需要從其他每個連通分量中選擇初始點,分別進(jìn)行遍歷,才能夠訪問到圖中的所有頂點；對于有向圖來說,若從初始點到圖中的每個頂點都有路徑,則能夠訪問到圖中的所有頂點；否則不能訪問到所有頂點,為此同樣需要再選初始點,繼續(xù)進(jìn)行遍歷,直到圖中的所有頂點都被訪問過為止。采用深度優(yōu)先搜索遍歷非連通無向圖的算法如下：DFS1(ALGraph*G){

inti;for(i=0;i<G->n;i++)//遍歷所有未訪問過的頂點

if(visited[i]==0)

DFS(G,i);}采用廣度優(yōu)先搜索遍歷非連通無向圖的算法如下：BFS1(ALGraph*G){inti;for(i=0;i<G->n;i++)//遍歷所有未訪問過的頂點

if(visited[i]==0)

BFS(G,i);}8.3.5圖遍歷的應(yīng)用

例8.3

假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，判斷無向圖G是否連通。若連通則返回1；否則返回0。

解：采用遍歷方式判斷無向圖G是否連通。這里用深度優(yōu)先遍歷方法，先給visited[]數(shù)組（為全局變量）置初值0，然后從0頂點開始遍歷該圖。在一次遍歷之后，若所有頂點i的visited[i]均為1，則該圖是連通的；否則不連通。對應(yīng)的算法如下：int

Connect(ALGraph*G)//判斷無向圖G的連通性{int

i,flag=1;for(i=0;i<G->n;i++) //visited數(shù)組置初值

visited[i]=0;DFS(G,0);

//調(diào)用DSF算法,從頂點0開始深度優(yōu)先遍歷

for(i=0;i<G->n;i++)if(visited[i]==0){flag=0; break; }returnflag;}

例8.4

假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖G中從頂點u到v的長度為l的所有簡單路徑。

解：所謂簡單路徑是指路徑上的頂點不重復(fù)。利用回溯的深度優(yōu)先搜索方法。從頂點u開始，進(jìn)行深度優(yōu)先搜索，在搜索過程中，需要把當(dāng)前的搜索線路記錄下來。為此設(shè)立一個數(shù)組path保存走過的路徑，用d記錄走過的路徑長度。若當(dāng)前掃描到的結(jié)點u等于v且路徑長度為l時，表示找到了一條路徑，則輸出路徑path。對應(yīng)的算法如下：voidPathAll(ALGraph*G,int

u,int

v,int

l,int

path[],intd)//d是到當(dāng)前為止已走過的路徑長度，調(diào)用時初值為-1{

int

m,i;ArcNode*p;

visited[u]=1;d++; //路徑長度增1

path[d]=u; //將當(dāng)前頂點添加到路徑中

if(u==v&&d==l) //輸出一條路徑

{printf("");for(i=0;i<=d;i++)printf("%d",path[i]);

printf("\n");}p=G->adjlist[u].firstarc;//p指向u的第一條弧的弧頭結(jié)點

while(p!=NULL){m=p->adjvex; //m為u的鄰接頂點

if(visited[m]==0) //若頂點未標(biāo)記訪問,則遞歸訪問之

PathAll(G,m,v,l,path,d); p=p->nextarc //找u的下一個鄰接頂點

}

visited[u]=0;

//恢復(fù)環(huán)境}voidmain(){int

path[MAXV],u=1,v=4,d=3,i,j;

MGraphg;

ALGraph*G;

g.n=5;g.e=6;

intA[MAXV][MAXV]={{0,1,0,1,0},{1,0,1,0,0}, {0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0}}; for(i=0;i<g.n;i++) //建立圖8.1(a)的鄰接矩陣

for(j=0;j<g.n;j++)

g.edges[i][j]=A[i][j];

MatToList(g,G);for(i=0;i<g.n;i++)visited[i]=0;

printf("圖G:\n");DispAdj(G); //輸出鄰接表

printf("從%d到%d的所有長度為%d路徑:\n",u,v,d);PathAll(G,u,v,d,path,-1);

printf("\n");}教材中藍(lán)字有誤。程序執(zhí)行結(jié)果如下：圖G:0:131:022:1343:0244:23從1到4的所有長度為3路徑:1034123413240

例8.5

假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，求圖中通過某頂點k的所有簡單回路（若存在）。并輸出如下圖所示的有向圖的鄰接表和通過頂點0的所有回路。01423int

visited[MAXV]； //全局變量voidDFSPath(ALGraph*G,int

u,int

v,int

path[],intd)//d是到當(dāng)前為止已走過的路徑長度，調(diào)用時初值為-1{int

m,i;ArcNode*p;

visited[u]=1;d++;path[d]=u;p=G->adjlist[u].firstarc;//p指向頂點u的第一條邊

while(p!=NULL){m=p->adjvex; //m為頂點u的相鄰點

if(m==v&&d>0) //找到一個回路，輸出之

{printf(""); for(i=0;i<=d;i++)

printf("%d",path[i]);

printf("%d\n",v); } if(visited[m]==0) //m未訪問,則遞歸訪問之

DFSPath(G,m,v,path,d); p=p->nextarc; //找u的下一個鄰接頂點

}

visited[u]=0; //恢復(fù)環(huán)境：使該頂點可重新使用}voidFindCyclePath(ALGraph*G,intk)//輸出經(jīng)過頂點k的所有回路{int

path[MAXV];

printf("經(jīng)過頂點%d的所有回路\n",k);DFSPath(G,k,k,path,-1);}8.4生成樹和最小生成樹8.4.1生成樹的概念一個連通圖的生成樹是一個極小連通子圖,它含有圖中全部頂點,但只有構(gòu)成一棵樹的(n-1)條邊。命題：如果在一棵生成樹上添加一條邊,必定構(gòu)成一個環(huán)。因為這條邊使得它依附的那兩個頂點之間有了第二條路徑。一棵有n個頂點的生成樹(連通無回路圖)有且僅有(n-1)條邊,如果一個圖有n個頂點和小于(n-1)條邊,則是非連通圖。如果它多于(n-1)條邊,則一定有回路。但是,有(n-1)條邊的圖不一定都是生成樹。

對于一個帶權(quán)(假定每條邊上的權(quán)均為大于零的實數(shù))連通無向圖G中的不同生成樹,其每棵樹的所有邊上的權(quán)值之和也可能不同；圖的所有生成樹中具有邊上的權(quán)值之和最小的樹稱為圖的最小生成樹。按照生成樹的定義,n個頂點的連通圖的生成樹有n個頂點、n-1條邊。因此,構(gòu)造最小生成樹的準(zhǔn)則有三條：

(1)必須只使用該圖中的邊來構(gòu)造最小生成樹；

(2)必須使用且僅使用n-1條邊來連接圖中的n個頂點；

(3)不能使用產(chǎn)生回路的邊。8.4.2無向圖的連通分量和生成樹在對無向圖進(jìn)行遍歷時,對于連通圖,僅需調(diào)用遍歷過程(DFS或BFS)一次,從圖中任一頂點出發(fā),便可以遍歷圖中的各個頂點。對非連通圖,則需多次調(diào)用遍歷過程,每次調(diào)用得到的頂點集連同相關(guān)的邊就構(gòu)成圖的一個連通分量。設(shè)G=(V,E)為連通圖,則從圖中任一頂點出發(fā)遍歷圖時,必定將E(G)分成兩個集合T和B,其中T是遍歷圖過程中走過的邊的集合,B是剩余的邊的集合：T∩B=Φ,T∪B=E(G)。顯然,G'=(V,T)是G的極小連通子圖,即G'是G的一棵生成樹。由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。這樣的生成樹是由遍歷時訪問過的n個頂點和遍歷時經(jīng)歷的n-1條邊組成。對于非連通圖,每個連通分量中的頂點集和遍歷時走過的邊一起構(gòu)成一棵生成樹,各個連通分量的生成樹組成非連通圖的生成森林。8.4.4普里姆算法

普里姆(Prim)算法是一種構(gòu)造性算法。假設(shè)G=(V,E)是一個具有n個頂點的帶權(quán)連通無向圖,T=(U,TE)是G的最小生成樹,其中U是T的頂點集,TE是T的邊集,則由G構(gòu)造最小生成樹T的步驟如下：

(1)初始化U={v}。v到其他頂點的所有邊為候選邊；

(2)重復(fù)以下步驟n-1次,使得其他n-1個頂點被加入到U中：①從候選邊中挑選權(quán)值最小的邊輸出,設(shè)該邊在V-U中的頂點是k,將v加入U中,刪除和k關(guān)聯(lián)的邊；②考察當(dāng)前V-U中的所有頂點vi,修改候選邊：若(vi,vk)的權(quán)值小于原來和vk關(guān)聯(lián)的候選邊,則用(v,vi)取代后者作為候選邊。普里姆算法過程：vkUV－UkiUV－Uv普里姆算法求解最小生成樹的過程01234651951418271682131270432165148531621

012

34

56closestlowcost19∞18∞14∞0000000001648412483337213325500UV-U(i,closest[i])i∈U，closest[i]∈V－U候選邊：普里姆(Prim)算法如下：#defineINF32767//INF表示∞voidPrim(int

cost[][MAXV],int

n,intv){int

lowcost[MAXV],min;

intclosest[MAXV],i,j,k;for(i=0;i<n;i++)//給lowcost[]和closest[]置初值

{lowcost[i]=cost[v][i];

closest[i]=v; }

for(i=1;i<n;i++)//找出n-1個頂點

{min=INF; for(j=0;j<n;j++) //在(V-U)中找出離U最近的頂點k if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}

printf("邊(%d,%d)權(quán)為:%d\n",closest[k],k,min);

lowcost[k]=0;//標(biāo)記k已經(jīng)加入U for(j=0;j<n;j++)//修改數(shù)組lowcost和closestif(cost[k][j]!=0&&cost[k][j]<lowcost[j]){lowcost[j]=cost[k][j];closest[j]=k;}}}

Prim()算法中有兩重for循環(huán),所以時間復(fù)雜度為O(n2)。8.4.5克魯斯卡爾算法

克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增次序選擇合適的邊來構(gòu)造最小生成樹的方法。假設(shè)G=(V,E)是一個具有n個頂點的帶權(quán)連通無向圖,T=(U,TE)是G的最小生成樹。

(1)置U的初值等于V(即包含有G中的全部頂點),TE的初值為空集(即圖T中每一個頂點都構(gòu)成一個分量)。

(2)將圖G中的邊按權(quán)值從小到大的順序依次選?。喝暨x取的邊未使生成樹T形成回路,則加入TE；否則舍棄,直到TE中包含(n-1)條邊為止。克魯斯卡爾算法求解最小生成樹的過程035214516354652025314NOViVjW1021235231434254503561257235801692461045660033110000為了簡便,在實現(xiàn)克魯斯卡爾算法Kruskal()時,參數(shù)E存放圖G中的所有邊,假設(shè)它們是按權(quán)值從小到大的順序排列的。n為圖G的頂點個數(shù),e為圖G的邊數(shù)。

typedef

struct

{ intu;//邊的起始頂點

intv;//邊的終止頂點

intw;//邊的權(quán)值

}Edge;voidKruskal(Edge

E[],int

n,inte){inti,j,m1,m2,sn1,sn2,k;int

vset[MAXV];for(i=0;i<n;i++)vset[i]=i; //初始化輔助數(shù)組

k=1;//k表示當(dāng)前構(gòu)造最小生成樹的第幾條邊,初值為1j=0;//E中邊的下標(biāo),初值為0while(k<n)//生成的邊數(shù)小于n時循環(huán)

{m1=E[j].u;m2=E[j].v; //取一條邊的頭尾頂點

sn1=vset[m1];sn2=vset[m2];//分別得到兩個頂點所屬的集合編號

if(sn1!=sn2) //屬不同的集合->最小生成樹的一條邊

{printf("(%d,%d):%d\n",m1,m2,E[j].w); k++; //生成邊數(shù)增1 for(i=0;i<n;i++) //兩個集合統(tǒng)一編號

if(vset[i]==sn2) //集合編號為sn2的改為sn1

vset[i]=sn1; } j++; //掃描下一條邊

}}

采用并查集求解（改進(jìn)克魯斯卡爾算法）：voidKruskal(MGraphg){

inti,j,k,u1,v1,sn1,sn2;

UFSTree

t[MaxSize];EdgeE[MaxSize];k=1; //e數(shù)組的下標(biāo)從1開始計

for(i=0;i<g.n;i++) //由g產(chǎn)生的邊集E for(j=0;j<g.n;j++) if(g.edges[i][j]!=0&&g.edges[i][j]!=INF) { E[k].u=i;E[k].v=j;

E[k].w=g.edges[i][j]; k++; }

HeapSort(E,g.e); //采用堆排序?qū)數(shù)組按權(quán)值遞增排序

MAKE_SET(t,g.n); //初始化并查集樹tk=1; //k表示當(dāng)前構(gòu)造生成樹的第幾條邊,初值為1j=1; //E中邊的下標(biāo),初值為1while(k<g.n) //生成的邊數(shù)小于n時循環(huán)

{u1=E[j].u;v1=E[j].v; //取一條邊的頭尾頂點編號u1和v2sn1=FIND_SET(t,u1);sn2=FIND_SET(t,v1);//分別得到兩個頂點所屬的集合編號

if(sn1!=sn2)//兩頂點屬不同集合,該邊是最小生成樹的一條邊

{printf("(%d,%d):%d\n",u1,v1,E[j].w); k++; //生成邊數(shù)增1 UNION(t,u1,v1); //將u1和v1兩個頂點合并

}j++; //掃描下一條邊

}}如果給定的帶權(quán)連通無向圖G有e條邊,n個頂點，采用堆排序(在第10章中介紹)對邊按權(quán)值遞增排序，那么用改進(jìn)克魯斯卡爾算法構(gòu)造最小生成樹的時間復(fù)雜度降為O(elog2e)。由于它與n無關(guān)，只與e有關(guān)，所以克魯斯卡爾算法適合于稀疏圖。思考題有n臺計算機(jī)，已知它們的位置，現(xiàn)連成一個網(wǎng)絡(luò)，采用什么算法求解所花最少網(wǎng)線。8.5最短路徑8.5.1路徑的概念

在一個無權(quán)的圖中,若從一頂點到另一頂點存在著一條路徑,則稱該路徑長度為該路徑上所經(jīng)過的邊的數(shù)目,它等于該路徑上的頂點數(shù)減1。由于從一頂點到另一頂點可能存在著多條路徑,每條路徑上所經(jīng)過的邊數(shù)可能不同,即路徑長度不同,我們把路徑長度最短(即經(jīng)過的邊數(shù)最少)的那條路徑叫做最短路徑,其路徑長度叫做最短路徑長度或最短距離。對于帶權(quán)的圖,考慮路徑上各邊上的權(quán)值,則通常把一條路徑上所經(jīng)邊的權(quán)值之和定義為該路徑的路徑長度或稱帶權(quán)路徑長度。從源點到終點可能不止一條路徑,把帶權(quán)路徑長度最短的那條路徑稱為最短路徑,其路徑長度(權(quán)值之和)稱為最短路徑長度或者最短距離。8.5.2從一個頂點到其余各頂點的最短路徑

問題：給定一個帶權(quán)有向圖G與源點v,求從v到G中其他頂點的最短路徑,并限定各邊上的權(quán)值大于或等于0。

采用狄克斯特拉(Dijkstra)算法求解基本思想是：設(shè)G=(V,E)是一個帶權(quán)有向圖,把圖中頂點集合V分成兩組：第一組為已求出最短路徑的頂點集合(用S表示,初始時S中只有一個源點,以后每求得一條最短路徑v,…vk,就將vk加入到集合S中,直到全部頂點都加入到S中,算法就結(jié)束了)

第二組為其余未確定最短路徑的頂點集合(用U表示)。按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中,總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外,每個頂點對應(yīng)一個距離,S中的頂點的距離就是從v到此頂點的最短路徑長度,U中的頂點的距離從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。

(1)初始時,S只包含源點,即S={v},v的距離為0。U包含除v外的其他頂點,U中頂點u距離為邊上的權(quán)(若v與u有邊<v,u>)或∞(若u不是v的出邊鄰接點)。

(2)從U中選取一個距離v最小的頂點k,把k加入S中(該選定的距離就是v到k的最短路徑長度)。

(3)以k為新考慮的中間點,修改U中各頂點的距離：若從源點v到頂點u(u∈U)的距離(經(jīng)過頂點k)比原來距離(不經(jīng)過頂點k)短,則修改頂點u的距離值,修改后的距離值的頂點k的距離加上邊<k,u>上的權(quán)。

(4)重復(fù)步驟(2)和(3)直到所有頂點都包含在S中。狄克斯特拉算法的過程頂點V到j(luò)的最小距離＝MIN(cvk+wkj,cvj)

S U dist[]path[]01234560123456{0} {1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,0,0,0,-1,-1,-1}{0,1}{2,3,4,5,6}{0,4,5,6,11,∞,∞}{0,0,1,0,1,-1,-1}{0,1,2}{3,4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3}{4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,0,1,0,5,2,5}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}438164256147660123456distpath00466∞∞∞00000401155969101711525101641656201狄克斯特拉算法如下(n為圖G的頂點數(shù),v0為源點編號)：voidDijkstra(int

cost[][MAXV],int

n,intv0){intdist[MAXV],path[MAXV];

int

s[MAXV];int

mindis,i,j,u;for(i=0;i<n;i++){dist[i]=cost[v0][i]; //距離初始化

s[i]=0; //s[]置空

if(cost[v0][i]<INF) //路徑初始化

path[i]=v0; else path[i]=-1;}s[v0]=1;path[v0]=0; //源點編號v0放入s中

for(i=0;i<n;i++)//循環(huán)直到所有頂點的最短路徑都求出

{mindis=INF; u=-1; for(j=0;j<n;j++)//選取不在s中且具有最小距離的頂點u if(s[j]==0&&dist[j]<mindis) {u=j;mindis=dist[j]; } s[u]=1;//頂點u加入s中

for(j=0;j<n;j++)//修改不在s中的頂點的距離

if(s[j]==0) if(cost[u][j]<INF&&dist[u]+cost[u][j]<dist[j]) {dist[j]=dist[u]+cost[u][j];path[j]=u;}}Dispath(dist,path,s,n,v0); //輸出最短路徑}09年考研題

1.帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標(biāo)頂點之間的一條最短路徑。假設(shè)從初始頂點到目標(biāo)頂點之間存在路徑，現(xiàn)有一種解決該問題的方法：（1）設(shè)最短路徑初始時僅包含初始頂點，令當(dāng)前頂點u為初始頂點；（2）選擇離u最近且尚未在最短路徑中的一個頂點v，加入到最短路徑中，修改當(dāng)前頂點u=v；（3）重復(fù)步驟（2），直到u是目標(biāo)頂點時為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。思考題求單源最短路徑問題是否可以采用求最小生成樹的方法求解？8.5.3每對頂點之間的最短路徑

問題：對于一個各邊權(quán)值均大于零的有向圖,對每一對頂點vi≠vj,求出vi與vj之間的最短路徑和最短路徑長度?？梢酝ㄟ^以每個頂點作為源點循環(huán)求出每對頂點之間的最短路徑。除此之外,弗洛伊德(Floyd)算法也可用于求兩頂點之間最短路徑。假設(shè)有向圖G=(V,E)采用鄰接矩陣cost存儲,另外設(shè)置一個二維數(shù)組A用于存放當(dāng)前頂點之間的最短路徑長度,分量A[i][j]表示當(dāng)前頂點vi到頂點vj的最短路徑長度。弗洛伊德算法的基本思想是遞推產(chǎn)生一個矩陣序列A0,A1,…,Ak,…,An,其中Ak[i][j]表示從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k的最短路徑長度。

初始時,有A-1[i][j]=cost[i][j]。當(dāng)求從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k+1的最短路徑長度時,要分兩種情況考慮：一種情況是該路徑不經(jīng)過頂點編號為k+1的頂點,此時該路徑長度與從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k的最短路徑長度相同；另一種情況是從頂點vi到頂點vj的最短路徑上經(jīng)過編號為k+1的頂點。Ak+1[i,j]=MIN(Ak[i,j],Ak[i,k+1]+Ak[k+1,j])那么,該路徑可分為兩段:(1)從頂點vi到頂點vk+1的最短路徑;(2)從頂點vk+1到頂點vj的最短路徑。此時最短路徑長度等于這兩段路徑長度之和。這兩種情況中的較小值,就是所要求的從頂點vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k+1的最短路徑。弗洛伊德思想可用如下的表達(dá)式來描述：

A-1[i][j]=cost[i][j]Ak+1[i][j]=MIN{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤k≤n-1)

采用弗洛伊德算法求解過程012353273124

考慮頂點v0,A0[i][j]表示由vi到vj,經(jīng)由頂點v0的最短路徑。

v2-v0-v1：不改變。

v2-v0-v3：不改變。

v3-v2-v0-v1：不改變。012353273124

考慮頂點v1,A1[i][j]表示由vi到vj,經(jīng)由頂點v1的最短路徑。

v0-v1-v2,路徑長度為9,將A[0][2]改為9。

path[0][2]改為1。

012353273124考慮頂點v2,A2[i][j]表示由vi到vj,經(jīng)由頂點v2的最短路徑。

v3-v2-v0,長度為4,將A[3][0]改為4；

v3-v2-v1,長度為4,將A[3][1]改為4。

v1-v2-v0,長度為7,將A[1][0]改為7。將path[3][0]、path[3][1]和path[1][0]均改為2。因此,有：

012353273124考慮頂點v3,A3[i][j]表示由vi到vj,經(jīng)由頂點v3的最短路徑。

v0-v3-v2：長度為8,A[0][2]改為8；

v1-v3-v2-v0,長度為6,A[1][0]改為6；

v1-v3-v2,長度為3,A[1][2]改為3。將path[0][2]、path[1][0]后path[1][2]均改為3。012353273124從0到0路徑為：0,0 路徑長度為：0從0到1路徑為：0,1 路徑長度為：5從0到2路徑為：0,3,2 路徑長度為：8從0到3路徑為：0,3 路徑長度為：7從1到0路徑為：1,3,2,0 路徑長度為：6從1到1路徑為：1,1 路徑長度為：0從1到2路徑為：1,3,2 路徑長度為：3從1到3路徑為：1,3 路徑長度為：2A=Path=從2到0路徑為：2,0 路徑長度為：3從2到1路徑為：2,1 路徑長度為：3從2到2路徑為：2,2 路徑長度為：0從2到3路徑為：2,3 路徑長度為：2從3到0路徑為：3,2,0 路徑長度為：4從3到1路徑為：3,2,1 路徑長度為：4從3到2路徑為：3,2 路徑長度為：1從3到3路徑為：3,3 路徑長度為：0弗洛伊德算法如下：voidFloyd(int

cost[][MAXV],intn){int

A[MAXV][MAXV],path[MAXV][MAXV];inti,j,k;for(i=0;i<n;i++) for(j=0;j<n;j++){A[i][j]=cost[i][j]; path[i][j]=-1;}for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(A[i][j]>(A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;}

Dispath(A,path,n);//輸出最短路徑}時間復(fù)雜度為O(n3)8.6拓?fù)渑判?/p>

設(shè)G=(V,E)是一個具有n個頂點的有向圖,V中頂點序列v1,v2,…,vn稱為一個拓?fù)湫蛄?當(dāng)且僅當(dāng)該頂點序列滿足下列條件：

若<vi,vj>是圖中的邊(即從頂點vi到vj有一條路徑),則在序列中頂點vi必須排在頂點vj之前。在一個有向圖中找一個拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。課程代號課程名稱先修課程C1高等數(shù)學(xué)無C2程序設(shè)計無C3離散數(shù)學(xué)C1C4數(shù)據(jù)結(jié)構(gòu)C2,C3C5編譯原理C2,C4C6操作系統(tǒng)C4,C7C7計算機(jī)組成原理C2

例如,計算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè),假設(shè)這些課程的名稱與相應(yīng)代號有如下關(guān)系：課程之間的先后關(guān)系可用有向圖表示

對這個有向圖進(jìn)行拓?fù)渑判蚩傻玫揭粋€拓?fù)湫蛄校篊1-C3-C2-C4-C7-C6-C5。也可得到另一個拓?fù)湫蛄校篊2-C7-C1-C3-C4-C5-C6,還可以得到其他的拓?fù)湫蛄?。學(xué)生按照任何一個拓?fù)湫蛄卸伎梢皂樞虻剡M(jìn)行課程學(xué)習(xí)。

(1)從有向圖中選擇一個沒有前驅(qū)(即入度為0)的頂點并且輸出它。

(2)從網(wǎng)中刪去該頂點,并且刪去從該頂點發(fā)出的全部有向邊。

(3)重復(fù)上述兩步,直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點為止。拓?fù)渑判虿襟E

為了實現(xiàn)拓?fù)渑判虻乃惴?對于給定的有向圖,采用鄰接表作為存儲結(jié)構(gòu),為每個頂點設(shè)立一個鏈表,每個鏈表有一個表頭結(jié)點,這些表頭結(jié)點構(gòu)成一個數(shù)組,表頭結(jié)點中增加一個存放頂點入度的域count。即將鄰接表定義中的VNode類型修改如下：

typedef

struct //表頭結(jié)點類型

{Vertexdata;//頂點信息

intcount;//存放頂點入度

ArcNode*firstarc;//指向第一條弧

}VNode;voidTopSort(VNode

adj[],intn){int

i,j;intSt[MAXV],top=-1;//棧St的指針為top

ArcNode*p;for(i=0;i<n;i++)if(adj[i].count==0) //入度為0的頂點入棧

{top++;St[top]=i;}while(top>-1) //棧不為空時循環(huán)

{i=St[top];top--; //出棧

printf("%d",i);p=adj[i].firstarc;while(p!=NULL){j=p->adjvex;adj[j].count--;if(adj[j].count==0) {top++;St[top]=j;}p=p->nextarc;//找下一個相鄰頂點

}}}8.7AOE網(wǎng)與關(guān)鍵路徑若用前面介紹過的帶權(quán)有向圖(DAG)描述工程的預(yù)計進(jìn)度,以頂點表示事件,有向邊表示活動,邊e的權(quán)c(e)表示完成活動e所需的時間(比如天數(shù)),或者說活動e持續(xù)時間。圖中入度為0的頂點表示工程的開始事件(如開工儀式),出度為0的頂點表示工程結(jié)束事件。則稱這樣的有向圖為AOE網(wǎng)(ActivityOnEdge)。7

整個工程完成的時間為：從有向圖的源點到匯點的最長路徑，具有最大長度的路徑叫關(guān)鍵路徑。abcdefghk6452118244例如:

“關(guān)鍵活動”指的是：該弧上的權(quán)值增加將使有向圖上的最長路徑的長度增加。注意：在一個AOE網(wǎng)中，可以有不止一條的關(guān)鍵路徑。源點匯點6174幾個定義：

(1)事件v的最早可發(fā)生時間：假設(shè)事件x是源點,事件y為匯點,并規(guī)定事件x的發(fā)生時間為0。定義圖中任一事件v的最早(eventearly)可發(fā)生時間ve(v)等于x到v所有路徑長度的最大值,即：ve(v)=

上式中的MAX是對x到v的所有路徑p取最大值,c(p)表示路徑p的長度(路徑上邊長之和),即：c(p)=

完成整個工程所需的最少時間,等于事件y的最早可發(fā)生時間ve(y)。

(2)事件v的最遲可發(fā)生時間：定義在不影響整個工程進(jìn)度的前提下,事件v必須發(fā)生的時間稱為v的最遲(eventlate)可發(fā)生時間,記作vl(v)。vl(v)應(yīng)等于ve(y)與v到y(tǒng)的最長路徑長度之差(y是匯點),即：vl(v)=ve(y)-

(3)