數(shù)據(jù)結(jié)構(gòu)--圖-期末考試復(fù)習(xí)

第十二章圖

12.1圖的定義

(1)圖是由一個(gè)頂點(diǎn)集和連接各頂點(diǎn)的邊集組成。它可以用二元組G=(V,E)表示，其中

V表示頂點(diǎn)集，E表示邊集。

(2)如果邊有方向，則稱有向圖，＜u,v＞表示從u出發(fā)到v的一條邊；與之對(duì)應(yīng)的是無(wú)

向圖，(u,v)

(3)有時(shí)邊還有第三個(gè)屬性，稱為邊的代價(jià)或權(quán)值，用來(lái)表示經(jīng)過(guò)這條邊所花費(fèi)的代

價(jià)，這樣的圖稱為加權(quán)圖(有向加權(quán)圖、無(wú)向加權(quán)圖)加權(quán)圖中的每條邊由3個(gè)分量表

示：兩個(gè)頂點(diǎn)和權(quán)值

(4)稀疏圖：|E|遠(yuǎn)遠(yuǎn)小于|V?|

理想下的邊數(shù)|E|=|V2|-|V|,例如右圖:|E|=32=3=6

12.2圖的基本術(shù)語(yǔ)

⑴鄰接

如(Vi,Vj)是無(wú)向圖中的一條邊，則稱Vi和Vj鄰接

(2)度

在無(wú)向圖中，結(jié)點(diǎn)的度是與該結(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)；在有向圖中，度分為出度和入度。

(3)子圖

假設(shè)G=(V,E)和GJ(V',E如果V'包含于V,E'包含于E,,則稱G'是G的子圖。

(4)路徑和路徑長(zhǎng)度

路徑是指圖中由邊連接而成的結(jié)點(diǎn)序列。

非加權(quán)的路徑長(zhǎng)度就是指組成路徑的邊數(shù)，為N-l(N為結(jié)點(diǎn)個(gè)數(shù))

加權(quán)的路徑長(zhǎng)度就是指路徑上所有邊的權(quán)值之和。

(5)連通圖和連通分量

如果一個(gè)無(wú)向圖G的任意兩個(gè)結(jié)點(diǎn)之間都是連通的（即有路徑），則稱G是連通圖；每

一個(gè)非連通圖都可以分成幾個(gè)極大的連通的部分，每一個(gè)極大的連通子圖稱為一個(gè)連通

分量。

0------------------?

?----?

（6）強(qiáng)連通圖和強(qiáng)連通分量

如果有向圖G的任意兩個(gè)結(jié)點(diǎn)之間都是連通的，則稱G是強(qiáng)連通圖。

對(duì)于非強(qiáng)連通圖，會(huì)有強(qiáng)連通分量。

（7）完全圖

每?jī)蓚€(gè)結(jié)點(diǎn)之間都有邊的無(wú)向圖稱為無(wú)向完全圖；每?jī)蓚€(gè)結(jié)點(diǎn)之間都有兩條弧的有向圖

稱為有向完全圖。

（8）生成樹(shù)

生成樹(shù)是國(guó)同連通圖的極小連通子圖，n-l條邊使得n個(gè)結(jié)點(diǎn)互相連通，在生成樹(shù)中添

加一條邊，必定會(huì)形成回路或環(huán)。

12.3圖的基本運(yùn)算

構(gòu)成圖；判斷兩條邊之間是否有邊的存在exist；在圖中添加或刪除一條邊insert/remove；

返回圖中的結(jié)點(diǎn)數(shù)或邊數(shù)；遍歷圖中所有結(jié)點(diǎn)。

12.4圖的存儲(chǔ)

12.4.1鄰接矩陣表示法

（1）若頂點(diǎn)i、j之間存在一條自i到j(luò)的有向邊或無(wú)向邊，那么A[i]0]=l,否則A「Hj]=O

或者無(wú)窮大。

01010

11010

01010

11010

01010

11010

(2)對(duì)于無(wú)向圖，鄰接矩陣第i行或第i列的元素之和是第i個(gè)結(jié)點(diǎn)的度；

