數(shù)據(jù)結構第七章 圖

第7章圖本章中介紹下列主要內容：圖的定義圖的存儲結構圖的遍歷操作圖的幾個典型問題第7章圖

圖(Graph)是一種比線性表和樹更為復雜的數(shù)據(jù)結構。

線性結構：是研究數(shù)據(jù)元素之間的一對一關系。在這種結構中，除第一個和最后一個元素外，任何一個元素都有唯一的一個直接前驅和直接后繼。

樹結構：是研究數(shù)據(jù)元素之間的一對多的關系。在這種結構中，每個元素對下(層)可以有0個或多個元素相聯(lián)系，對上(層)只有唯一的一個元素相關，數(shù)據(jù)元素之間有明顯的層次關系。圖結構：是研究數(shù)據(jù)元素之間的多對多的關系。在這種結構中，任意兩個元素之間可能存在關系。即結點之間的關系可以是任意的，圖中任意元素之間都可能相關。圖的應用極為廣泛，已滲入到諸如語言學、邏輯學、物理、化學、電訊、計算機科學以及數(shù)學的其它分支。第7章圖7.1

圖的基本概念7.1.1圖的定義和術語一個圖(G)定義為一個偶對(V,E)，記為G=(V,E)。其中：V是頂點(Vertex)的非空有限集合，記為V(G)；E是無序集V&V的一個子集，記為E(G)，其元素是圖的弧(Arc)。將頂點集合為空的圖稱為空圖。其形式化定義為：G=(V，E)V={v|vdataobject}E={<v,w>|v,wV∧p(v,w)}P(v,w)表示從頂點v到頂點w有一條直接通路。

弧(Arc)

：表示兩個頂點v和w之間存在一個關系，用頂點偶對<v,w>表示。通常根據(jù)圖的頂點偶對將圖分為有向圖和無向圖。

有向圖(Digraph)：

若圖G的關系集合E(G)中，頂點偶對<v,w>的v和w之間是有序的，稱圖G是有向圖。在有向圖中，若<v,w>E(G)，表示從頂點v到頂點w有一條弧。其中：v稱為弧尾(tail)或始點(initial

node)，w稱為弧頭(head)或終點(terminalnode)

。定義和術語（2）無向圖(Undigraph)：若圖G的關系集合E(G)中，頂點偶對<v,w>的v和w之間是無序的，稱圖G是無向圖。在無向圖中，若<v,w>E(G)，有<w,v>E(G)，即E(G)是對稱，則用無序對(v,w)表示v和w之間的一條邊(Edge)，因此(v,w)和(w,v)代表的是同一條邊。定義和術語（3）

例1：設有有向圖G1和無向圖G2，形式化定義：G1=(V1，E1)V1={a,b,c,d,e}E1={<a,b>,<a,c>,<a,e>,<c,d>,<c,e>,<d,a>,<d,b>,<e,d>}G2=(V2，E2)V2={a,b,c,d}E2={(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)}abcd(b)無向圖G2

(a)有向圖G1

acbde

完全無向圖：對于無向圖，若圖中頂點數(shù)為n，用e表示邊的數(shù)目，則e[0，n(n-1)/2]。具有n(n-1)/2條邊的無向圖稱為完全無向圖。

完全無向圖另外的定義是：對于無向圖G=(V，E)，若vi，vj

V，當vi≠vj時，有(vi,vj)E，即圖中任意兩個不同的頂點間都有一條無向邊，這樣的無向圖稱為完全無向圖。定義和術語（4）完全有向圖：對于有向圖，若圖中頂點數(shù)為n，用e表示弧的數(shù)目，則e[0，n(n-1)]。具有n(n-1)條邊的有向圖稱為完全有向圖。完全有向圖另外的定義是：對于有向圖G=(V，E)，若vi，vjV

，當vi≠vj時，有<vi,vj>E∧<vj,vi>E，即圖中任意兩個不同的頂點間都有一條弧，這樣的有向圖稱為完全有向圖。定義和術語（5）有很少邊或弧的圖（e<n㏒n）的圖稱為稀疏圖，反之稱為稠密圖。

權(Weight)：與圖的邊和弧相關的數(shù)。權可以表示從一個頂點到另一個頂點的距離或耗費。子圖和生成子圖：設有圖G=(V，E)和G’=(V’，E’)，若V’V且E’E，則稱圖G’是G的子圖；若V’=V且E’E，則稱圖G’是G的一個生成子圖。定義和術語（6）頂點的鄰接(Adjacent)：對于無向圖G=(V，E)，若邊(v,w)E，則稱頂點v和w互為鄰接點，即v和w相鄰接。邊(v,w)依附(incident)與頂點v和w。對于有向圖G=(V，E)，若有向弧<v,w>E，則稱頂點v

“鄰接到”頂點w，頂點w“鄰接自”頂點v，弧<v,w>與頂點v和w

“相關聯(lián)”。頂點的度、入度、出度：對于無向圖G=(V，E)，viV，圖G中依附于vi的邊的數(shù)目稱為頂點vi的度(degree)，記為TD(vi)。定義和術語（7）

顯然，在無向圖中，所有頂點度的和是圖中邊的2倍。即∑TD(vi)=2e(i=1,2,…,n，e為圖的邊數(shù))。對有向圖G=(V，E)，若viV，圖G中以vi作為起點的有向邊(弧)的數(shù)目稱為頂點vi的出度(Outdegree)，記為OD(vi)；以vi作為終點的有向邊(弧)的數(shù)目稱為頂點vi的入度(Indegree)，記為ID(vi)。頂點vi的出度與入度之和稱為vi的度，記為TD(vi)。即

TD(vi)=OD(vi)+ID(vi)

