數(shù)據(jù)結(jié)構(gòu)第七章圖計(jì)算機(jī)科學(xué)系施化吉E-mail:

圖(Graph)是一種比樹更為復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。

在樹形結(jié)構(gòu)中,數(shù)據(jù)元素之間的關(guān)系是一對多的關(guān)系。

而在圖形結(jié)構(gòu)中,數(shù)據(jù)元素之間的關(guān)系是任意的,圖中每一個數(shù)據(jù)元素可以和任何其它數(shù)據(jù)元素相關(guān)聯(lián),是多對多的關(guān)系。

7.1圖的基本概念

7.1圖的基本概念

圖是由數(shù)據(jù)元素的集合及數(shù)據(jù)元素間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu):Graph＝(V,E),其中:V={x|x某個數(shù)據(jù)對象}是數(shù)據(jù)元素的集合,在圖中,數(shù)據(jù)元素一般被稱為頂點(diǎn)(vertex);

E={(v,w)|v,wV}或E={<v,w>|v,wV&&Path(v,w)}是數(shù)據(jù)元素之間關(guān)系的集合,也叫做邊(edge)集合;Path(v,w)表示從頂點(diǎn)v到頂點(diǎn)w的一條單向通路,它是有方向的.7.1.1圖的定義

在圖中如果頂點(diǎn)對(v,w)是無序的,則稱此圖為無向圖(undirectedgraph).

頂點(diǎn)對(v,w)稱為與頂點(diǎn)v和頂點(diǎn)w相關(guān)聯(lián)的一條邊.由于這條邊沒有方向,所以(v,w)與(w,v)是同一條邊;在圖中如果頂點(diǎn)對＜v,w＞是有序的,則稱此圖為有向圖(directedgraph).

頂點(diǎn)對＜v,w＞稱為從頂點(diǎn)v到頂點(diǎn)w的一條有向邊(又稱為弧),

其中v稱為有向邊＜v,w＞的始點(diǎn)(弧尾);w稱為有向邊＜v,w＞的終點(diǎn)(弧頭).

顯然＜v,w＞與＜w,v＞是兩條不同的弧.

一般表示無向圖中邊的頂點(diǎn)對用一對圓括號括()起來;

表示有向圖中弧的頂點(diǎn)對用一對尖括號<>括起來.

右圖所示的4個圖,其中G1和G2是無向圖,G3和G4是有向圖.

在圖G3和G4中,為了表示有向邊,邊的方向用箭頭畫出,箭頭從有向邊的始點(diǎn)指向有向邊的終點(diǎn);在無向圖中用線段表示邊.在下面對圖的討論中,對圖作一些限制:第一、圖中不能有從頂點(diǎn)自身到自身的邊(即自身環(huán)),就是說不應(yīng)有形如(x,x)或＜x,x＞的邊.如圖(a)所示的帶自身環(huán)的圖不討論.第二、兩個頂點(diǎn)v和w之間相關(guān)聯(lián)的邊不能多于一條.如圖(b)所示的多重圖也不討論.7.1.2圖的術(shù)語

1．完全圖(completegraph):若一個無向圖有n個頂點(diǎn),請問該無向圖最多有多少條邊？又,若一個有向圖有n個頂點(diǎn),請問該有向圖最多有多少條弧？7.1.2圖的術(shù)語

1．完全圖(completegraph):

在有n個頂點(diǎn)的無向圖中,若有n(n-1)／2條邊,則稱此無向圖為完全無向圖.

在有n個頂點(diǎn)的有向圖中,若有n(n-1)條邊,則稱此圖為完全有向圖.

顯然,在完全圖中邊(弧)數(shù)目達(dá)到最大.213完全有向圖213完全無向圖7.1.2圖的術(shù)語

2．權(quán)(weight):

在某些圖的應(yīng)用中,邊(弧)上具有與它相關(guān)的系數(shù),稱之為權(quán).

這些權(quán)可以表示從一個頂點(diǎn)到另一個頂點(diǎn)的距離、所花費(fèi)的代價、所需的時間、次數(shù)等等.

這種帶權(quán)圖也被稱為網(wǎng)絡(luò)(network).分別有:無向網(wǎng)和有向網(wǎng).ABECF1597211132ABECF1597211132無向網(wǎng)有向網(wǎng)7.1.2圖的術(shù)語

3．鄰接點(diǎn)(adjacentvertex):

如果(v,w)是無向圖G中的一條邊,則稱v與w互為鄰接頂點(diǎn),而且邊(v,w)被稱為依附于頂點(diǎn)v和w.

如果＜v,w＞是有向圖G中的一條弧,則稱頂點(diǎn)v鄰接到頂點(diǎn)w(也稱v是w的前驅(qū)),頂點(diǎn)w鄰接自頂點(diǎn)v(也稱w是v的后繼),?。紇,w＞與頂點(diǎn)v與w相關(guān)聯(lián).ABECF1597211132ABECF1597211132無向網(wǎng)有向網(wǎng)4．子圖(subgraph):

設(shè)有兩個圖G＝(V,E)和G’＝(V’,E’).若V’V且E’E,則稱圖G’是圖G的子圖.

下圖右圖中(a)和(b)是無向圖G1的兩個子圖,圖(c)和(d)是有向圖G3的兩個子圖.7.1.2圖的術(shù)語

5．頂點(diǎn)的度(degree):無向圖中,頂點(diǎn)的度是指與每個頂點(diǎn)相連的邊數(shù)有向圖中,頂點(diǎn)的度分成入度與出度入度ID(Vi):是指以該頂點(diǎn)為頭的弧的數(shù)目出度OD(Vi):是指以該頂點(diǎn)為尾的弧的數(shù)目頂點(diǎn)的度TD(Vi)＝出度OD(Vi)＋入度ID(Vi)G2中頂點(diǎn)1的度為2G4中頂點(diǎn)1的入度為2

出度為1

頂點(diǎn)1的度為37.1.2圖的術(shù)語

6．路徑(path):

在圖G＝(V,E)中,若從頂點(diǎn)vi出發(fā),沿一些邊(或弧)經(jīng)過一些頂點(diǎn)vp1,vp2,…,vpk,到達(dá)頂點(diǎn)vj,

則頂點(diǎn)序列(vi,vp1,vp2,…,vpk,vj)被稱為:從頂點(diǎn)vi到頂點(diǎn)vj的路徑.例245136G1路徑:1,2,3,5,6,3路徑長度:5簡單路徑:1,2,3,5回路:1,2,3,5,6,3,1簡單回路:3,5,6,3例157324G26路徑:1,2,5,7,6,5,2,3路徑長度:7簡單路徑:1,2,5,7,6回路:1,2,5,7,6,5,2,1簡單回路:1,2,3,17.1.2圖的術(shù)語

7．路徑長度(pathlength):