對(duì)于有向圖，鄰接矩陣的第i行元素之和是出度，第j列元素之和是入度。

(3)圖的鄰接矩陣存儲(chǔ)需要兩個(gè)部分：一個(gè)是存儲(chǔ)結(jié)點(diǎn)值的數(shù)組；一個(gè)是存儲(chǔ)邊的鄰

接矩陣。

12-2基于鄰接矩陣的圖類定義

template<classTypeOfVer,classTypeOfEdge>

classadjMatrixGraph:publicgraph<TypeOfEdge>{〃7意味著“繼承自”，鄰接矩陣?yán)^承自

圖的抽象類

public:〃公有成員函數(shù)

adjMatrixGraph(intvSize,constTypeOfVerd[],constTypeOfEdgenoEdgeFlag);

〃構(gòu)造函數(shù)，三個(gè)參數(shù)，vSize頂點(diǎn)個(gè)數(shù)，頂點(diǎn)值數(shù)組，結(jié)點(diǎn)間不存在邊的標(biāo)志

boolinsert(intujntv,TypeOfEdgew);〃插入一條邊

boolremove(intu,intv);〃刪除條邊

boolexist(intu,intv)const;〃彳j爾類型，fepoL非真即假，返回常數(shù)，是否存

在邊

~adjMatrixGraph();〃析構(gòu)函數(shù)

private:〃私有成員變址

TypeOfEdge**edge;〃存放鄰接處:陣,二維數(shù)組

TypeOfVer*ver;〃仃

TypeOfEdgenoedge;〃結(jié)點(diǎn)間不存在邊的標(biāo)志

12-3adjMatrixGraph類的構(gòu)造函數(shù)

template<classTypeOfVer,classTypeOfEdge>

adjMatrixGraph<TypeOfVer,TypeOfEdge>：：adjMatrixGraph(intvSize,constTypeOfVerd[],

constTypeOfEdgenoEdgeFlag)〃構(gòu)造函數(shù)有3個(gè)參數(shù)：結(jié)點(diǎn)數(shù)、結(jié)點(diǎn)值和鄰接矩陣中表

示結(jié)點(diǎn)間無(wú)邊的標(biāo)記，構(gòu)造函數(shù)根據(jù)這3個(gè)參數(shù)構(gòu)造?個(gè)只有結(jié)點(diǎn)沒(méi)有邊的圖

{inti,j;

Vers=vSize;//設(shè)置存儲(chǔ)結(jié)點(diǎn)數(shù)

Edges=0;〃邊數(shù)

noEdge=noEdgeFlag;〃無(wú)邊標(biāo)記

ver=newTypeOfVer[vSize];〃申請(qǐng)一個(gè)存儲(chǔ)結(jié)點(diǎn)的一維數(shù)組ver,

for(i=0;i<vSize;++i)ver[i]=d[i];//for循環(huán)把參數(shù)中給出的結(jié)點(diǎn)值保存在數(shù)組ver中

edge=newTypeOfEdge*[vSize];

〃鄰接矩陣egde是一個(gè)vSize*vSize的矩陣，而二維數(shù)組可以看成一個(gè)指向一維數(shù)組的

指針數(shù)組，所以此行為申請(qǐng)一個(gè)指向一維數(shù)組的指針數(shù)組edge

for(i=0;i<vSize;++i){〃對(duì)鄰接矩陣111的每一行進(jìn)行初始化

edge[i]=newTypeOfEdge[vSize];〃為鄰接矩陣的這?行申請(qǐng)空間

for(j=0;j<vSize;++j)edge[i][j]=noEdge;〃將每個(gè)元素都設(shè)成“沒(méi)有邊”

edge「Hi]=O；〃把自己到自己的邊的權(quán)值設(shè)為0

)

)

12-4adjMatrixGraph類的析構(gòu)函數(shù)

template<classTypeOfVer,classTypeOfEdge>

adjMatrixGraph<TypeOfVer,TypeOfEdge>::~adjMatrixGraph()