定義和術語（8）路徑(Path)、路徑長度、回路(Cycle)：對無向圖G=(V，E)，若從頂點vi經過若干條邊能到達vj，稱頂點vi和vj是連通的，又稱頂點vi到vj有路徑。對有向圖G=(V，E)，從頂點vi到vj有有向路徑，指的是從頂點vi經過若干條有向邊(弧)能到達vj?；蚵窂绞菆DG中連接兩頂點間所經過的頂點序列。Path=vi0vi1…vim，vijV且(vij-1,vij)Ej=1,2,…,m定義和術語（9）路徑上邊或有向邊(弧)的數(shù)目稱為該路徑的長度。在一條路徑中，若沒有重復相同的頂點，該路徑稱為簡單路徑；第一個頂點和最后一個頂點相同的路徑稱為回路(環(huán))；在一個回路中，若除第一個與最后一個頂點外，其余頂點不重復出現(xiàn)的回路稱為簡單回路(簡單環(huán))。定義和術語（10）連通圖、圖的連通分量：對無向圖G=(V，E)，若vi，vj

V，vi和vj都是連通的，則稱圖G是連通圖，否則稱為非連通圖。若G是非連通圖，則極大的連通子圖稱為G的連通分量。對有向圖G=(V，E)，若vi，vj

V，都有以vi為起點，

vj

為終點以及以vj為起點，vi為終點的有向路徑，稱圖G是強連通圖，否則稱為非強連通圖。若G是非強連通圖，則極大的強連通子圖稱為G的強連通分量。

“極大”的含義：指的是對子圖再增加圖G中的其它頂點，子圖就不再連通。定義和術語（11）

生成樹、生成森林：一個連通圖(無向圖)的生成樹是一個極小連通子圖，它含有圖中全部n個頂點和只有足以構成一棵樹的n-1條邊，稱為圖的生成樹，如圖7-2所示。關于無向圖的生成樹的幾個結論：

◆

一棵有n個頂點的生成樹有且僅有n-1條邊；

◆

如果一個圖有n個頂點和小于n-1條邊，則是非連通圖；adbc圖7-2圖G2的一棵生成樹◆

如果多于n-1條邊，則一定有環(huán)；◆

有n-1條邊的圖不一定是生成樹。

有向圖的生成森林是這樣一個子圖，由若干棵有向樹組成，含有圖中全部頂點。有向樹是只有一個頂點的入度為0，其余頂點的入度均為1的有向圖，如圖7-3所示。

網：每個邊(或弧)都附加一個權值的圖，稱為帶權圖。帶權的連通圖(包括弱連通的有向圖)稱為網或網絡。網絡是工程上常用的一個概念，用來表示一個工程或某種流程，如圖7-4所示。圖7-3有向圖及其生成森林abcde(a)有向圖(b)生成森林acbde354126abcde3圖7-4帶權有向圖7.1.2

圖的抽象數(shù)據(jù)類型定義

圖是一種數(shù)據(jù)結構，加上一組基本操作就構成了圖的抽象數(shù)據(jù)類型。圖的抽象數(shù)據(jù)類型定義如下：ADTGraph{數(shù)據(jù)對象V：具有相同特性的數(shù)據(jù)元素集合，稱為頂點集。數(shù)據(jù)關系R：R={VR}VR={<v,w>|<v,w>|v,wV∧p(v,w)，<v,w>表示從v到w的弧，P(v,w)定義了弧<v,w>的信息}基本操作P：Create_Graph()：圖的創(chuàng)建操作。

初始條件：無。操作結果：生成一個沒有頂點的空圖G。GetVex(G,v)：求圖中的頂點v的值。初始條件：圖G存在，v是圖中的一個頂點。操作結果：生成一個沒有頂點的空圖G。

……

DFStraver(G,V)：從v出發(fā)對圖G深度優(yōu)先遍歷。

初始條件：圖G存在。操作結果：對圖G深度優(yōu)先遍歷，每個頂點訪問且只訪問一次。}ADTGraph7.2圖的存儲結構

圖的存儲結構比較復雜，其復雜性主要表現(xiàn)在：

◆

任意頂點之間可能存在聯(lián)系，無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關系。

◆

圖中頂點的度不一樣，有的可能相差很大，若按度數(shù)最大的頂點設計結構，則會浪費很多存儲單元，反之按每個頂點自己的度設計不同的結構，又會影響操作。圖的常用的存儲結構有：鄰接矩陣、鄰接鏈表、十字鏈表、鄰接多重表和邊表。7.2.1鄰接矩陣(數(shù)組)表示法基本思想：對于有n個頂點的圖，用一維數(shù)組vexs[n]存儲頂點信息，用二維數(shù)組A[n][n]存儲頂點之間關系的信息。該二維數(shù)組稱為鄰接矩陣。在鄰接矩陣中，以頂點在vexs數(shù)組中的下標代表頂點，鄰接矩陣中的元素A[i][j]存放的是頂點i到頂點j之間關系的信息。

1無向圖--無權圖的鄰接矩陣

無向無權圖G=(V，E)有n(n≧1)個頂點，其鄰接矩陣是n階對稱方陣，如圖7-5所示。其元素的定義如下：(a)無向圖

abcd圖7-5無向無權圖的數(shù)組存儲(b)頂點矩陣vexsabcd0111101111011110(c)鄰接矩陣1若(vi,vj)E，即vi,vj鄰接0若(vi,vj)E，即vi,vj不鄰接A[i][j]=

1無向圖--帶權圖的鄰接矩陣

無向帶權圖G=(V，E)的鄰接矩陣如圖7-6所示。其元素的定義如下：(a)帶權無向圖

(b)頂點矩陣圖7-6無向帶權圖的數(shù)組存儲(c)鄰接矩陣354126abcde3vexsabcde∞62∞∞6∞34323∞1∞∞43∞5∞3∞5∞Wij

若(vi,vj)E，即vi,vj鄰接，權值為wij∞

若(vi,vj)E，即vi,vj不鄰接時A[i][j]=無向圖鄰接矩陣的特性：

◆

鄰接矩陣是對稱方陣；

◆

對于頂點vi，其度數(shù)是第i行的非0元素的個數(shù)；

◆