對于不帶權(quán)的圖,路徑長度是指這條路徑上邊(弧)的數(shù)目.例245136G1例157324G267.1.2圖的術(shù)語

路徑:1,2,3,5,6,3路徑長度:5簡單路徑:1,2,3,5回路:1,2,3,5,6,3,1簡單回路:3,5,6,3路徑:1,2,5,7,6,5,2,3路徑長度:7簡單路徑:1,2,5,7,6回路:1,2,5,7,6,5,2,1簡單回路:1,2,3,1路徑:A,B,C,F路徑長度:15+3+2路徑:A,E,C,F,B路徑長度:9+21+2+7ABECF1597211132ABEC1.2圖的術(shù)語

7．路徑長度(pathlength):

對于帶權(quán)圖,路徑長度是指路徑上各邊(弧)的權(quán)之和.8．簡單路徑、回路和簡單回路:

對于一路徑(v1,v2,…,vm),若路徑上各頂點(diǎn)均不相同,則稱這路徑為簡單路徑.例245136G1路徑:1,2,3,5,6,3路徑長度:5簡單路徑:1,2,3,5回路:1,2,3,5,6,3,1簡單回路:3,5,6,3例157324G26路徑:1,2,5,7,6,5,2,3路徑長度:7簡單路徑:1,2,5,7,6回路:1,2,5,7,6,5,2,1簡單回路:1,2,3,17.1.2圖的術(shù)語

8．簡單路徑、回路和簡單回路:

若路徑上第一個頂點(diǎn)v1和最后一個頂點(diǎn)vm相同,則稱這樣的路徑為回路或環(huán).例245136G1例157324G267.1.2圖的術(shù)語

路徑:1,2,3,5,6,3路徑長度:5簡單路徑:1,2,3,5回路:1,2,3,5,6,3,1簡單回路:3,5,6,3路徑:1,2,5,7,6,5,2,3路徑長度:7簡單路徑:1,2,5,7,6回路:1,2,5,7,6,5,2,1簡單回路:1,2,3,18．簡單路徑、回路和簡單回路:

若回路中除起點(diǎn)和終點(diǎn)相同外,其余頂點(diǎn)各不相同,則稱為簡單回路.例245136G1例157324G267.1.2圖的術(shù)語

路徑:1,2,3,5,6,3路徑長度:5簡單路徑:1,2,3,5回路:1,2,3,5,6,3,1簡單回路:3,5,6,3路徑:1,2,5,7,6,5,2,3路徑長度:7簡單路徑:1,2,5,7,6回路:1,2,5,7,6,5,2,1簡單回路:1,2,3,19．連通圖與連通分量:

在無向圖中,若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱頂點(diǎn)vi與vj是連通的.

如果無向圖中任意兩個頂點(diǎn)都是連通的,則稱此無向圖是連通圖.

非連通圖的極大連通子圖(包括所有連通的頂點(diǎn)和這些頂點(diǎn)依附的所有的邊)叫做連通分量.如右圖(a)所示是一個非連通圖,圖(b)所示是相應(yīng)的三個連通分量.7.1.2圖的術(shù)語

G是一個共有28條邊的非連通無向圖,則該圖至少有

個頂點(diǎn).910．強(qiáng)連通圖與強(qiáng)連通分量(stronglyconnecteddigraph):

在有向圖中,若對于頂點(diǎn)vi和vj,同時存在一條從vi到vj和從vj到vi的路徑,則稱頂點(diǎn)vi和頂點(diǎn)vj是強(qiáng)連通的.

如果有向圖中任意兩個頂點(diǎn)都是強(qiáng)連通的,則稱此有向圖為強(qiáng)連通圖.

非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量.G3是強(qiáng)連通圖,G4是非強(qiáng)連通圖,G4有兩個強(qiáng)連通分量7.1.2圖的術(shù)語

11．生成樹和生成森林:BACDFE

假設(shè)一個連通圖有n個頂點(diǎn)和e條邊,其中n-1條邊和n個頂點(diǎn)構(gòu)成一個極小連通子圖,稱該極小連通子圖為該連通圖的生成樹.7.1.2圖的術(shù)語

“極小”：邊不能再少了，否則不連通點(diǎn)不能再少了，因?yàn)檫@個概念要求必須達(dá)到n個頂點(diǎn)11．生成樹和生成森林:對非連通圖,則稱由各個連通分量的生成樹的集合為該非連通圖的生成森林.BACDFE

假設(shè)一個連通圖有n個頂點(diǎn)和e條邊,其中n-1條邊和n個頂點(diǎn)構(gòu)成一個極小連通子圖,稱該極小連通子圖為該連通圖的生成樹.7.1.2圖的術(shù)語

11．生成樹和生成森林:

如果一個有向圖只有一個入度為零的頂點(diǎn),且其它頂點(diǎn)的入度均為1,則稱這個有向圖為有向樹.ABECF一個有向圖的生成森林——是由若干棵互不相交的有向樹組成,含有圖中全部頂點(diǎn)和圖中的部分弧.ABCDEFABFECD7.1.2圖的術(shù)語

7.1.3圖的基本操作圖的基本操作一般有:(1)InsertVertex(vertex):在圖中插入一個頂點(diǎn)vertex。(2)InsertEdge(v1,v2):在圖中插入一條邊(v1,v2)。(3)DeleteVertex(v):在圖中刪除一個頂點(diǎn)v及依附于v的邊。(4)DeleteEdge(v1,v2):在圖中刪除一條邊(或弧)。詳情見教材解釋(5)GetWeight(v1,v2):在圖中取邊(v1,v2)上的權(quán)。(6)GetFirstNeighbor(intv):在圖中取頂點(diǎn)v的第一個鄰接點(diǎn)。(7)GetNextNeighbor(intv1,intv2):在圖中取頂點(diǎn)v1的鄰接點(diǎn)v2的下一個鄰接點(diǎn)(v2也是v1的一個鄰接點(diǎn))。(8)Travers():遍歷圖,按某種次序依次訪問圖中的每一個頂點(diǎn),并使每一個頂點(diǎn)只被訪問一次。(9)IsEmpty():判斷圖是否為空。7.1.3圖的基本操作

常用的圖的存儲結(jié)構(gòu)有：

鄰接矩陣

鄰接表鄰接多重表十字鏈表

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

鄰接矩陣

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

鄰接表

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

鄰接多重表

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

十字鏈表

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

7.2.1鄰接矩陣7.2.1鄰接矩陣在圖的鄰接矩陣表示中,除了記錄每一個頂點(diǎn)信息的頂點(diǎn)表外,還有一個表示各個頂點(diǎn)之間關(guān)系的矩陣,稱之為鄰接矩陣。若設(shè)圖G＝(V,E)是一個有n個頂點(diǎn)的圖,則圖的鄰接矩陣是一個二維數(shù)組arcs[n][n],它的定義為:對于網(wǎng)絡(luò)(或帶權(quán)圖),鄰接矩陣定義如下:

