第七章圖7.1圖的定義和術(shù)語

圖是一種數(shù)據(jù)結(jié)構(gòu)，其形式化定義為：

Graph=(V,R)其中，

V={x|x∈dataobject}//

頂點的有窮非空集合

R={VR}

//V上的關(guān)系的有窮集合

VR={<x,y>|x,y∈V}

<x,y>表示從

x到y(tǒng)

的一條弧。稱

y為弧頭，x為弧尾。

由頂點和弧構(gòu)成的圖稱為有向圖。其中V1={A,B,C,D,E}VR1={<A,B>,<A,E>,<B,C>,<C,D>,<D,A>,<D,B>,<E,C>}例:G1=(V1,{VR1})EACBD

若<x,y>VR

必有<y,x>VR,則稱頂點x和頂點y之間存在一條邊，并以(x,y)表示之。由頂點和邊構(gòu)成的圖稱作無向圖。V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(B,F),(C,D),(C,F),(D,F)}例:G2=(V2,{VR2})EADBCF設(shè)圖G=(V,{VR})

和圖

G=(V,{VR}),且

VV,VRVR,則稱

G

為

G

的子圖.159781132

弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng).EACBDACBD假設(shè)圖中有n個頂點，e條邊(弧)，則含有e=n(n-1)/2

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

條弧的有向圖稱作有向完全圖;

有很少條邊或弧(如e<nlogn)的圖稱作稀疏圖,反之稱作稠密圖。

假若頂點

v和頂點

w

之間存在一條邊，則稱頂點

v和

w互為鄰接點，例如:TD(B)=3TD(A)=2邊(v,w)

和頂點

v

和

w

相關(guān)聯(lián).

頂點

v

的度定義為和

v

相關(guān)聯(lián)的邊的數(shù)目.EADBCF頂點

v

的出度:以頂點

v

為弧尾的弧的數(shù)目;頂點

v

的入度:以頂點

v

為弧頭的弧的數(shù)目。頂點的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3對于有向圖：EACBD設(shè)圖G=(V,{VR})的一個頂點序列(u=vi,0,vi,1,…,vi,m=w)中，(vi,j-1,vi,j)VR1≤j≤m,則稱該序列為從頂點u

到頂點w之間的一條路徑,路徑上邊的數(shù)目稱作路徑長度。如:

從

A

到

D

長度為

3

的路徑（A,B,C,D）簡單路徑：指序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路：指序列中第一個頂點和最后一個頂點相同，而其余頂點不重復(fù)出現(xiàn)的路徑。EACBD若圖

G

中任意兩個頂點之間都有路徑相通,則稱此圖為連通圖;若無向圖為非連通圖,則圖中各個極大連通子圖稱作此圖的連通分量。EADBCFEADBCF

對有向圖，若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為強連通圖.否則有向圖的各個極大強連通子圖稱作它的強連通分量.EACBDEACBD

設(shè)一個連通圖有

n個頂點，圖中全部頂點和

n-1條邊構(gòu)成的極小連通子圖稱為此連通圖的生成樹.

對于非連通圖,由各個連通分量的生成樹構(gòu)成的集合稱為該非連通圖的生成森林.EADBCF無論頂點用字母還是序號表示，均代表著頂點的全部信息。

為了存儲及操作的方便，需要人為地為圖中所有頂點規(guī)定一個線性序列

V1,V2,…,Vn，頂點在該序列中的位置(序號)稱為頂點在圖中的位置(序號)。EACBD51324結(jié)構(gòu)的建立和銷毀對鄰接點的操作插入和刪除弧對頂點的訪問操作遍歷插入或刪除頂點基本操作CreatGraph(&G,V,VR);//按定義(V,VR)構(gòu)造圖DestroyGraph(&G);//銷毀圖結(jié)構(gòu)的建立和銷毀對頂點的訪問操作LocateVex(G,u);

//若G中存在頂點u，則返回該頂點在

//圖中“位置”；否則返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//對v賦值value。對鄰接點的操作FirstAdjVex(G,v);

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

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