無向圖的邊數(shù)是上(或下)三角形矩陣中非0元素個數(shù)。

2有向圖--

無權圖的鄰接矩陣

若有向無權圖G=(V，E)有n(n≧1)個頂點，則其鄰接矩陣是n階對稱方陣，如圖7-7所示。元素定義如下：1若<vi,vj>E，從vi到vj有弧A[i][j]=0若<vi,vj>E從vi到vj

沒有弧(a)有向圖acbde圖7-7有向無權圖的數(shù)組存儲(b)頂點矩陣vexsabcde(c)鄰接矩陣0110100000000111100000010

2有向圖--帶權圖的鄰接矩陣

有向帶權圖G=(V，E)的鄰接矩陣如圖7-8所示。其元素的定義如下：wij

若<vi,vj>E，即vi,vj鄰接，權值為wij∞

若<vi,vj>E，即vi,vj不鄰接時A[i][j]=圖7-8帶權有向圖的數(shù)組存儲(b)頂點矩陣vexsabcde(c)鄰接矩陣∞62∞∞∞∞

∞

∞3∞3∞1∞∞4

∞∞5∞∞

∞∞∞(a)帶權有向圖

354126abcde3有向圖鄰接矩陣的特性：◆

對于頂點vi，第i行的非0元素的個數(shù)是其出度OD(vi)；第i列的非0元素的個數(shù)是其入度ID(vi)。◆

鄰接矩陣中非0元素的個數(shù)就是圖的弧的數(shù)目。

3圖的鄰接矩陣的操作

圖的鄰接矩陣的實現(xiàn)比較容易，定義兩個數(shù)組分別存儲頂點信息(數(shù)據(jù)元素)和邊或弧的信息(數(shù)據(jù)元素之間的關系)。其存儲結構形式定義如下：#defineINFINITYMAX_VAL/*最大值∞*//*根據(jù)圖的權值類型，分別定義為最大整數(shù)或實數(shù)*/#defineMAX_VEX30/*最大頂點數(shù)目*/typedef

enum{DG,AG,WDG,WAG}GraphKind;/*{有向圖，無向圖，帶權有向圖，帶權無向圖}*/typedef

struct

ArcCell{VRType

adj;/*弧或邊兩頂點關系,1或0或權值或無窮*/InfoType*Info;/*弧或邊的其它信息*/}ArcCell;/*弧或邊的結構定義*/typedef

struct{GraphKindkind;/*圖的種類標志*/int

vexnum,arcnum;/*圖的當前頂點數(shù)和弧數(shù)*/VexType

vexs[MAX_VEX];/*頂點向量*/ArcCell

arcs[MAX_VEX][MAX_VEX];}MGraph;/*圖的結構定義*/利用上述定義的數(shù)據(jù)結構，可以方便地實現(xiàn)圖的各種操作。(1)圖的創(chuàng)建AdjGraph*Create_Graph(MGraph*G){printf(“請輸入圖的種類標志：”);scanf(“%d”,&G->kind);G->vexnum=0;/*初始化頂點個數(shù)*/return(G);}

(2)圖的頂點定位

圖的頂點定位操作實際上是確定一個頂點在vexs數(shù)組中的位置(下標)，其過程完全等同于在順序存儲的線性表中查找一個數(shù)據(jù)元素。int

LocateVex(MGraph*G,VexType*vp){intk;for(k=0;k<G->vexnum;k++)if(G->vexs[k]==*vp)return(k);return(-1);/*圖中無此頂點*/}

(3)向圖中增加頂點

向圖中增加一個頂點的操作，類似在順序存儲的線性表的末尾增加一個數(shù)據(jù)元素。int

AddVertex(MGraph*G,VexType*vp){intk,j;if(G->vexnum>=MAX_VEX){printf(“VertexOverflow!\n”);return(-1);}if(LocateVex(G,vp)!=-1){printf(“Vertexhasexisted!\n”);return(-1);}k=G->vexnum;G->vexs[G->vexnum++]=*vp;if(G->kind==DG||G->kind==AG)for(j=0;j<G->vexnum;j++)G->adj[j][k].ArcVal=G->adj[k][j].ArcVal=0;

/*是不帶權的有向圖或無向圖*/elsefor(j=0;j<G->vexnum;j++){G->adj[j][k].ArcVal=INFINITY;G->adj[k][j].ArcVal=INFINITY;

/*是帶權的有向圖或無向圖*/}return(k);}

(4)向圖中增加一條弧

根據(jù)給定的弧或邊所依附的頂點，修改鄰接矩陣中所對應的數(shù)組元素。

int

AddArc(MGraph*G,ArcType*arc){intk,j;k=LocateVex(G,&arc->vex1);j=LocateVex(G,&arc->vex1);if(k==-1||j==-1){printf(“Arc’sVertexdonotexisted!\n”);return(-1);}if(G->kind==DG||G->kind==WDG){G->adj[k][j].ArcVal=arc->ArcVal;G->adj[k][j].ArcInfo=arc->ArcInfo;

/*是有向圖或帶權的有向圖*/}else{G->adj[k][j].ArcVal=arc->ArcVal;G->adj[j][k].ArcVal=arc->ArcVal;G->adj[k][j].ArcInfo=arc->ArcInfo;G->adj[j][k].ArcInfo=arc->ArcInfo;

/*是無向圖或帶權的無向圖,需對稱賦值*/}return(1);}7.2.2

鄰接鏈表法基本思想：對圖的每個頂點建立一個單鏈表，存儲該頂點所有鄰接頂點及其相關信息。每一個單鏈表設一個表頭結點。第i個單鏈表表示依附于頂點Vi的邊(對有向圖是以頂點Vi為頭或尾的弧)。

1結點結構與鄰接鏈表示例

鏈表中的結點稱為表結點，每個結點由三個域組成，如圖7-9(a)所示。其中鄰接點域(adjvex)指示與頂點Vi鄰接的頂點在圖中的位置(頂點編號)，鏈域(nextarc)指向下一個與頂點Vi鄰接的表結點，數(shù)據(jù)域(info)存儲和邊或弧相關的信息，如權值等。對于無權圖，如果沒有與邊相關的其他信息，可省略此域。