1,如果<i,j>∈E或者(i,j)∈Earcs[i][j]=0,否則

W(i,j):i≠j,且(i,j)∈Earcs[i][j]=∞:i≠j,且(i,j)∈E0:i=j

下圖給出了無向圖、有向圖和有向網(wǎng)的鄰接矩陣.其中:

一維數(shù)組vertexes[]用于存儲頂點(diǎn)的信息,

二維數(shù)組arcs[][]用于存儲邊(或弧)的信息.

7.2.1鄰接矩陣從圖中可知,無向圖的鄰接矩陣是對稱的,將第i行的元素值或第i列的元素值累加起來就得到頂點(diǎn)i的度。即：

7.2.1鄰接矩陣有向圖的鄰接矩陣可能不對稱.如果第i行第j列為1,則表示有一條從頂點(diǎn)Vi到頂點(diǎn)Vj的有向邊,將第i行的所有元素值累加起來就得到頂點(diǎn)Vi的出度OD(Vi).如果第j行第i列為1,則表示有一條從頂點(diǎn)Vj到頂點(diǎn)Vi的有向邊,將第i列的所有元素值累加起來就得到頂點(diǎn)Vi的入度ID(Vi).7.2.1鄰接矩陣有向圖的鄰接矩陣可能不對稱.如果第i行第j列為1,則表示有一條從頂點(diǎn)Vi到頂點(diǎn)Vj的有向邊,將第i行的所有元素值累加起來就得到頂點(diǎn)Vi的出度OD(Vi).如果第j行第i列為1,則表示有一條從頂點(diǎn)Vj到頂點(diǎn)Vi的有向邊,將第i列的所有元素值累加起來就得到頂點(diǎn)Vi的入度ID(Vi).7.2.1鄰接矩陣頂點(diǎn)的度TD(Vi)＝出度OD(Vi)＋入度ID(Vi)鄰接矩陣作為存儲表示的圖的類聲明

:const

intMaxVertexes=20;//最大的頂點(diǎn)數(shù)template<class

vertexType,class