//在圖G中增添新頂點v。DeleteVex(&G,v);//刪除G中頂點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());//從頂點v起深度優(yōu)先遍歷圖G，并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());

//從頂點v起廣度優(yōu)先遍歷圖G，并對每//個頂點調(diào)用函數(shù)Visit一次且僅一次。7.2圖的存儲結(jié)構(gòu)圖的任何一種存儲結(jié)構(gòu)都需要存儲兩方面的信息：和頂點相關(guān)的信息；如頂點名稱等。與?。ɑ蜻叄┫嚓P(guān)的信息，即體現(xiàn)頂點之間鄰接關(guān)系的信息。如弧是否存在的信息、弧上所帶的權(quán)等。7.2.1

數(shù)組表示法（鄰接矩陣表示法）鄰接矩陣的定義：設(shè)圖G=(V,{VR})是有n(n

1)個頂點的圖，則G的鄰接矩陣A是具有如下性質(zhì)的n階方陣：A[i,j]=0否則1若<i,j>或(i,j)VR{例：無向圖的鄰接矩陣為對稱矩陣EADBCF有向圖的鄰接矩陣通常是非對稱矩陣例：EACBD網(wǎng)的鄰接矩陣定義：設(shè)圖G=(V,{VR})是有n(n

1)個頂點的網(wǎng)，則G的鄰接矩陣A是具有如下性質(zhì)的n階方陣：A[i,j]=∞

否則Wij

若<i,j>或(i,j)VR{?。ㄟ叄┥纤鶐У臋?quán)比圖中任何權(quán)都大的數(shù)，常用計算機所允許的最大數(shù)來表示例：159781132EACBD//-----圖的數(shù)組(鄰接矩陣)存儲表示

-----#defineINFINITYINT_MAX//

最大值

#defineMAX_VERTEX_NUM

20//

最大頂點個數(shù)typedef

enum{DG,DN,UDG,UDN}GraphKind;數(shù)組表示法的類C語言描述typedef

struct

ArcCell{//弧的定義

VRType

adj;//

頂點關(guān)系域

InfoType

*info;//

弧的相關(guān)信息指針

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef

struct{//圖的定義

VertexType

vexs[MAX_VERTEX_NUM];//

頂點向量

AdjMatrixarcs;//

鄰接矩陣

int

vexnum,arcnum;//

圖的頂點數(shù)和弧數(shù)

GraphKindkind;//

圖的種類標志}MGraph;7.2.2鄰接表無向圖的鄰接表

A14

B045

C35

D25

E01

F123012345頂點表邊表EADBCF有向圖的鄰接表在有向圖的鄰接表中不易找到指向該頂點的弧。

A14

B2

C3

D01

E201234EACBD有向圖的逆鄰接表在有向圖的逆鄰接表中，對每個頂點，鏈接的是指向該頂點的弧。

A3

B03

C14

D2

E001234EACBD//-----圖的鄰接表存儲表示

-----#defineMAX_VERTEX_NUM

20//

最大頂點個數(shù)typedef

struct

ArcNode{

int

adjvex;//

該弧所指向的頂點的序號

struct

ArcNode

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

InfoType

*info;//該弧相關(guān)信息的指針

}ArcNode;鄰接表的類C語言描述adjvexinfonextarc弧的結(jié)點結(jié)構(gòu)typedef

struct

VNode{

VertexTypedata;//

頂點信息

ArcNode

*firstarc;//指向以該頂點為弧尾的

//第一條弧的指針

}VNode,AdjList[MAX_VERTEX_NUM];typedef

struct{

AdjListvertices;

int

vexnum,arcnum;//

圖的頂點數(shù)和弧數(shù)

intkind;//

圖的種類標志}ALGraph;

datafirstarc頂點的結(jié)點結(jié)構(gòu)//圖的結(jié)構(gòu)定義圖的存儲結(jié)構(gòu)的選擇對于稀疏圖，用鄰接表比用數(shù)組表示法節(jié)省存儲空間，當和邊(或弧)相關(guān)的信息較多時更是如此。對于稠密圖(尤其是無向稠密圖)，用數(shù)組表示法比較合算。設(shè)圖中有n個頂點，e條邊（或?。?，則鄰接表的存儲量為：O(n+e)(有向圖)

O(n+2e)(無向圖)數(shù)組表示法的存儲量為：O(n+n2)存儲結(jié)構(gòu)的選擇通常需考慮兩方面的因素：其一是存儲量的大小，其二是操作的效率及其實現(xiàn)的方便程度。1.判定無向圖中任意兩個頂點vi和vj

之間是否有邊相連。

2.檢測有向圖中共有多少條弧。

3.統(tǒng)計有向圖中某頂點vi的出度。

例：對于下列算法設(shè)計問題選擇存儲結(jié)構(gòu)。tailvexheadvexhlinktlinkinfo弧尾位置弧頭位置指向弧頭相同的下一條弧指向弧尾相同的下一條弧弧的相關(guān)信息指針弧結(jié)點有向圖的另一種鏈式存儲結(jié)構(gòu)?？梢钥醋魇青徑颖砗湍驵徑颖硐嘟Y(jié)合的一種鏈表。7.2.3

十字鏈表指向以該頂點為尾的第一個弧結(jié)點

datafirstin

firstout頂點結(jié)點指向以該頂點為頭的第一個弧結(jié)點頂點數(shù)據(jù)//-----有向圖的十字鏈表存儲表示

-----#defineMAX_VERTEX_NUM

20//

最大頂點個數(shù)typedef

struct

ArcBox{//

弧結(jié)點

int

tailvex,headvex;//

該弧的尾頂點和頭頂點的位置

struct

ArcBox

*hlink,*tlink;//弧頭相同和弧尾相同的弧結(jié)點的鏈域

InfoType

*info;//該弧相關(guān)信息的指針

}ArcBox;十字鏈表的類C語言描述tailvexheadvexhlinktlinkinfotypedef

struct

VexNode{//

頂點結(jié)點

VertexTypedata;//

頂點信息

ArcBox

*firstin,*firstout;//分別指向該頂點第一條入弧和出弧}VexNode;typedef

struct{

VexNode

xlist[MAX_VERTEX_NUM];//表頭向量

int

vexnum,arcnum;//

有向圖的頂點數(shù)和弧數(shù)}OLGraph;

datafirstin

firstout無向圖的另一種鏈式存儲結(jié)構(gòu)。無向圖中的一條邊在鄰接表中用兩個結(jié)點表示，而在鄰接多重表中只需一個結(jié)點。若在無向圖的應(yīng)用問題中需要對邊進行某種操作，如對已被搜索過的邊做記號或刪除一條邊等，則采用鄰接多重表作存儲結(jié)構(gòu)更為適宜。7.2.4

鄰接多重表markivexilinkjvexjlinkinfo標志域該邊依附的兩個頂點在圖中的位置指向下一條依附于頂點ivex

的邊邊的相關(guān)信息指針邊結(jié)點指向下一條依附于頂點jvex

的邊

datafirstedge頂點結(jié)點指向第一條依附于該頂點的邊頂點數(shù)據(jù)//-----無向圖的鄰接多重表存儲表示

-----#defineMAX_VERTEX_NUM

20//

最大頂點個數(shù)typedef

enum{unvisited,visited}VisitIf;typedef

struct

EBox{//

邊結(jié)點

VisitIfmark;//訪問標記

int

ivex,jvex;//該邊依附的兩個頂點的位置

struct

EBox

*ilink,*jlink;

//指向依附于相應(yīng)頂點的下一條邊的指針

InfoType

*info;//該邊信息指針}EBox

鄰接多重表的類C語言描述markivexilinkjvexjlinkinfotypedef

struct

VexBox{//

頂點結(jié)點

VertexTypedata;//

頂點信息

EBox

*firstedge;//指向第一條依附于該頂點的邊}VexBox;typedef

struct{

VexBox

adjmulist[MAX_VERTEX_NUM];//表頭向量

int

vexnum,edgenum;//

無向圖的頂點數(shù)和邊數(shù)}AMLGraph;

datafirstedge7.3圖的遍歷圖的遍歷

從圖中某個頂點出發(fā)系統(tǒng)地訪問圖中所有頂點，使得每個頂點僅被訪問一次，這一過程稱作圖的遍歷。深度優(yōu)先搜索廣度優(yōu)先搜索從圖中某個頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到。連通圖的深度優(yōu)先搜索遍歷7.3.1深度優(yōu)先搜索Vw1SG1SG2SG3W1、W2和W3

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

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

若該鄰接點Wi未被訪問，

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

G進行深度優(yōu)先遍歷

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

visited[v]=FALSE;//訪問標志數(shù)組初始化

for(v=0;v<G.vexnum;++v)//選出發(fā)點

if(!visited[v])DFS(G,v);//從尚未訪問的頂點v出發(fā)深度優(yōu)先遍歷圖G}//DFSTraverse算法7.4

abchdekfgFFFFFFFFFTTTTTTTTTachdfkebgachkfedbg訪問標志:訪問次序:例如:012345678類似于樹的按層次遍歷，從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。7.3.2廣度優(yōu)先搜索Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w4對于連通圖，廣度優(yōu)先搜索遍歷圖的過程是以V

為起始點，由近至遠，依次訪問和V

有路徑相通且路徑長度為1,2,...

的頂點。訪問次序:Vw1w2w8w7w3w5

w6w4voidBFSTraverse(GraphG,Status(*Visit)(intv)){//對圖

G進行廣度優(yōu)先遍歷

//算法中使用輔助隊列Q和訪問標志數(shù)組visitedfor(v=0;v<G.vexnum;++v)

visited[v]=FALSE;//訪問標志數(shù)組初始化

InitQueue(Q);for(v=0;v<G.vexnum;++v)if(!visited[v]){

visited[v]=TRUE;Visit(v);

EnQueue(Q,v);算法7.6

while(!QueueEmpty(Q)){

DeQueue(Q,u);//

隊頭元素出隊并置為ufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!visited[w]){

visited[w]=TRUE;Visit(w);

EnQueue(Q,w);}if}while}if}//BFSTraverse算法7.6

7.4圖的連通性問題連通圖(或強連通圖）的所有頂點加上遍歷過程中經(jīng)過的邊（或弧）可以構(gòu)成圖的生成樹，根據(jù)遍歷策略的不同，分別稱為深度優(yōu)先生成樹和廣度優(yōu)先生成樹。7.4.1生成樹和生成森林對于不連通的無向圖或不是強連通的有向圖，從任意一個頂點出發(fā)一般不能系統(tǒng)地訪問所有頂點，往往需要有兩個或兩個以上的出發(fā)點，這樣便得到了生成森林。例:深度優(yōu)先生成樹廣度優(yōu)先生成樹無向圖(p168)(p171)例:深度優(yōu)先生成森林無向圖假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？問題：7.4.3最小生成樹構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。該問題等價于：算法二：Kruskal（克魯斯卡爾）算法算法一：Prim（普里姆）算法連通網(wǎng)的所有生成樹中，各邊權(quán)的總和為最小的生成樹，稱作該連通網(wǎng)的最小生成樹（最小代價生成樹）。設(shè)連通網(wǎng)N=(V,E)，

其最小生成樹T=(U,TE)；算法從U={u0},TE=

開始，重復(fù)執(zhí)行以下操作：

1.

找一條權(quán)最小的邊(u,v)，u

U,v

V-U；

2.

將(u,v)并入集合TE，將v并入集合U直至U=V為止。Prim(普里姆)算法的基本思想:

Prim算法在生成樹的構(gòu)造過程中，圖中n個頂點分屬兩個集合：已落在生成樹上的頂點集U

和尚未落在生成樹上的頂點集V-U

，則應(yīng)在所有連通U中頂點和V-U中頂點的邊中選取權(quán)值最小的邊。abcdegf例如:195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67設(shè)置一個輔助數(shù)組，對當前V－U集中的每個頂點，記錄與頂點集U中頂點相連接的代價最小的邊：struct{

VertexType

adjvex;//U集中的頂點序號

VRType

lowcost;//邊的權(quán)值}

closedge[MAX_VERTEX_NUM];abcdegf195141827168213ae12dcb7aaa19141814例如:e12ee8168d3dd7213c55具體做法:首先構(gòu)造一個只含n個頂點的子圖T，然后選一條權(quán)值最小的邊，若在T中添加它后不產(chǎn)生回路，則在T中加上這條邊，否則舍棄之，選另一條權(quán)值最小的邊，如此重復(fù)，直至在T中加上第n-1條邊為止?？紤]問題的出發(fā)點:為使生成樹上邊的權(quán)值之和達到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄篴bcdegf195141827168213ae12dcbgf7148531621例如:7121819

Prim算法的時間復(fù)雜度為O(n2)，與網(wǎng)中的邊數(shù)無關(guān)，因此適用于求邊稠密的連通網(wǎng)的最小生成樹。

Kruskal算法恰恰相反,它的時間復(fù)雜度為O(eloge),因此相對于Prim算法而言,適合于求邊稀疏的連通網(wǎng)的最小生成樹。7.5有向無環(huán)圖

及其應(yīng)用設(shè)有向圖G=(V,{A})，G的拓撲序列是指V中所有頂點的線性序列，該序列滿足如下條件：若G中從頂點Vi到頂點Vj

有一條路徑，則序列中Vi必在Vj之前。構(gòu)造有向圖的拓撲序列的過程稱作拓撲排序。7.5.1拓撲排序例如：對于下列有向圖BDAC可求得拓撲序列：

ABCD

或

ACBD所謂拓撲排序，就是對有向圖進行下列操作:按照有向圖給出的次序關(guān)系，將圖中所有頂點排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點，則可以人為地加上任意的次序關(guān)系。對于任意的有向圖，拓撲排序不一定成功，如果有向圖含有環(huán)，則不能得到其拓撲序列。例如，對于下列有向圖不能求得它的拓撲序列。因為圖中存在回路

(B,C,D)BACD拓撲排序的應(yīng)用

若以有向圖表示一個工程的施工流程圖或程序的數(shù)據(jù)流圖，則圖中不允許出現(xiàn)回路。檢查有向圖中是否存在回路的方法之一，就是對有向圖進行拓撲排序。AOV-網(wǎng)(ActivityOnVertexnetwork)

頂點表示活動，弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)，簡稱AOV-網(wǎng)。例如：課程之間優(yōu)先關(guān)系圖拓撲排序的方法:從有向圖中選取一個沒有前驅(qū)的頂點，并輸出之;3.重復(fù)上述兩步，直至全部頂點均已輸出，或者圖中找不到無前驅(qū)的頂點為止。2.從有向圖中刪去此頂點以及所有以它為尾的弧;abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

沒有前驅(qū)的頂點

入度為零的頂點刪除頂點及以它為尾的弧

弧頭頂點的入度減17.5.2關(guān)鍵路徑AOE-網(wǎng)(ActivityOnEdgenetwork)

帶權(quán)的有向無環(huán)圖，其中頂點表示事件,弧表示活動，權(quán)表示活動的持續(xù)時間。8假設(shè)以AOE-網(wǎng)表示一個工程的施工流程圖，每條弧表示一項子工程，弧上的權(quán)值表示完成該項子工程所需要的時間。需要研究的問題是：完成整個工程至少需要多少時間？哪些子工程是“關(guān)鍵工程”？即哪些子工程將影響整個工程的完成期限？8從源點到匯點的最長路徑稱為關(guān)鍵路徑，關(guān)鍵路徑的長度是完成整個工程的最短時間。例:源點匯點關(guān)鍵路徑上的