第十二章圖

12.1圖的定義

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

V表示頂點集，E表示邊集。

(2)如果邊有方向，則稱有向圖，＜u,v＞表示從u出發到v的一條邊；與之對應的是無

向圖，(u,v)

(3)有時邊還有第三個屬性，稱為邊的代價或權值，用來表示經過這條邊所花費的代

價，這樣的圖稱為加權圖(有向加權圖、無向加權圖)加權圖中的每條邊由3個分量表

示：兩個頂點和權值

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

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

12.2圖的基本術語

⑴鄰接

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

(2)度

在無向圖中，結點的度是與該結點關聯的邊數；在有向圖中，度分為出度和入度。

(3)子圖

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

(4)路徑和路徑長度

路徑是指圖中由邊連接而成的結點序列。

非加權的路徑長度就是指組成路徑的邊數，為N-l(N為結點個數)

加權的路徑長度就是指路徑上所有邊的權值之和。

(5)連通圖和連通分量

如果一個無向圖G的任意兩個結點之間都是連通的（即有路徑），則稱G是連通圖；每

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

分量。

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

?----?

（6）強連通圖和強連通分量

如果有向圖G的任意兩個結點之間都是連通的，則稱G是強連通圖。

對于非強連通圖，會有強連通分量。

（7）完全圖

每兩個結點之間都有邊的無向圖稱為無向完全圖；每兩個結點之間都有兩條弧的有向圖

稱為有向完全圖。

（8）生成樹

生成樹是國同連通圖的極小連通子圖，n-l條邊使得n個結點互相連通，在生成樹中添

加一條邊，必定會形成回路或環。

12.3圖的基本運算

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

返回圖中的結點數或邊數；遍歷圖中所有結點。

12.4圖的存儲

12.4.1鄰接矩陣表示法

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

或者無窮大。

01010

11010

01010

11010

01010

11010

(2)對于無向圖，鄰接矩陣第i行或第i列的元素之和是第i個結點的度；

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

(3)圖的鄰接矩陣存儲需要兩個部分：一個是存儲結點值的數組；一個是存儲邊的鄰

接矩陣。

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

template<classTypeOfVer,classTypeOfEdge>

classadjMatrixGraph:publicgraph<TypeOfEdge>{〃7意味著“繼承自”，鄰接矩陣繼承自

圖的抽象類

public:〃公有成員函數

adjMatrixGraph(intvSize,constTypeOfVerd[],constTypeOfEdgenoEdgeFlag);

〃構造函數，三個參數，vSize頂點個數，頂點值數組，結點間不存在邊的標志

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

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

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

在邊

~adjMatrixGraph();〃析構函數

private:〃私有成員變址

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

TypeOfVer*ver;〃仃

TypeOfEdgenoedge;〃結點間不存在邊的標志

12-3adjMatrixGraph類的構造函數

template<classTypeOfVer,classTypeOfEdge>

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

constTypeOfEdgenoEdgeFlag)〃構造函數有3個參數：結點數、結點值和鄰接矩陣中表

示結點間無邊的標記，構造函數根據這3個參數構造?個只有結點沒有邊的圖

{inti,j;

Vers=vSize;//設置存儲結點數

Edges=0;〃邊數

noEdge=noEdgeFlag;〃無邊標記

ver=newTypeOfVer[vSize];〃申請一個存儲結點的一維數組ver,

for(i=0;i<vSize;++i)ver[i]=d[i];//for循環把參數中給出的結點值保存在數組ver中

edge=newTypeOfEdge*[vSize];

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

指針數組，所以此行為申請一個指向一維數組的指針數組edge

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

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

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

edge「Hi]=O；〃把自己到自己的邊的權值設為0

)

)

12-4adjMatrixGraph類的析構函數

template<classTypeOfVer,classTypeOfEdge>

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

(

delete[]ver;〃釋放了存放站點俏.的?維數組的空間

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

矩陣，for的每個循環周期釋放了鄰接矩陣的一行

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

)

12-5adjMatrixGraph類其它成員函數的實現

template<classTypeOfVer,classTypeOfEdge>

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

〃插入函數，參數是邊，起點為u,終點為v,權重為w

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

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

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

++Edge;〃邊數+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作為參數輸入的邊是否合法

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

false

edge[u][v]=noEdge;〃如果存在,則將對應的數組無戈noEdge

-Edge;〃邊數；

returntrue;//i￡PItrue表示刪除成功

)

template<classTypeOfVer,classTypeOfEdge>

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

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

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

elsereturntrue;〃存隹返回true

}

12.4.2鄰接表表示法

(1)基本定義

將每個結點的鄰接結點組成一個鏈表，鏈表的每個結點代表一條邊。

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

（2）保存方法

在鄰接表表示法中，保存一個圖同樣分為兩部分：保存頂點和保存邊。

頂點集|用一個數組表示,數組中每個元素由兩部分組成：頂點值和指向該頂點對應的鏈

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

睡由一組單鏈表表示。①非加權圖②加權圖

終止結點的編號后繼指針

datalink

權值終止結點的編號后繼指針

costdatalink

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

①有向圖

每條邊都作為一個單鏈表的結點出現，所以所有頂點對應的單鏈表的結點總數=圖的邊

數

②無向圖

每條邊在鄰接表中將出現兩次，例如（x,y）,在x的單鏈表中有一個以y為終點的結點，

在y的單鏈表中有一個以x為終點的結點，所以所有頂點對應的單鏈表的結點總數=圖

邊數的兩倍。

12-6鄰接表類的定義

template<classTypeOfVers,classTypeOfEdge>

classadjListGraph:publicgraph<TypeOfEdge>{

public:

adjListGraph(intvSize,constTypeOfVerd[]);〃構造函數

boolinsert(intujntvJypeOfEdgew);〃插入邊

boolremove(intujntv);〃刪除邊

boolexist(intujntv)const;〃是否存在

~adjListGraph。;〃析構函數

private:

structedgeNode{〃為了保存邊的信息，定義一個單.鏈表中的結點類型edgeNode

intend;〃終止結點的編號

TypeOfEdgeweight;〃權重

edgeNode*next;〃后繼指針

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

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

)；

structverNode{〃為了保存頂點的*定義了一個保存頂點的數組中的結點類型

verNode

TypeOfVerver;

edgeNode*head;〃頂點的首地址

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

{head=h;}

)；

verNode*verList;//保存頂點數組的首地址

）；

verListedaeNode

12-7adjListGraph類的構造函數和析構函數

template<classTypeOfVers,classTypeOfEdge>

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

{Vers=vSize;Edges=O;〃根據參數表中給出的頂點個數中請?個存儲頂點的數組，并設得

個頂點對應的單鏈表為空

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

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

}

template<classTypeOfVers,classTypeOfEdge>

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

{inti;

edgeNode*p;〃臨時指針

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

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

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

deletep;③〃三步刪除一條單.鏈表中的一個結點

}

delete[]verList;〃釋放存儲頂點的數組的空間

}

verListedaeNode

12-8insert函數的實現

template<classTypeOfVers,classTypeOfEdge>

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

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

結點，然后將新插入的邊對應的結點插入到單鏈表的表頭

++Edges;〃邊數+工

returntrue;

}

12-9remove函數的實現

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；第一個結,就是要刪除的結點

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

deletep;--Edges;

returntrue;

)

4

whil