(

delete[]ver;〃釋放了存放站點(diǎn)俏.的?維數(shù)組的空間

for(inti=O;i<Vers;++i)delete[]edge。];〃循環(huán)釋放保存鄰接矩陣的空間,edge是鄰接

矩陣，for的每個(gè)循環(huán)周期釋放了鄰接矩陣的一行

delete1]edge;//#^了指向鄰接矩陣每一行首地址的指針―

)

12-5adjMatrixGraph類其它成員函數(shù)的實(shí)現(xiàn)

template<classTypeOfVer,classTypeOfEdge>

booladjMatrixGraph<TypeOfVer,TypeOfEdge>::|insert|(intu,intv,TypeOfEdgew)

〃插入函數(shù)，參數(shù)是邊，起點(diǎn)為u,終點(diǎn)為v,權(quán)重為w

{if(u<O||u>Vers-l||v<O||v>Vers-l)returnflase;〃檢查作為參數(shù)輸入的邊是否合法

if(edge[u][v]!=noEdge)returnfalse;〃檢查被捅入的邊是否存隹，如果存在,返回false

edge[u][v]=w;〃若不存在，則在鄰接矩陣中添加相應(yīng)的邊

++Edge;〃邊數(shù)+1

returntrue;〃返叵Itrue我示插入成功

)

template<classTypeOfVer,classTypeOfEdge>

booladjMatrixGraph<TypeOfVer,TypeOfEdge>::|remove|(intu,intv)

{if(u<0||u>Vers?l||v<0]|v>Vers-1)returnflase;〃檢彳f作為參數(shù)輸入的邊是否合法

if(edge[u][v]==noEdge)returnfalse;〃檢查所刪除的邊是否存在,如果不存在,返回

false

edge[u][v]=noEdge;〃如果存在,則將對(duì)應(yīng)的數(shù)組無(wú)戈noEdge

-Edge;〃邊數(shù)；

returntrue;//i￡P(guān)Itrue表示刪除成功

)

template<classTypeOfVer,classTypeOfEdge>

booladjMatrixGraph<TypeOfVer,TypeOfEdge>::|exist|(intujntv)const

{if(u<0||u>Vers-l||v<0||v>Vers-l)returnflase;〃檢查作為參數(shù)輸入的邊是否合法

if(edge[u][v]==noEdge)returnfalse;〃判斷邊是否存在，不存在返1nlfalse

elsereturntrue;〃存隹返回true

}

12.4.2鄰接表表示法

(1)基本定義

將每個(gè)結(jié)點(diǎn)的鄰接結(jié)點(diǎn)組成一個(gè)鏈表，鏈表的每個(gè)結(jié)點(diǎn)代表一條邊。

左邊圖只是右邊的部分表示

（2）保存方法

在鄰接表表示法中，保存一個(gè)圖同樣分為兩部分：保存頂點(diǎn)和保存邊。

頂點(diǎn)集|用一個(gè)數(shù)組表示,數(shù)組中每個(gè)元素由兩部分組成：頂點(diǎn)值和指向該頂點(diǎn)對(duì)應(yīng)的鏈

表的首地址,即:data和link兩部分。

睡由一組單鏈表表示。①非加權(quán)圖②加權(quán)圖

終止結(jié)點(diǎn)的編號(hào)后繼指針

datalink

權(quán)值終止結(jié)點(diǎn)的編號(hào)后繼指針

costdatalink

（3）有向圖和無(wú)向圖保存方法比較之處

①有向圖

每條邊都作為一個(gè)單鏈表的結(jié)點(diǎn)出現(xiàn)，所以所有頂點(diǎn)對(duì)應(yīng)的單鏈表的結(jié)點(diǎn)總數(shù)=圖的邊

數(shù)

②無(wú)向圖

每條邊在鄰接表中將出現(xiàn)兩次，例如（x,y）,在x的單鏈表中有一個(gè)以y為終點(diǎn)的結(jié)點(diǎn)，

在y的單鏈表中有一個(gè)以x為終點(diǎn)的結(jié)點(diǎn)，所以所有頂點(diǎn)對(duì)應(yīng)的單鏈表的結(jié)點(diǎn)總數(shù)=圖