每個鏈表設一個表頭結點(稱為頂點結點)，由兩個域組成，如圖7-9(b)所示。鏈域(firstarc)指向鏈表中的第一個結點，數(shù)據(jù)域(data)

存儲頂點名或其他信息。adjvexinfonextarc表結點：datafirstarc頂點結點：圖7-9鄰接鏈表結點結構用鄰接鏈表存儲圖時，對無向圖，其鄰接鏈表是唯一的，如圖7-10所示；對有向圖，其鄰接鏈表有兩種形式，如圖7-11所示。圖7-10無向圖及其鄰接鏈表v1v2v3v4v501234MAX_VEX-1v1

v2v3

v4┇┇v5

213?02?0314?204?23?(a)有向圖v1v2v3v4v513?014?2?3?01234MAX_VEX-1v12v20?v33v41┇┇┇v51(b)正鄰接鏈表，出度直觀2?02?2?01234MAX_VEX-1v11v22v31v42┇┇┇v513?04?(c)逆鄰接鏈表，入度直觀圖7-11有向圖及其鄰接鏈表結構體定義，詳見P163鄰接表法的特點

◆

表頭向量中每個分量就是一個單鏈表的頭結點，分量個數(shù)就是圖中的頂點數(shù)目；

◆

在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲空間；

◆

在無向圖，頂點Vi的度是第i個鏈表的結點數(shù)；

◆

對有向圖可以建立正鄰接表或逆鄰接表。正鄰接表是以頂點Vi為出度(即為弧的起點)而建立的鄰接表；逆鄰接表是以頂點Vi為入度(即為弧的終點)而建立的鄰接表；

◆

在有向圖中，第i個鏈表中的結點數(shù)是頂點Vi的出(或入)度；求入(或出)度，須遍歷整個鄰接表；◆

在鄰接表上容易找出任一頂點的第一個鄰接點和下一個鄰接點；7.2.3

十字鏈表法

十字鏈表(OrthogonalList)是有向圖的另一種鏈式存儲結構，是將有向圖的正鄰接表和逆鄰接表結合起來得到的一種鏈表。在這種結構中，每條弧的弧頭結點和弧尾結點都存放在鏈表中，并將弧結點分別組織到以弧尾結點為頭(頂點)結點和以弧頭結點為頭(頂點)結點的鏈表中。這種結構的結點邏輯結構如圖7-12所示?；〗Y點tailvex

headvexinfohlink

tlink頂點結點Datafirstin

firstout圖7-12十字鏈表結點結構◆

data域：存儲和頂點相關的信息；◆

指針域firstin：指向以該頂點為弧頭的第一條弧所對應的弧結點；◆

指針域firstout：指向以該頂點為弧尾的第一條弧所對應的弧結點；◆

尾域tailvex：指示弧尾頂點在圖中的位置；◆

頭域headvex：指示弧頭頂點在圖中的位置；◆

指針域hlink：指向弧頭相同的下一條?。弧?/p>

指針域tlink：指向弧尾相同的下一條?。弧?/p>

Info域：指向該弧的相關信息；V0V1V2V30102∧2023∧∧30∧31∧32∧∧0213V0V1∧V2V3圖7-13有向圖的十字鏈表結構有向圖的十字鏈表結構結構體定義，詳見P1657.2.4

鄰接多重表

鄰接多重表(AdjacencyMultilist)是無向圖的另一種鏈式存儲結構。鄰接表是無向圖的一種有效的存儲結構，在無向圖的鄰接表中，一條邊(v,w)的兩個表結點分別初選在以v和w為頭結點的鏈表中，很容易求得頂點和邊的信息，但在涉及到邊的操作會帶來不便。鄰接多重表的結構和十字鏈表類似，每條邊用一個結點表示；鄰接多重表中的頂點結點結構與鄰接表中的完全相同，而表結點包括六個域如圖7-14所示。datafirstedge頂點結點圖7-14鄰接多重表的結點結構表結點markivex

ilink

jvex

jlinkinfo◆

Data域：存儲和頂點相關的信息；◆

指針域firstedge：指向依附于該頂點的第一條邊所對應的表結點；◆

標志域mark：用以標識該條邊是否被訪問過；◆

ivex和jvex域：分別保存該邊所依附的兩個頂點在圖中的位置；◆

info域：保存該邊的相關信息；◆

指針域ilink：指向下一條依附于頂點ivex的邊；◆

指針域jlink：指向下一條依附于頂點jvex的邊；

鄰接多重表與鄰接表的區(qū)別：

后者的同一條邊用兩個表結點表示，而前者只用一個表結點表示；除標志域外，鄰接多重表與鄰接表表達的信息是相同的，因此，操作的實現(xiàn)也基本相似。圖7-15無向圖及其多重鄰接鏈表v1v2v3v4v1v2v3v401230102∧21∧230∧3∧結構體定義，詳見P166-1677.3

圖的遍歷

圖的遍歷(TraveringGraph)：從圖的某一頂點出發(fā)，訪遍圖中的其余頂點，且每個頂點僅被訪問一次。圖的遍歷算法是各種圖的操作的基礎。

◆

復雜性：圖的任意頂點可能和其余的頂點相鄰接，可能在訪問了某個頂點后，沿某條路徑搜索后又回到原頂點。

◆

解決辦法：在遍歷過程中記下已被訪問過的頂點。設置一個輔助向量Visited[1…n](n為頂點數(shù))，其初值為0，一旦訪問了頂點vi后，使Visited[i]為1或為訪問的次序號。圖的遍歷算法有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)結構是(正)鄰接鏈表。7.3.1深度優(yōu)先搜索算法深度優(yōu)先搜索(DepthFirstSearch--DFS)遍歷類似樹的先序遍歷，是樹的先序遍歷的推廣。1

算法思想