arcType>classGraph{//vertexType是頂點(diǎn)類型,arcType是邊(弧)的類型private:

SeqList<vertexType>Vertexes(MaxVertexes);

//存儲頂點(diǎn)信息的順序表

arcTypeArcs[MaxVertexes][MaxVertexes];//存儲邊(或弧)信息的矩陣

intCurrentNumArcs;//當(dāng)前的邊(或弧)數(shù)

intFindVertex(SeqList<vertexType>&L,constvertexType&v)//查找頂點(diǎn)v是否存在

{returnL.Locate(v);}

intGetVertexPos(constvertexType&v)//取頂點(diǎn)v在數(shù)組中的位置

{returnFindVertex(Vertexes,v);}順序表類要改寫為模版形式7.2.1鄰接矩陣詳情見教材解釋public:Graph(intnum=MaxVertexes);//構(gòu)造函數(shù)

intIsEmpty()const{returnVertexes.empty();}//判斷圖是否為空

intNumberOfVertexes(){returnVertexes.len;}//取圖的頂點(diǎn)數(shù)

intNumberOfArcs(){returnCurrentNumArcs;}//取圖的邊(或弧)數(shù)

vertexTypeGetValue(intv)//取圖中頂點(diǎn)v的值,如果不存在頂點(diǎn)v,則返回空

arcTypeGetWeight(intv1,intv2);//取邊(v1,v2)(或弧<v1,v2>)上的權(quán)7.2.1鄰接矩陣詳情見教材解釋intInsertVertex(vertexType&v);//在圖中插入頂點(diǎn)v

intInsertArc(intv1,intv2,arcTypeweight);//在圖中插入依附于頂點(diǎn)v1和v2的邊(或弧),weight是相應(yīng)邊(或弧)的信息

voidDeleteVertex(intv);//刪除頂點(diǎn)v,及依附于v的邊(或弧)

voidDeleteArc(intv1,intv2);//在圖中刪除依附于頂點(diǎn)v1和v2的邊(或弧)

intGetFirstNeighbor(intv);//取圖中頂點(diǎn)v的第一個鄰接點(diǎn)的序號。如果不存在,則返回-1

intGetNextNeighbor(intv1,intv2);//取圖中頂點(diǎn)v1的在v2之后的下一個鄰接點(diǎn)的序號。如果不存在,則返回-1}7.2.1鄰接矩陣詳情見教材解釋算法見下頁在鄰接矩陣上查找鄰接點(diǎn)算法:template<classvertexType,classarcType>intGraph<vertexType,arcType>::GetFirstNeighbor(constintv){//取出頂點(diǎn)位置為v的第一個鄰接頂點(diǎn)的位置

在鄰接矩陣上查找鄰接點(diǎn)算法:3．鄰接點(diǎn)(adjacentvertex):

如果(v,w)是無向圖G中的一條邊,則稱v與w互為鄰接頂點(diǎn),而且邊(v,w)被稱為依附于頂點(diǎn)v和w.

如果＜v,w＞是有向圖G中的一條弧,則稱頂點(diǎn)v鄰接到頂點(diǎn)w(也稱v是w的前驅(qū)),頂點(diǎn)w鄰接自頂點(diǎn)v(也稱w是v的后繼),?。紇,w＞與頂點(diǎn)v與w相關(guān)聯(lián).template<classvertexType,classarcType>intGraph<vertexType,arcType>::GetFirstNeighbor(constintv){//取出頂點(diǎn)位置為v的第一個鄰接頂點(diǎn)的位置

if(v>=0&&v<Vertexes.len){//若給定頂點(diǎn)號合理，則查找for(intj=0;j<Vertexes.len;j++)if(Arcs[v][j]==1)returnj;}return-1;//若給定頂點(diǎn)號不合理//或沒有找到，則都是失敗}在鄰接矩陣上查找鄰接點(diǎn)算法:template<classvertexType,classarcType>intGraph<vertexType,arcType>::GetNextNeighbor(intv1,intv2){//取圖中頂點(diǎn)v1的在v2之后的下一個鄰接點(diǎn)的序號。如果不存在返回-1if(v1>=0&&v1<Vertexes.len&&v2>=0&&v2<Vertexes.len-1){//若給定頂點(diǎn)號合理，則查找for(intj=v2+1;j<Vertexes.len;j++)if(Arcs[v1][j]==1)returnj;}return-1;}在鄰接矩陣上查找鄰接點(diǎn)算法:7.2.2鄰接表7.2.2鄰接表

實(shí)現(xiàn):為圖中每個頂點(diǎn)建立一個單鏈表,第i個單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊(有向圖中指以Vi為尾的弧).頂點(diǎn)結(jié)點(diǎn):data域:存放頂點(diǎn)信息firstarc域:指示第一個鄰接點(diǎn)弧(邊)結(jié)點(diǎn):adjvex域:鄰接點(diǎn)域,存放與Vi鄰接的點(diǎn)在頂點(diǎn)數(shù)組中的位置nextarc域:指示下一條邊或弧(下一個鄰接點(diǎn))下圖(b)所示的是有向圖的鄰接表表示。7.2.2鄰接表

特點(diǎn)無向圖中頂點(diǎn)Vi的度為第i個單鏈表中的邊結(jié)點(diǎn)數(shù)7.2.2鄰接表

有向圖中頂點(diǎn)Vi的出度為第i個單鏈表中的弧結(jié)點(diǎn)個數(shù)頂點(diǎn)Vi的入度為所有單鏈表中鄰接點(diǎn)域值是i的弧結(jié)點(diǎn)個數(shù)計(jì)算頂點(diǎn)的入度比較麻煩?。?7.2.2鄰接表

為此,對有向圖可以建立逆鄰接表,如圖(c)所示。在有向圖的逆鄰接表中,頂點(diǎn)vi的弧鏈表中鏈接的是所有以vi為弧頭的弧尾頂點(diǎn)。7.2.2鄰接表

對于帶權(quán)圖(網(wǎng)絡(luò)),必須在鄰接表的邊(或弧)結(jié)點(diǎn)中增加一個存放邊(或弧)上的權(quán)值的域weight。如下圖所示的是一個帶權(quán)圖的鄰接表表示。7.2.2鄰接表

在鄰接表的邊(或弧)鏈表中,各個邊(或弧)結(jié)點(diǎn)的鏈入順序任意,視邊(或弧)結(jié)點(diǎn)輸入次序而定。7.2.2鄰接表

設(shè)圖中有n個頂點(diǎn),e條邊,則用鄰接表表示無向圖時,需要n個頂點(diǎn)結(jié)點(diǎn),2e個邊結(jié)點(diǎn);用鄰接表表示有向圖時,若不考慮逆鄰接表,只需n個頂點(diǎn)結(jié)點(diǎn),e個弧結(jié)點(diǎn)。7.2.2鄰接表

圖的鄰接表表示的類定義:圖的鄰接表表示的類定義

:constintMaxVertexes=20;//最大的頂點(diǎn)數(shù)template<classvertexType,classarcType>classGraph;

template<classarcType>structArcNode{//定義邊(弧)結(jié)點(diǎn)friendclassGraph<classvertexType,classarcType>;intadjvex;//和邊(或弧)相關(guān)聯(lián)的另一個頂點(diǎn)序號

arcTypeweight;//邊(或弧)上的信息(權(quán))ArcNode<arcType>*nextarc;//指向下一條邊(弧)結(jié)點(diǎn)的指針

ArcNode(){}//構(gòu)造函數(shù)

ArcNode(intv,arcTypew):adjvex(v),weight(w),next(NULL){}//構(gòu)造函數(shù)}7.2.2鄰接表

template<classarcType,classvertexType>structVertexNode{//定義頂點(diǎn)結(jié)點(diǎn)friendclassGraph<classvertexType,classarcType>;vertexTypedata;//頂點(diǎn)的信息

ArcNode<arcType>*firstarc;//指向依附該頂點(diǎn)的邊(弧)鏈表}7.2.2鄰接表

template<classarcType,classvertexType>structVertexNode{//定義頂點(diǎn)結(jié)點(diǎn)friendclassGraph<classvertexType,classarcType>;vertexTypedata;//頂點(diǎn)的信息

ArcNode<arcType>*firstarc;//指向依附該頂點(diǎn)的邊(弧)鏈表}template<classvertexType,classarcType>Graph{//定義圖private:VertexNode<arcType,vertexType>*VertexesTable;//頂點(diǎn)表

intCurrentNumVertexes;當(dāng)前的頂點(diǎn)數(shù)

intCurrentNumArcs;//當(dāng)前的邊(或弧)數(shù)

intGetVertexPos(constvertexType&v);//取頂點(diǎn)v在數(shù)組中的位置7.2.2鄰接表

public:Graph:CurrentNumVertexes(0),CurrentNumArcs(0){};//構(gòu)造函數(shù)

Graph(vertexTypev[],intnum=MaxVertexes);//構(gòu)造函數(shù)

~Graph();//析構(gòu)函數(shù)

intIsEmpty()const{returnCurrentNumVertexes==0;}//判斷圖是否為空

intNumberOfVertexes(){returnCurrentNumVertexes;}//取圖的頂點(diǎn)數(shù)

intNumberOfArcs(){returnCurrentNumArcs;}//取圖的邊(或弧)數(shù)

vertexTypeGetValue(intv);//取圖中頂點(diǎn)v的數(shù)據(jù)值,如果不存在頂點(diǎn)v則返回空7.2.2鄰接表

詳情見教材解釋

arcTypeGetWeight(intv1,intv2);//取邊（或弧）上權(quán)值

int

GetFirstNeighbor(intv);//取v的第一個鄰接點(diǎn)

int

GetNextNeighbor(intv1,intv2);//取v的針對于v2的下一個鄰接點(diǎn)int

InsertVertex(vertexType&v);//插入頂點(diǎn)v

intInsertArc(intv1,intv2,arcTypew);//插入一條邊（或?。?/p>

voidDeleteVertex(intv);//刪除頂點(diǎn)v

voidDeleteArc(intv1,intv2);//刪除邊（或?。﹠7.2.2鄰接表

詳情見教材解釋在鄰接表上,圖的部分成員函數(shù)的實(shí)現(xiàn):template<ClassvertexType,classarcType>intGraph<vertexType,arcType>::GetFirstNeighbor(intv){//查找頂點(diǎn)v的第一個鄰接點(diǎn)在鄰接表中位置

if(v>=0&&v<CurrentNumVertexes){//若給定頂點(diǎn)號合理ArcNode<ArcType>*p=VertexesTable[v].firstarc;

if(p!=NULL)

returnp->adjvex;}

return–1;//若頂點(diǎn)不存在或頂點(diǎn)無關(guān)聯(lián)的邊}7.2.2鄰接表

在鄰接表上,圖的部分成員函數(shù)的實(shí)現(xiàn):template<ClassvertexType,classarcTypeType>intGraph<vertexType,arcType>::GetNextNeighbor(intv1,intv2){//查找頂點(diǎn)v1的在V2之后的下一個鄰接點(diǎn)在鄰接表中位置

if(v1>=0&&v1<CurrentNumVertexes){//若給定頂點(diǎn)號合理ArcNode<ArcType>*p=VertexesTable[v1].firstarc;

while(p!=NULL){

if(p->adjvex==v2&&p->nextarc!=NULL)

returnp->nextarc->adjvex;

elsep=p->nextarc;}//while}//if

return-1;

//若給定頂點(diǎn)號不合理//或沒有找到，則都是失敗}7.2.2鄰接表

template<ClassvertexType,classarcType>intGraph<vertexType,arcType>::InsertArc(intv1,intv2,arcTypew){//在有向圖中插入依附于頂點(diǎn)v1和v2的弧,弧的權(quán)值是w.約定鄰接表中不能有相同的弧

if(v1>=0&&v1<CurrentNumVertexes&&v2>=0&&v2<CurrentNumVertexes){//有這樣的V1,V2

}elsereturn0;}7.2.2鄰接表

（1）查找<v1,v2>這條弧（2）若不存在,則插入新的<v1,v2>這條?。?）否則（已經(jīng)存在），則不用再插入這條弧template<ClassvertexType,classarcType>intGraph<vertexType,arcType>::InsertArc(intv1,intv2,arcTypew){//在有向圖中插入依附于頂點(diǎn)v1和v2的弧,弧的權(quán)值是w.約定鄰接表中不能有相同的弧

if(v1>=0&&v1<CurrentNumVertexes&&v2>=0&&v2<CurrentNumVertexes){//有這樣的V1,V2ArcNode<ArcType>*p=VertexesTable[v1].firstarc;

while(p!=NULL&&p->adjvex!=v2)p=p->nextarc;

if(p==NULL){//說明不存在<v1,v2>這條弧,則插入

q=newArcNode<arcType>(v2,w);//生成新的結(jié)點(diǎn)并插入

return1;}//ifelsereturn0;}elsereturn0;}7.2.2鄰接表

ArcNode(intv,arcTypew):adjvex(v),weight(w),next(NULL){}//構(gòu)造函數(shù)（1）查找<v1,v2>這條?。?）若不存在,則插入新的<v1,v2>這條?。?）否則（已經(jīng)存在），則不用再插入這條弧template<ClassvertexType,classarcType>intGraph<vertexType,arcType>::InsertArc(intv1,intv2,arcTypew){//在有向圖中插入依附于頂點(diǎn)v1和v2的弧,弧的權(quán)值是w.約定鄰接表中不能有相同的弧

if(v1>=0&&v1<CurrentNumVertexes&&v2>=0&&v2<CurrentNumVertexes){//有這樣的V1,V2ArcNode<ArcType>*p=VertexesTable[v1].firstarc;

while(p!=NULL&&p->adjvex!=v2)p=p->nextarc;

if(p==NULL){//說明不存在<v1,v2>這條弧,則插入

q=newArcNode<arcType>(v2,w);//生成新的結(jié)點(diǎn)并插入return1;}//ifelsereturn0;}elsereturn0;}7.2.2鄰接表

怎么插？插在什么位置？最后？最前？template<ClassvertexType,classarcType>intGraph<vertexType,arcType>::InsertArc(intv1,intv2,arcTypew){//在有向圖中插入依附于頂點(diǎn)v1和v2的弧,弧的權(quán)值是w.約定鄰接表中不能有相同的弧

if(v1>=0&&v1<CurrentNumVertexes&&v2>=0&&v2<CurrentNumVertexes){//有這樣的V1,V2ArcNode<ArcType>*p=VertexesTable[v1].firstarc;

while(p!=NULL&&p->adjvex!=v2)p=p->nextarc;

if(p==NULL){//說明不存在<v1,v2>這條弧,則插入

q=newArcNode<arcType>(v2,w);//生成新的結(jié)點(diǎn)并插入q->nextarc=VertexesTable[v1].firstarc;VertexesTable[v1].firstarc=q;

//讓q成為第一個鄰接點(diǎn)

CurrentNumArcs++;return1;}//ifelsereturn0;}elsereturn0;}7.2.2鄰接表

template<classvertexType,classarcType>Graph<vertexType,arcType>::~Graph(){//析構(gòu)函數(shù),逐條釋放邊(弧)鏈表的結(jié)點(diǎn)

for(inti=0;i<CurrentNumVertexes;i++){ArcNode<ArcType>*p=VertexesTable[i].firstarc;while(p!=NULL){//逐條釋放邊(弧)鏈表的結(jié)點(diǎn)

VertexesTable[i].firstarc=p->nextarc;deletep;p=VertexesTable[i].firstarc;}//while

}//for

delete[]VertexesTable;//釋放頂點(diǎn)表}7.2.2鄰接表

7.3圖的遍歷與連通性7.2.3鄰接多重表

引入鄰接多重表結(jié)構(gòu)的原因:在一些較復(fù)雜的問題中,有時需要給被訪問過的邊加以標(biāo)記,若用鄰接表,則需要對一條邊的兩個邊結(jié)點(diǎn)同時作標(biāo)記,但是這兩個頂點(diǎn)不在同一條邊結(jié)點(diǎn)鏈表中,很不方便。為此,引入新的結(jié)構(gòu)——鄰接多重表結(jié)構(gòu)。鄰接多重表主要針對無向圖。7.2.3鄰接多重表

在無向圖的鄰接多重表中,圖的每一條邊用一個邊結(jié)點(diǎn)表示,它由六個域組成。其中:tag是標(biāo)記域,標(biāo)記該邊是否被處理或被搜索過;weight為邊的信息域,用于存儲邊的權(quán)值;adjvex1和adjvex2是頂點(diǎn)域,表示該邊所依附的兩個頂點(diǎn)在圖中的序號;nextarc1域是鏈接指針,指向下一條依附于頂點(diǎn)adjvex1的邊;nextarc2也是鏈接指針,指向下一條依附于頂點(diǎn)adjvex2的邊。7.2.3鄰接多重表

對圖中的每一個頂點(diǎn)用一個頂點(diǎn)結(jié)點(diǎn)表示,它有兩個域組成。其中:data域存儲有關(guān)頂點(diǎn)的信息;firstarc域是鏈接指針,指向第一條依附于該頂點(diǎn)的邊。所有的頂點(diǎn)結(jié)點(diǎn)組成一個順序表。7.2.4十字鏈表

引入十字鏈表的原因:1.對已經(jīng)處理過的弧作標(biāo)記在鄰接表(或逆鄰接表)表示時不方便

2.要同時做到計(jì)算出／入度也不方便(鄰接表只對出度計(jì)算方便,逆鄰接表只對入度計(jì)算方便)為此,引入新的結(jié)構(gòu)——十字鏈表結(jié)構(gòu)。十字鏈表主要針對有向圖。7.2.4十字鏈表

在有向圖的十字鏈表中,圖中的每一條弧用一個弧結(jié)點(diǎn)表示?；〗Y(jié)點(diǎn)的結(jié)構(gòu)與無向圖鄰接多重表中的邊結(jié)點(diǎn)結(jié)構(gòu)類似,也有六個域。其中:tag是標(biāo)記域,標(biāo)記該弧是否被處理或被搜索過;weight為弧的信息域,用于存儲弧的權(quán)值等信息;7.2.4十字鏈表

tailvex表示弧尾頂點(diǎn)序號的頂點(diǎn)域;headvex表示弧頭頂點(diǎn)序號的頂點(diǎn)域;tailnextarc域是鏈接指針,指向下一條以頂點(diǎn)tailvex為始點(diǎn)(弧尾)的弧;headnextarc也是鏈接指針,指向下一條以頂點(diǎn)headvex為終點(diǎn)(弧頭)的弧。7.2.4十字鏈表

對有向圖中的每一個頂點(diǎn)也用一個頂點(diǎn)結(jié)點(diǎn)表示,它由三個域組成。其中:data域存儲有關(guān)頂點(diǎn)的信息;firstinarc域是鏈接指針,指向第一條以該頂點(diǎn)為終點(diǎn)(弧頭)的弧(尾頂點(diǎn));firstoutarc域也是鏈接指針,指向第一條以該頂點(diǎn)為始點(diǎn)(弧尾)的弧(頭頂點(diǎn))。所有的頂點(diǎn)結(jié)點(diǎn)組成一個順序表。在有向圖的十字鏈表中,從頂點(diǎn)結(jié)點(diǎn)中的firstoutarc域出發(fā),由弧結(jié)點(diǎn)中的tailnextarc域鏈接起來的鏈表,正好是原來的鄰接表結(jié)構(gòu)。統(tǒng)計(jì)該鏈表中弧結(jié)點(diǎn)的個數(shù),可求得該頂點(diǎn)的出度。7.2.4十字鏈表

若從頂點(diǎn)結(jié)點(diǎn)的firstintarc域出發(fā),由弧結(jié)點(diǎn)中的headnextarc域鏈接起來的鏈表,正好是原來的逆鄰接表結(jié)構(gòu)。統(tǒng)計(jì)該鏈表中弧結(jié)點(diǎn)的個數(shù),可求得該頂點(diǎn)的入度。7.2.4十字鏈表

7.3圖的遍歷與連通性

7.3圖的遍歷與連通性

對于給定的圖,沿著一些邊(或弧)訪問圖中所有的頂點(diǎn),且使每個頂點(diǎn)僅被訪問一次,這個過程叫做圖的遍歷.

圖的遍歷通常有兩種方法:深度優(yōu)先遍歷(DepthFirstTraversal)和廣度優(yōu)先遍歷(BreadthFirstTraversal).這兩種方法對無向圖和有向圖都是適用的,但在下面的討論中將主要介紹對無向圖的遍歷.7.3.1深度優(yōu)先遍歷

圖的深度優(yōu)先遍歷基于深度優(yōu)先搜索DFS(DepthFirstSearch),深度優(yōu)先搜索(DFS)方法:從圖的頂點(diǎn)V0出發(fā),先訪問頂點(diǎn)V0,再訪問V0的一個未被訪問過的鄰接頂點(diǎn)V1,再從V1出發(fā)訪問V1的某個未被訪問過的鄰接頂點(diǎn),……,直到一個其所有的鄰接頂點(diǎn)都已被訪問過的頂點(diǎn);7.3.1深度優(yōu)先遍歷

圖的深度優(yōu)先遍歷基于深度優(yōu)先搜索DFS(DepthFirstSearch),深度優(yōu)先搜索(DFS)接著退回到尚有鄰接頂點(diǎn)未被訪問過的頂點(diǎn),再從該頂點(diǎn)出發(fā),重復(fù)上述過程(顯然是一個遞歸的過程),……,直到所有的被訪問過的頂點(diǎn)的鄰接頂點(diǎn)都被訪問過為止.下圖(a)給出了深度優(yōu)先搜索的示例.由于該圖是連通的,所以從頂點(diǎn)A出發(fā),通過一次深度優(yōu)先搜索,就可以訪問圖中的所有頂點(diǎn).從圖的頂點(diǎn)V0出發(fā),先訪問頂點(diǎn)V0,再訪問V0的一個未被訪問過的鄰接頂點(diǎn)V1,再從V1出發(fā)訪問V1的某個未被訪問過的鄰接頂點(diǎn),……,直到一個其所有的鄰接頂點(diǎn)都已被訪問過的頂點(diǎn);

接著退回到尚有鄰接頂點(diǎn)未被訪問過的頂點(diǎn),再從該頂點(diǎn)出發(fā),重復(fù)上述過程(顯然是一個遞歸的過程),……,直到所有的被訪問過的頂點(diǎn)的鄰接頂點(diǎn)都被訪問過為止.7.3.1深度優(yōu)先遍歷

圖的深度優(yōu)先遍歷的訪問順序與樹的前序遍歷順序類似.

圖(b)給出了在深度優(yōu)先遍歷的過程中,訪問的所有頂點(diǎn)和經(jīng)過的邊,圖中各頂點(diǎn)旁附加的數(shù)字表示各頂點(diǎn)被訪問的次序.

在圖(b)中,共有n-1條邊連結(jié)了所有n個頂點(diǎn),在此把它稱為圖(a)的深度優(yōu)先搜索生成樹(DFS生成樹).7.3.1深度優(yōu)先遍歷

V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷:V1V2V4V8V5V6V3V7深度遍歷:V1V3V6V8V7V5V2V4V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V87.3.1深度優(yōu)先遍歷

從指定的結(jié)點(diǎn)v開始進(jìn)行深度優(yōu)先搜索(DFS)的算法的步驟是:(1)訪問結(jié)點(diǎn)v,并標(biāo)記v已被訪問;(2)取頂點(diǎn)v的第一個鄰接頂點(diǎn)w;(3)若頂點(diǎn)w不存在,算法結(jié)束;否則繼續(xù)步驟(4);(4)若頂點(diǎn)w未被訪問,則從w開始進(jìn)行深度優(yōu)先搜索(DFS),

然后轉(zhuǎn)步驟(5);否則,直接轉(zhuǎn)步驟(5);(5)令w為頂點(diǎn)v的在原來w之后的下一個鄰接頂點(diǎn),轉(zhuǎn)到步驟(3).7.3.1深度優(yōu)先遍歷

開始標(biāo)志數(shù)組初始化Vi=0Vi訪問過？DFSVi=Vi+1Vi==n？結(jié)束NNYY深度優(yōu)先遍歷算法流程為了實(shí)現(xiàn)圖的深度和廣度遍歷算法,我們要引入一個輔助數(shù)組visited[],其作用是用來標(biāo)志某個頂點(diǎn)是否已經(jīng)被訪問過.7.3.1深度優(yōu)先遍歷

下面給出深度優(yōu)先搜索和深度優(yōu)先遍歷的算法:template<classvertexType,classarcType>voidGraph<vertexType,arcType>::DFTraverse(voidvisit(vertexTypev)){//深度優(yōu)先遍歷任意圖

inti,n=NumberOfVertexes();//取圖的頂點(diǎn)個數(shù)

int*visited=newint[n];//定義訪問標(biāo)記數(shù)組visitedfor(i=0;i<n;i++)visited[i]=0;//訪問標(biāo)記數(shù)組visited初始化

for(i=0;i<n;i++)//對圖中的每一個頂點(diǎn)進(jìn)行判斷

if(!visited[i])DFS(i,visited,visit);delete[]visited;//釋放visited數(shù)組}為了實(shí)現(xiàn)圖的深度和廣度遍歷算法,我們要引入一個輔助數(shù)組visited[],其作用是用來標(biāo)志某個頂點(diǎn)是否已經(jīng)被訪問過。7.3.1深度優(yōu)先遍歷

template<classvertexType,classarcType>voidGraph<vertexType,arcType>::DFTraverse(voidvisit(vertexTypev)){//深度優(yōu)先遍歷任意圖

inti,n=NumberOfVertexes();//取圖的頂點(diǎn)個數(shù)

int*visited=newint[n];//定義訪問標(biāo)記數(shù)組

visitedfor(i=0;i<n;i++)visited[i]=0;//訪問標(biāo)記數(shù)組visited初始化

for(i=0;i<n;i++)//對圖中的每一個頂點(diǎn)進(jìn)行判斷

if(!visited[i])DFS(v,visited,visit);delete[]visited;//釋放

visited}開始標(biāo)志數(shù)組初始化Vi=0Vi訪問過？DFSVi=Vi+1Vi==n？結(jié)束NNYY7.3.1深度優(yōu)先遍歷

template<classvertexType,classarcType>voidGraph<vertexType,arcType>::DFS(constintv,intvisited[],voidvisit(vertexTypev)){//深度優(yōu)先搜索一個連通圖

visit(GetValue(v));//訪問頂點(diǎn)vvisited[v]=1;//頂點(diǎn)v作訪問標(biāo)記

intw=GetFirstNeighbor(v);while(w!=-1){//若頂點(diǎn)w存在

if(!visited[w])DFS(w,visited,visit);w=GetNextNeighbor(v,w);}//重復(fù)檢測v的所有鄰接頂點(diǎn)}7.3.1深度優(yōu)先遍歷

7.3.1深度優(yōu)先遍歷

【例】已知帶權(quán)有向圖的鄰接表如下圖所示。要求:(1)畫出該帶權(quán)有向圖。(2)求出基于該鄰接表的從頂點(diǎn)A出發(fā)的深度優(yōu)先搜索的頂點(diǎn)序列以及DFS生成樹。7.3.2廣度優(yōu)先遍歷

7.3.2廣度優(yōu)先遍歷

圖的廣度優(yōu)先遍歷基于廣度優(yōu)先搜索BFS(BreadthFirstSearch)。

廣度優(yōu)先搜索是從圖中某一頂點(diǎn)v出發(fā),在訪問頂點(diǎn)v后再訪問v的各個未被訪問過的鄰接頂點(diǎn)w1、w2、…、wk。然后再依次訪問w1、w2、…、wk的所有還未被訪問過的鄰接頂點(diǎn)。繼續(xù)從這些訪問過的頂點(diǎn)出發(fā),再訪問它們的所有還未被訪問過的鄰接頂點(diǎn),……,如此下去,直到圖中所有和頂點(diǎn)v由路徑連通的頂點(diǎn)都被訪問到為止。

下圖(a)給出了一個從頂點(diǎn)A出發(fā)進(jìn)行廣度優(yōu)先遍歷的示例。圖(b)給出了由廣度優(yōu)先遍歷得到的廣度優(yōu)先生成樹(BFS生成樹),它由遍歷時訪問過的n個頂點(diǎn)和遍歷時經(jīng)歷的n-1條邊組成,各頂點(diǎn)旁邊附的數(shù)字標(biāo)明了頂點(diǎn)被訪問的順序。

廣度優(yōu)先搜索是從圖中某一頂點(diǎn)v出發(fā),在訪問頂點(diǎn)v后再訪問v的各個未被訪問過的鄰接頂點(diǎn)w1、w2、…、wk。然后再依次訪問w1、w2、…、wk的所有還未被訪問過的鄰接頂點(diǎn)。繼續(xù)從這些訪問過的頂點(diǎn)出發(fā),再訪問它們的所有還未被訪問過的鄰接頂點(diǎn),……,如此下去,直到圖中所有和頂點(diǎn)v由路徑連通的頂點(diǎn)都被訪問到為止。

7.3.2廣度優(yōu)先遍歷

從指定的結(jié)點(diǎn)v開始進(jìn)行廣度優(yōu)先搜索的算法步驟是:(1)訪問結(jié)點(diǎn)v,并標(biāo)記v已被訪問,同時頂點(diǎn)v入隊(duì)列;(2)當(dāng)隊(duì)列空時算法結(jié)束,否則繼續(xù)步驟(3);(3)隊(duì)頭頂點(diǎn)出隊(duì)列為v;(4)取頂點(diǎn)v的第一個鄰接頂點(diǎn)w;(5)若頂點(diǎn)w不存在,轉(zhuǎn)步驟(2)繼續(xù)出隊(duì);否則繼續(xù)步驟(6)(6)若頂點(diǎn)w未被訪問,則訪問結(jié)點(diǎn)w,并標(biāo)記w已被訪問,同時頂點(diǎn)w入隊(duì)列,然后轉(zhuǎn)步驟(7);否則直接轉(zhuǎn)步驟(7);(7)令w為頂點(diǎn)v的在原來w之后的下一個鄰接頂點(diǎn),轉(zhuǎn)到步驟(5)。7.3.2廣度優(yōu)先遍歷

開始訪問V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎？取V下一鄰接點(diǎn)ww訪問過？結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎？隊(duì)頭V出隊(duì)訪問w,置標(biāo)志w入隊(duì)NaaY7.3.2廣度優(yōu)先遍歷

廣度優(yōu)先遍歷的算法:template<classvertexType,classarcType>voidGraph<vertexType,arcType>::BFTraverse(voidvisit(vertexTypev)){inti,n=NumberOfVertexes();//取圖的頂點(diǎn)個數(shù)

int*visited=newint[n];//定義訪問標(biāo)記數(shù)組visitedfor(i=0;i<n;i++)visited[i]=0;//訪問標(biāo)記數(shù)組visited初始化

for(i=0;i<n;i++)//對圖中的每一個頂點(diǎn)進(jìn)行判斷

if(!visited[i])BFS

(i,visited,visit);delete[]visited;//釋放visited}7.3.2廣度優(yōu)先遍歷

template<classvertexType,classarcType>voidGraph<vertexType,arcType>::BFS(const

intv0,intvisited[],voidvisit(vertexTypev0)){linkqueue<int>q;//定義隊(duì)列qvisit(GetValue(v0));//訪問頂點(diǎn)vvisited[v0]=1;//頂點(diǎn)v作已訪問標(biāo)記

q.EnQueue(v0);//頂點(diǎn)v進(jìn)隊(duì)列q開始訪問V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎？取V下一鄰接點(diǎn)ww訪問過結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎？隊(duì)頭V出隊(duì)訪問w,置標(biāo)志w入隊(duì)NY7.3.2廣度優(yōu)先遍歷

while(!q.IsEmpty()){v=q.DeQueue();//隊(duì)頭元素出隊(duì)列

intw=GetFirstNeighbor(v);while(w!=-1){//若鄰接頂點(diǎn)w存在

if(!visited[w]){//若該鄰接頂點(diǎn)未訪問過

visit(GetValue(w));//訪問頂點(diǎn)wvisited[w]=1;//頂點(diǎn)w作已訪問標(biāo)記

q.EnQueue(w);//頂點(diǎn)w進(jìn)隊(duì)列q

}//if(!visited[w])w=GetNextNeighbor(v,w);}//While(w!=-1)

//重復(fù)檢測v的所有鄰接頂點(diǎn)

}//while(!q.IsEmpty())//外層循環(huán),判隊(duì)列空否}//BFS開始訪問V0,置標(biāo)志求V鄰接點(diǎn)ww存在嗎？取V下一鄰接點(diǎn)ww訪問過結(jié)束NYNYBFS初始化隊(duì)列V0入隊(duì)隊(duì)列空嗎？隊(duì)頭V出隊(duì)訪問w,置標(biāo)志w入隊(duì)NY7.3.2廣度優(yōu)先遍歷

例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

20123451fr遍歷序列:10123454fr遍歷序列:1401234543fr遍歷序列:143假設(shè)頂點(diǎn)從數(shù)組的下標(biāo)1開始存儲,隊(duì)列頭指針指向真正的隊(duì)頭元素,隊(duì)尾指針指向隊(duì)尾元素的后一個位置。例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2012345432fr遍歷序列:1432012345

32fr遍歷序列:1432012345

325fr遍歷序列:14325假設(shè)頂點(diǎn)從數(shù)組的下標(biāo)1開始存儲,隊(duì)列頭指針指向真正的隊(duì)頭元素,隊(duì)尾指針指向隊(duì)尾元素的后一個位置。012345

25fr遍歷序列/p>

5fr遍歷序列/p>

fr遍歷序列:14325例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2假設(shè)頂點(diǎn)從數(shù)組的下標(biāo)1開始存儲,隊(duì)列頭指針指向真正的隊(duì)頭元素,隊(duì)尾指針指向隊(duì)尾元素的后一個位置。以上都是以無向圖為例,實(shí)際上DFS和BFS對有向圖也是適用的7.3.3連通分量對于連通圖,從任一頂點(diǎn)出發(fā),只需一次調(diào)用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法就可以訪問到圖中的所有頂點(diǎn);

對于非連通圖時,從圖中某一頂點(diǎn)出發(fā),一次調(diào)用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能訪問到圖中的所有頂點(diǎn),只能訪問到該頂點(diǎn)所在的極大連通子圖(即連通分量)的所有頂點(diǎn)。非連通圖有m個連通分量,就要m次調(diào)用DFS或BFS才能訪問圖中的所有頂點(diǎn)。若從圖的每一個連通分量中的某一個頂點(diǎn)出發(fā)進(jìn)行搜索,就可以求得圖的所有連通分量(所謂連通分量是指非連通圖中極大連通子圖)對應(yīng)的DFS或BFS生成樹。

7.4最小生成樹

一個連通圖的生成樹是原圖的極小連通子圖,它包含原圖中的所有n個頂點(diǎn)和使n個頂點(diǎn)連通的n-1條邊。這意味著對于生成樹來說,若刪除它的一條邊,就會使生成樹變成非連通圖;若給它增加一條邊,就會形成圖中的一個回路（樹是要求不能有回路的）。另一方面,一個連通圖的生成樹不是唯一的；

使用不同的方法遍歷圖,可以得到不同的生成樹;

從不同的頂點(diǎn)出發(fā),也可能得到不同的生成樹;

而且生成樹有時還和圖的存儲結(jié)構(gòu)中具體的結(jié)點(diǎn)順序有關(guān),比如鄰接表中各鄰接點(diǎn)的次序。“極小”：邊不能再少了，否則不連通點(diǎn)不能再少了，因?yàn)檫@個概念要求必須達(dá)到n個頂點(diǎn)對于一個有n個頂點(diǎn)的帶權(quán)的連通圖(即網(wǎng)絡(luò)),可以有不同的生成樹,每一棵生成樹都可以構(gòu)成通信網(wǎng)絡(luò)。我們希望能夠根據(jù)各條邊上的權(quán)值,選擇一棵總造價最小的生成樹,這就是構(gòu)造網(wǎng)絡(luò)的最小(代價)生成樹(Minimum-costSpanningTree)問題。如何找這樣的最小生成樹？常用的構(gòu)造網(wǎng)絡(luò)的最小(代價)生成樹算法有:

克魯斯卡爾(Kruskal)算法和普里姆(Prim)算法。

7.4最小生成樹

克魯斯卡爾(Kruskal)算法

7.4.1克魯斯卡爾算法

克魯斯卡爾(Kruskal)算法的基本思想是:設(shè)連通網(wǎng)N=(V,E),令最小生成樹為T=(V,TE)初始狀態(tài)為只有n個頂點(diǎn)而無邊的非連通圖T=(V,{}),每個頂點(diǎn)自成一個連通分量。在E中選取代價最小的邊,并從E中刪除該邊。若該邊依附的頂點(diǎn)落在T中不同的連通分量上,則將此邊加入到T中;否則,舍去此邊,選取下一條代價最小的邊。依此類推,直至T中所有頂點(diǎn)都在同一連通分量上為止。對于右圖(a)所示的連通網(wǎng)絡(luò),下圖中(a)(f)給出了按克魯斯卡爾算法生成最小生成樹的過程。算法的詳細(xì)實(shí)現(xiàn)見教材P226-228,了解即可。普里姆(Prim)算法7.4.1普里姆算法

普里姆(Prim)算法的基本思想是:

假設(shè)連通網(wǎng)絡(luò)為N＝(V,E);TE為N的最小生成樹上邊的集合,開始時TE=;U為算法在構(gòu)造最小生成樹過程中已得到的頂點(diǎn)集,開始時U={u0}(u0V)。算法從N中的某一頂點(diǎn)u0出發(fā),選擇與u0關(guān)聯(lián)的具