邊數(shù)的兩倍。

12-6鄰接表類的定義

template<classTypeOfVers,classTypeOfEdge>

classadjListGraph:publicgraph<TypeOfEdge>{

public:

adjListGraph(intvSize,constTypeOfVerd[]);〃構(gòu)造函數(shù)

boolinsert(intujntvJypeOfEdgew);〃插入邊

boolremove(intujntv);〃刪除邊

boolexist(intujntv)const;〃是否存在

~adjListGraph。;〃析構(gòu)函數(shù)

private:

structedgeNode{〃為了保存邊的信息，定義一個(gè)單.鏈表中的結(jié)點(diǎn)類型edgeNode

intend;〃終止結(jié)點(diǎn)的編號(hào)

TypeOfEdgeweight;〃權(quán)重

edgeNode*next;〃后繼指針

edgeNode(inte,TypeOfEdgew,edgeNode*n=NULL)

{end=e;weight=w;next=n;}

)；

structverNode{〃為了保存頂點(diǎn)的*定義了一個(gè)保存頂點(diǎn)的數(shù)組中的結(jié)點(diǎn)類型

verNode

TypeOfVerver;

edgeNode*head;〃頂點(diǎn)的首地址

verNode(edgeNode*n=NULL)〃后繼指針

{head=h;}

)；

verNode*verList;//保存頂點(diǎn)數(shù)組的首地址

）；

verListedaeNode

12-7adjListGraph類的構(gòu)造函數(shù)和析構(gòu)函數(shù)

template<classTypeOfVers,classTypeOfEdge>

adjListGraph<TypeOfVers,TypeOfEdge>::adjListGraphfintvSize,constTypeOfVerd[])

{Vers=vSize;Edges=O;〃根據(jù)參數(shù)表中給出的頂點(diǎn)個(gè)數(shù)中請(qǐng)?個(gè)存儲(chǔ)頂點(diǎn)的數(shù)組，并設(shè)得

個(gè)頂點(diǎn)對(duì)應(yīng)的單鏈表為空

verList=newverNode[vSize];〃把數(shù)組首地址賦給verList

for(inti=O;i<Vers;++i)verList[i].ver=d「];〃將參數(shù)表中給出的頂點(diǎn)值存入該數(shù)組

}

template<classTypeOfVers,classTypeOfEdge>

adjListGraph<TypeOfVers,TypeOfEdge>::~adjListGraph|()

{inti;

edgeNode*p;〃臨時(shí)指針

for(i=0;i<Vers;++i)//?次循環(huán)刪除?條單鏈表，即?個(gè)頂點(diǎn)的所有邊

while((p=verList[i].head)!=NULL){(l)

verList[i].head=p->next;(2)

deletep;③〃三步刪除一條單.鏈表中的一個(gè)結(jié)點(diǎn)

}

delete[]verList;〃釋放存儲(chǔ)頂點(diǎn)的數(shù)組的空間

}

verListedaeNode

12-8insert函數(shù)的實(shí)現(xiàn)

template<classTypeOfVers,classTypeOfEdge>

adjListGraph<TypeOfVers,TypeOfEdge>::insert(intu,intv,TypeOfEdgew)

{verList[u].head=newedgeNode(v,w,verList[u].head);〃為新插入的邊申請(qǐng)-~個(gè)單鏈表'I1的

結(jié)點(diǎn)，然后將新插入的邊對(duì)應(yīng)的結(jié)點(diǎn)插入到單鏈表的表頭

++Edges;〃邊數(shù)+工

returntrue;

}

12-9remove函數(shù)的實(shí)現(xiàn)

template<classTypeOfVers,classTypeOfEdge>

adjListGraph<TypeOfVers,TypeOfEdge>::|remove|(intu,intv)

{edgeNode*p=verList[u].head,*q;

verListedaeNode

if(p==NULL)returnfalse;

if(p->end==v)〃7；第一個(gè)結(jié),就是要?jiǎng)h除的結(jié)點(diǎn)

{verList[u].head=p->next;

deletep;--Edges;

returntrue;

)

4

whil