設初始狀態(tài)時圖中的所有頂點未被訪問，則：⑴

從圖中某個頂點vi出發(fā)，訪問vi；然后找到vi的一個鄰接頂點vi1；⑵從vi1出發(fā)，深度優(yōu)先搜索訪問和vi1相鄰接且未被訪問的所有頂點；⑶轉⑴

，直到和vi相鄰接的所有頂點都被訪問為止⑷繼續(xù)選取圖中未被訪問頂點vj作為起始頂點，轉(1)，直到圖中所有頂點都被訪問為止。圖7-17無向圖深度優(yōu)先搜索遍歷(a)無向圖Gv1v2v3v4v5(b)G的鄰接鏈表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21?20?01?4?3?

無向圖的深度優(yōu)先搜索遍歷示例(紅色箭頭)。某種DFS次序是：v1→

v3→

v2→

v4→

v5由算法思想知，這是一個遞歸過程。因此，先設計一個從某個頂點(編號)為v0開始深度優(yōu)先搜索的函數(shù)，便于調用。代碼詳見P1692算法實現(xiàn)3算法分析

遍歷時，對圖的每個頂點至多調用一次DFS函數(shù)。其實質就是對每個頂點查找鄰接頂點的過程，取決于存儲結構。當圖有e條邊，其時間復雜度為O(e)，總時間復雜度為O(n+e)。7.3.2廣度優(yōu)先搜索算法

廣度優(yōu)先搜索(BreadthFirstSearch--BFS)遍歷類似樹的按層次遍歷的過程。1

算法思想設初始狀態(tài)時圖中的所有頂點未被訪問，則：⑴

從圖中某個頂點vi出發(fā)，訪問vi；⑵訪問vi的所有相鄰接且未被訪問的所有頂點vi1，vi2，…，vim；⑶以vi1，vi2，…，vim的次序，以vij(1≦j≦m)依此作為vi，轉⑴；⑷繼續(xù)選取圖中未被訪問頂點vk作為起始頂點，轉⑴，直到圖中所有頂點都被訪問為止。有向圖的廣度優(yōu)先搜索遍歷示例(紅色箭頭)。上述圖的BFS次序是：v1→

v2→

v4→

v3→

v5(b)G’的正鄰接鏈表13?014?2?3?01234MAX_VEX-1v12v20?v33v41┇┇┇v51圖7-18有向圖廣度優(yōu)先搜索遍歷(a)有向圖G’v1v2v3v4v5

2

算法實現(xiàn)

為了標記圖中頂點是否被訪問過，同樣需要一個訪問標記數(shù)組；其次，為了依此訪問與vi相鄰接的各個頂點，需要附加一個隊列來保存訪問vi的相鄰接的頂點。代碼實現(xiàn)詳見P170。

3算法分析用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索算法遍歷圖的唯一區(qū)別是鄰接點搜索次序不同，因此，廣度優(yōu)先搜索算法遍歷圖的總時間復雜度為O(n+e)。7.4

圖的連通性問題

本節(jié)所討論的內容是圖的遍歷算法的具體應用。7.4.1無向圖的連通分量與生成樹1無向圖的連通分量和生成樹

對于無向圖，對其進行遍歷時：◆

若是連通圖：僅需從圖中任一頂點出發(fā)，就能訪問圖中的所有頂點；◆

若是非連通圖：需從圖中多個頂點出發(fā)。每次從一個新頂點出發(fā)所訪問的頂點集序列恰好是各個連通分量的頂點集；(a)無向圖Gv1v2v3v4v5(b)G的鄰接鏈表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21?20?01?4?3?圖7-19無向圖及深度優(yōu)先生成森林(c)深度優(yōu)先生成森林v1v2v3v4v5無向非連通圖，按圖中給定的鄰接表進行深度優(yōu)先搜索遍歷，2次調用DFS所得到的頂點訪問序列集是：

{v1,v3,v2}和{v4,v5}

⑴若G=(V,E)是無向連通圖，頂點集和邊集分別是V(G)，E(G)。若從G中任意點出發(fā)遍歷時，E(G)被分成兩個互不相交的集合：T(G)：遍歷過程中所經過的邊的集合；B(G)：遍歷過程中未經過的邊的集合；顯然：E(G)=T(G)∪B(G)，T(G)∩B(G)=?

顯然，圖G’=(V,T(G))是G的極小連通子圖，且G’是一棵樹。G’稱為圖G的一棵生成樹。從任意點出發(fā)按DFS算法得到生成樹G’稱為深度優(yōu)先生成樹；按BFS算法得到的G’稱為廣度優(yōu)先生成樹。

⑵

若G=(V,E)是無向非連通圖，對圖進行遍歷時得到若干個連通分量的頂點集：V1(G),V2(G),…,Vn(G)和相應所經過的邊集：T1(G),T2(G),…,Tn(G)

則對應的頂點集和邊集的二元組：Gi=(Vi(G),Ti(G))(1≦i≦n)是對應分量的生成樹，所有這些生成樹構成了原來非連通圖的生成森林。說明：當給定無向圖要求畫出其對應的生成樹或生成森林時，必須先給出相應的鄰接表，然后才能根據(jù)鄰接表畫出其對應的生成樹或生成森林。7.4.2

有向圖的強連通分量

對于有向圖，在其每一個強連通分量中，任何兩個頂點都是可達的。VG，與V可相互到達的所有頂點就是包含V的強連通分量的所有頂點。設從V可到達(以V為起點的所有有向路徑的終點)的頂點集合為T1(G)，而到達V(以V為終點的所有有向路徑的起點)的頂點集合為T2(G)，則包含V的強連通分量的頂點集合是：

T1(G)∩T2(G)。

求有向圖G的強連通分量的基本步驟是：⑴對G進行深度優(yōu)先遍歷，生成G的深度優(yōu)先生成森林T。⑵對森林T的頂點按中序遍歷順序進行編號。⑶

改變G中每一條弧的方向，構成一個新的有向圖G’。⑷

按⑵中標出的頂點編號，從編號最大的頂點開始對G’進行深度優(yōu)先搜索，得到一棵深度優(yōu)先生成樹。若一次完整的搜索過程沒有遍歷G’的所有頂點，則從未訪問的頂點中選擇一個編號最大的頂點，由它開始再進行深度優(yōu)先搜索，并得到另一棵深度優(yōu)先生成樹。在該步驟中，每一次深度優(yōu)先搜索所得到的生成樹中的頂點就是G的一個強連通分量的所有頂點。

⑸

重復步驟⑷，直到G’中的所有頂點都被訪問。dacfeb(a)有向圖G654321dacfeb(b)執(zhí)行步驟(1)和(2)acdfeb(c)執(zhí)行步驟(3)adcbef(d)執(zhí)行步驟(4)和(5)圖7-20利用深度優(yōu)先搜索求有向圖的強連通分量

在算法實現(xiàn)時，建立一個數(shù)組in_order[n]存放深度優(yōu)先生成森林的中序遍歷序列。對每個頂點v，在調用DFS函數(shù)結束時，將頂點依次存放在數(shù)組in_order[n]中。圖采用十字鏈表作為存儲結構最合適。7.4.3

最小生成樹

如果連通圖是一個帶權圖，則其生成樹中的邊也帶權，生成樹中所有邊的權值之和稱為生成樹的代價。

最小生成樹(MinimumSpanningTree)：帶權連通圖中代價最小的生成樹稱為最小生成樹。最小生成樹在實際中具有重要用途，如設計通信網。設圖的頂點表示城市，邊表示兩個城市之間的通信線路，邊的權值表示建造通信線路的費用。n個城市之間最多可以建n(n-1)/2條線路，如何選擇其中的n-1條，使總的建造費用最低?基本原則是：◆

盡可能選取權值最小的邊，但不能構成回路；◆

選擇n-1條邊構成最小生成樹。以上的基本原則是基于MST的如下性質：設G=(V，E)是一個帶權連通圖，U是頂點集V的一個非空子集。若u∈U

，v∈V-U，且(u,v)是U中頂點到V-U中頂點之間權值最小的邊，則必存在一棵包含邊(u,v)的最小生成樹。

構造最小生成樹的算法有許多，基本原則是：

設圖G的任何一棵最小生成樹都不包含邊(u,v)。設T是G的一棵生成樹，則T是連通的，從u到v必有一條路徑(u,…,v)，當將邊(u,v)加入到T中時就構成了回路。則路徑(u,…,v)中必有一條邊(u’,v’)，滿足u’∈U，v’∈V-U。刪去邊(u’,v’)便可消除回路，同時得到另一棵生成樹T’。

由于(u,v)是U中頂點到V-U中頂點之間權值最小的邊，故(u,v)的權值不會高于(u’,v’)的權值，T’的代價也不會高于T，T’是包含(u,v)的一棵最小生成樹，與假設矛盾。證明：用反證法證明。7.5.1普里姆(Prim)算法

從連通網N=(U，E)中找最小生成樹T=(U，TE)

。1算法思想(P174頁)⑴

若從頂點v0出發(fā)構造，U={v0}，TE={}；⑵

先找權值最小的邊(u，v)，其中u∈U且v∈V-U，并且子圖不構成環(huán)，則U=U∪{v}，TE=TE∪{(u，v)}

；⑶

重復⑵

，直到U=V為止。則TE中必有n-1條邊，

T=(U，TE)就是最小生成樹。v1v3v2v4v54857121136(a)v2v45(b)(c)v53v2v45(d)v14v53v2v45v36(e)v14v53v2v45圖7-21按prime算法從v2出發(fā)構造最小生成樹的過程

iclosedge01234UV-UKadjvexlwcostv28v2

7v25v212{v2}{v1,v3,v4,v5}3adjvexlwcostv44v27v20v43{v2,v4}{v1,v3,v5}4adjvexlwcostv44v56v20v40{v2,v4,v5}{v1,v3}0adjvexlwcostv40v56v20v40{v2,v4,v5,v1}{v3}2adjvexlwcostv40v50v20v40{v2,v4,v5,v1,v3}{}表7-1構造過程中輔組數(shù)組closedge中各分量的值的變化情況

算法實現(xiàn)：P175

設帶權連通圖有n個頂點，則算法的主要執(zhí)行是二重循環(huán)：求closedge中權值最小的邊，頻度為n-1；

修改closedge數(shù)組，頻度為n。因此，整個算法的時間復雜度是O(n2)，與邊的數(shù)目無關。算法分析：7.5.2克魯斯卡爾(Kruskal)算法1

算法思想（P176）設G=(V,E)是具有n個頂點的連通網，T=(U,TE)是其最小生成樹。初值：U=V，TE={}。對G中的邊按權值大小從小到大依次選取。⑴

選取權值最小的邊(vi，vj)，若邊(vi，vj)加入到TE后形成回路，則舍棄該邊(邊(vi，vj)；否則，將該邊并入到TE中，即TE=TE∪{(vi，vj)}。⑵

重復⑴

，直到TE中包含有n-1條邊為止。v1v3v2v4v54857121136(a)(b)3v5v4v36(e)v14v53v2v45圖7-22按kruskal算法構造最小生成樹的過程(c)v143v5v4(d)v25v143v5v4設帶權連通圖有n個頂點，e條邊，則算法的主要執(zhí)行是：◆

Vset數(shù)組初始化：時間復雜度是O(n)；◆

邊表按權值排序：若采用堆排序或快速排序，選擇最小邊時間復雜度是O(㏒e)；◆

又生成每個連通分量，判斷回路；整個算法的時間復雜度是O(e㏒e)。算法分析：7.6

有向無環(huán)圖及其應用

有向無環(huán)圖(DirectedAcyclingGraph)：是圖中沒有回路(環(huán))的有向圖。是一類具有代表性的圖，主要用于研究工程項目的工序問題、工程時間進度問題等。一個工程(project)都可分為若干個稱為活動(active)的子工程(或工序)，各個子工程受到一定的條件約束：某個子工程必須開始于另一個子工程完成之后；整個工程有一個開始點(起點)和一個終點。人們關心：◆

工程能否順利完成?影響工程的關鍵活動是什么?◆

估算整個工程完成所必須的最短時間是多少?對工程的活動加以抽象：圖中頂點表示活動，有向邊表示活動之間的優(yōu)先關系，這樣的有向圖稱為頂點表示活動的網(ActivityOnVertexNetwork

，AOV網)。AOV網7.6.1拓撲排序1

定義拓撲排序(TopologicalSort)：由某個集合上的一個偏序得到該集合上的一個全序的操作。◆

集合上的關系：集合A上的關系是從A到A的關系(AA)?！?/p>

關系的自反性：若a∈A有(a，a)∈R，稱集合A上的關系R是自反的?！?/p>

關系的對稱性：如果對于a，b∈A，只要有(a，b)∈R就有(b，a)∈R

，稱集合A上的關系R是對稱的。◆

關系的對稱性與反對稱性：如果對于a，b∈A

，只要有(a，b)∈R就有(b，a)∈R

，稱集合A上的關系R是對稱的。如果對于a，b∈A

，僅當a=b時有(a，b)∈R和(b，a)∈R

，稱集合A上的關系R是反對稱的?！?/p>

關系的傳遞性：若a，b，c∈A，若(a，b)∈R，并且(b，c)∈R

，則(a，c)∈R，稱集合A上的關系R是傳遞的?！?/p>

偏序：若集合A上的關系R是自反的，反對稱的和傳遞的，則稱R是集合A上的偏序關系。◆

全序：設R是集合A上的偏序關系，a，b∈A，必有aRb或bRa，則稱R是集合A上的全序關系。

即偏序是指集合中僅有部分元素之間可以比較，而全序是指集合中任意兩個元素之間都可以比較。在AOV網中，若有有向邊<i,j>，則i是j的直接前驅，j是i的直接后繼；推而廣之，若從頂點i到頂點j有有向路徑，則i是j的前驅，j是i的后繼。在AOV網中，不能有環(huán)，否則，某項活動能否進行是以自身的完成作為前提條件。

檢查方法：對有向圖的頂點進行拓撲排序，若所有頂點都在其拓撲有序序列中，則無環(huán)。

有向圖的拓撲排序：構造AOV網中頂點的一個拓撲線性序列(v’1,v’2,?,v’n)，使得該線性序列不僅保持原來有向圖中頂點之間的優(yōu)先關系，而且對原圖中沒有優(yōu)先關系的頂點之間也建立一種(人為的)優(yōu)先關系。

2

拓撲排序算法算法思想①

在AOV網中選擇一個沒有前驅的頂點且輸出；

②

在AOV網中刪除該頂點以及從該頂點出發(fā)的(以該頂點為尾的弧)所有有向弧(邊)；③

重復①、②，直到圖中全部頂點都已輸出(圖中無環(huán))或圖中不存在無前驅的頂點(圖中必有環(huán))。3算法實現(xiàn)說明◆采用正鄰接鏈作為AOV網的存儲結構；◆

設立堆棧，用來暫存入度為0的頂點；◆刪除頂點以它為尾的?。夯☆^頂點的入度減1。算法實現(xiàn)v1v2v3v4v5v6(a)有向圖(b)輸出v1后v4v2v3v5v6圖7-23有向圖的拓撲排序過程(c)輸出v6后v4v2v3v5(d)輸出v4后v2v3v5(e)輸出v3后v2v5(1)

統(tǒng)計各頂點入度的函數(shù)voidcount_indegree(ALGraph*G){intk;LinkNode*p;for(k=0;k<G->vexnum;k++)G->adjlist[k].indegree=0;/*頂點入度初始化*/for(k=0;k<G->vexnum;k++){p=G->adjlist[k].firstarc;while(p!=NULL)/*頂點入度統(tǒng)計*/{G->adjlist[p->adjvex].indegree++;p=p->nextarc;}}}3算法實現(xiàn)說明◆采用正鄰接鏈作為AOV網的存儲結構；◆設立堆棧，用來暫存入度為0的頂點；◆刪除頂點以它為尾的弧：弧頭頂點的入度減1。

(2)

拓撲排序算法int

Topologic_Sort(ALGraph*G,int

topol[])/*頂點的拓撲序列保存在一維數(shù)組topol中*/{intk,no,vex_no,top=0,count=0,boolean=1;int

stack[MAX_VEX];/*用作堆棧*/LinkNode*p;count_indegree(G);/*統(tǒng)計各頂點的入度*/for(k=0;k<G->vexnum;k++)if(G->adjlist[k].indegree==0)stack[++top]=G->adjlist[k].data;do{if(top==0)boolean=0;else{no=stack[top--];/*棧頂元素出棧*/

topl[++count]=no;/*記錄頂點序列*/p=G->adjlist[no].firstarc;while(p!=NULL)/*刪除以頂點為尾的弧*/{vex_no=p->adjvex;G->adjlist[vex_no].indegree--;if(G->adjlist[vex_no].indegree==0)stack[++top]=vex_no;p=p->nextarc;}}}while(boolean==0);if(count<G->vexnum)return(-1);elsereturn(1);}算法分析：

設AOV網有n個頂點，e條邊，則算法的主要執(zhí)行是：◆

統(tǒng)計各頂點的入度：時間復雜度是O(n+e)；◆

入度為0的頂點入棧：時間復雜度是O(n)；◆

排序過程：頂點入棧和出棧操作執(zhí)行n次，入度減1的操作共執(zhí)行e次，時間復雜度是O(n+e)；

因此，整個算法的時間復雜度是O(n+e)。7.6.2關鍵路徑(CriticalPath)

與AOV網相對應的是AOE(ActivityOnEdge)，是邊表示活動的有向無環(huán)圖，如圖7-24所示。圖中頂點表示事件(Event)，每個事件表示在其前的所有活動已經完成，其后的活動可以開始；弧表示活動，弧上的權值表示相應活動所需的時間或費用。v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2圖7-24一個AOE網

1

與AOE有關的研究問題◆

完成整個工程至少需要多少時間?◆

哪些活動是影響工程進度(費用)的關鍵?

工程完成最短時間：從起點到終點的最長路徑長度(路徑上各活動持續(xù)時間之和)。長度最長的路徑稱為關鍵路徑，關鍵路徑上的活動稱為關鍵活動。關鍵活動是影響整個工程的關鍵。設v0是起點，從v0到vi的最長路徑長度稱為事件vi的最早發(fā)生時間，即是以vi為尾的所有活動的最早發(fā)生時間。若活動ai是弧<j,k>，持續(xù)時間是dut(<j,k>)，設：◆e(i)：表示活動ai的最早開始時間；◆

l(i)：在不影響進度的前提下，表示活動ai的最晚開始時間；則l(i)-e(i)表示活動ai的時間余量，若l(i)-e(i)=0，表示活動ai是關鍵活動?！?/p>

ve(i)：表示事件vi的最早發(fā)生時間，即從起點到頂點vi的最長路徑長度；

◆

vl(i)：表示事件vi的最晚發(fā)生時間。則有以下關系：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)7-10j=0，表示vj是起點Max{ve(i)+dut(<i,j>)|<vi,vj>是網中的弧}ve(j)=7-2

含義是：源點事件的最早發(fā)生時間設為0；除源點外，只有進入頂點vj的所有弧所代表的活動全部結束后，事件vj才能發(fā)生。即只有vj的所有前驅事件vi的最早發(fā)生時間ve(i)計算出來后，才能計算ve(j)。

方法是：對所有事件進行拓撲排序，然后依次按拓撲順序計算每個事件的最早發(fā)生時間。ve(n-1)j=n-1，表示vj是終點Min{vl(k)-dut(<j,k>)|<vj,vk>是網中的弧}vl(j)=7-3

含義是：只有vj的所有后繼事件vk的最晚發(fā)生時間vl(k)計算出來后，才能計算vl(j)。

方法是：按拓撲排序的逆順序，依次計算每個事件的最晚發(fā)生時間。

2

求AOE中關鍵路徑和關鍵活動⑴

算法思想①利用拓撲排序求出AOE網的一個拓撲序列；

②從拓撲排序的序列的第一個頂點(源點)開始，按拓撲順序依次計算每個事件的最早發(fā)生時間ve(i)

；

③從拓撲排序的序列的最后一個頂點(匯點)開始，按逆拓撲順序依次計算每個事件的最晚發(fā)生時間vl(i)

；

對于圖7-24的AOE網，處理過程如下：◆

拓撲排序的序列是：(v0,v1,v2,v3,

v4,v5,v6,v7,v8)頂點v0v1v2v3v4v5v6v7v8ve(i)0310122217202833vl(i)0910232217312833表7-2圖7-24的ve(i)和vl(i)的值◆

根據(jù)計算ve(i)的公式(7-2)和計算vl(i)的公式(7-3)，計算各個事件的ve(i)和vl(i)值，如表7-2所示?！?/p>

根據(jù)關鍵路徑的定義，知該AOE網的關鍵路徑是：(v0,v2,v4,v7,v8)和(v0,v2,v5,v7,v8)?！?/p>

關鍵路徑活動是：<v0,v2>，<v2,v4>，<v2,v5>，<v4,v7>，<v5,v7>，<v5,v8>。⑵

算法實現(xiàn)voidcritical_path(ALGraph*G){intj,k,m;LinkNode*p;if(Topologic_Sort(G)==-1)printf(“\nAOE網中存在回路，錯誤!!\n\n”);else{for(j=0;j<G->vexnum;j++)

ve[j]=0;/*事件最早發(fā)生時間初始化*/for(m=0;m<G->vexnum;m++){j=topol[m];p=G->adjlist[j].firstarc;for(;p!=NULL;p=p->nextarc)

{k=p->adjvex;if(ve[j]+p->weight>ve[k])

ve[k]=ve[j]+p->weight;}}/*計算每個事件的最早發(fā)生時間ve值*/for(j=0;j<G->vexnum;j++)

vl[j]=ve[j];/*事件最晚發(fā)生時間初始化*/for(m=G->vexnum-1;m>=0;m--){j=topol[m];p=G->adjlist[j].firstarc;for(;p!=NULL;p=p->nextarc){k=p->adjvex;if(vl[k]-p->weight<vl[j])

vl[j]=vl[k]-p->weight;

}}/*計算每個事件的最晚發(fā)生時間vl值*/for(m=0;m<G->vexnum;m++){p=G->adjlist[m].firstarc;for(;p!=NULL;p=p->nextarc){k=p->adjvex;if((ve[m]+p->weight)==vl[k])

printf(“<%d,%d>,m,j”);}}/*輸出所有的關鍵活動*/}/*endofelse*/}⑶

算法分析

設AOE網有n個事件，e個活動，則算法的主要執(zhí)行是：◆

進行拓撲排序：時間復雜度是O(n+e)；◆

求每個事件的ve值和vl值：時間復雜度是O(n+e)；◆

根據(jù)ve值和vl值找關鍵活動：時間復雜度是O(n+e)；

因此，整個算法的時間復雜度是O(n+e)。7.7

最短路徑若用帶權圖表示交通網，圖中頂點表示地點，邊代表兩地之間有直接道路，邊上的權值表示路程(或所花費用或時間)。從一個地方到另一個地方的路徑長度表示該路徑上各邊的權值之和。問題：◆

兩地之間是否有通路?◆

在有多條通路的情況下，哪條最短?

考慮到交通網的有向性，直接討論的是帶權有向圖的最短路徑問題，但解決問題的算法也適用于無向圖。將一個路徑的起始頂點稱為