數(shù)據(jù)結(jié)構(gòu)-第七章

數(shù)據(jù)結(jié)構(gòu)C++實(shí)現(xiàn)第七章圖繆淮扣顧訓(xùn)穰沈俊編著科學(xué)出版社

新世紀(jì)計(jì)算機(jī)專(zhuān)業(yè)系列教材

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

在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是層次型的，樹(shù)中除葉子以外的每一個(gè)數(shù)據(jù)元素可以和它下一層的多個(gè)數(shù)據(jù)元素存在關(guān)系；但除根元素以外的每一個(gè)數(shù)據(jù)元素只能且必須和它上一層中的一個(gè)數(shù)據(jù)元素存在關(guān)系。而在圖形結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是任意的，圖中每一個(gè)數(shù)據(jù)元素可以和任何其它數(shù)據(jù)元素相關(guān)聯(lián)。

本章主要介紹圖的存儲(chǔ)結(jié)構(gòu)以及圖的基本操作的實(shí)現(xiàn)；并利用圖論的知識(shí)討論圖的應(yīng)用的實(shí)現(xiàn)。圖的基本概念

圖是由數(shù)據(jù)元素的集合及數(shù)據(jù)元素間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph＝（V,E)，其中：V={x|x

某個(gè)數(shù)據(jù)對(duì)象}是數(shù)據(jù)元素的集合，在圖中，數(shù)據(jù)元素一般被稱(chēng)為頂點(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的一條單向通路，它是有方向的。

在圖中如果頂點(diǎn)對(duì)(v、w)是無(wú)序的，則稱(chēng)此圖為無(wú)向圖(undirectedgraph)，頂點(diǎn)對(duì)(v、w)稱(chēng)為與頂點(diǎn)v和頂點(diǎn)w相關(guān)聯(lián)的一條邊。由于這條邊沒(méi)有方向，所以(v、w)與(w、v)是同一條邊；在圖中如果頂點(diǎn)對(duì)＜v、w＞是有序的，則稱(chēng)此圖為有向圖(directedgraph)，頂點(diǎn)對(duì)＜v、w＞稱(chēng)為從頂點(diǎn)v到頂點(diǎn)w的一條有向邊（又稱(chēng)為弧），其中v稱(chēng)為有向邊＜v、w＞的始點(diǎn)（弧尾）；w稱(chēng)為有向邊＜v、w＞的終點(diǎn)（弧頭）。顯然＜v、w＞與＜w、v＞是兩條不同的弧。

一般表示無(wú)向圖中邊的頂點(diǎn)對(duì)用一對(duì)圓括號(hào)括起來(lái)；表示有向圖中弧的頂點(diǎn)對(duì)用一對(duì)尖括號(hào)括起來(lái)。

右圖所示的4個(gè)圖，其中G1和G2是無(wú)向圖，G3和G4是有向圖。

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

1．完全圖(completegraph)：在有n個(gè)頂點(diǎn)的無(wú)向圖中，若有n(n-1)／2條邊，則稱(chēng)此無(wú)向圖為完全無(wú)向圖。在有n個(gè)頂點(diǎn)的有向圖中，若有n(n-1)條邊，則稱(chēng)此圖為完全有向圖。在完全圖中邊（弧）數(shù)目達(dá)到最大。2．權(quán)(weight)：在某些圖的應(yīng)用中，邊（?。┥暇哂信c它相關(guān)的系數(shù)，稱(chēng)之為權(quán)。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離、花費(fèi)的代價(jià)、所需的時(shí)間、次數(shù)等。這種帶權(quán)圖也被稱(chēng)為網(wǎng)絡(luò)(network)。3．鄰接點(diǎn)(adjacentvertex)：如果(v，w)是無(wú)向圖G中的一條邊，則稱(chēng)v與w互為鄰接頂點(diǎn)，且邊(v，w)稱(chēng)為依附于頂點(diǎn)v和w。如果＜v、w＞是有向圖G中的一條弧，則稱(chēng)頂點(diǎn)v鄰接到頂點(diǎn)w（也稱(chēng)v是w的前驅(qū)），頂點(diǎn)w鄰接自頂點(diǎn)v（也稱(chēng)w是v的后繼），弧＜v，w＞與頂點(diǎn)v與w相關(guān)聯(lián)。4．子圖(subgraph)：設(shè)有兩個(gè)圖G＝(V，E)和G’＝(V’，E’)。若V’V且E’E，則稱(chēng)圖G’是圖G的子圖。下圖(a)和(b)給出無(wú)向圖G1的兩個(gè)子圖，圖(c)和(d)給出有向圖G3的兩個(gè)子圖。5．頂點(diǎn)的度(degree)：在無(wú)向圖中，一個(gè)頂點(diǎn)v的度是依附于頂點(diǎn)v的邊的條數(shù)，記作TD(v)。在有向圖中，以頂點(diǎn)v為始點(diǎn)的有向邊的條數(shù)稱(chēng)為頂點(diǎn)v的出度，記作OD(v)；以頂點(diǎn)v為終點(diǎn)的有向邊的條數(shù)稱(chēng)為頂點(diǎn)v的入度，記作ID(v)。有向圖中頂點(diǎn)v的度等于該頂點(diǎn)的入度與出度之和：TD(v)＝ID(v)十OD(v)。6．路徑(path)：在圖G＝(V，E)中，若從頂點(diǎn)vi出發(fā)，沿一些邊（或?。┙?jīng)過(guò)一些頂點(diǎn)vp1、vp2、…、vpk，到達(dá)頂點(diǎn)vj，則頂點(diǎn)序列(vi、vp1、vp2、…、vpk、vj)被稱(chēng)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。7．路徑長(zhǎng)度(pathlength)：對(duì)于不帶權(quán)的圖，路徑長(zhǎng)度是指此路徑上邊的數(shù)目。對(duì)于帶權(quán)圖，路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。8．簡(jiǎn)單路徑與回路(cycle)：對(duì)于一路徑（v1、v2、…、vm），若路徑上各頂點(diǎn)均不相同，則稱(chēng)這路徑為簡(jiǎn)單路徑。若路徑上第一個(gè)頂點(diǎn)v1和最后一個(gè)頂點(diǎn)vm相同，則稱(chēng)這樣的路徑為回路或環(huán)。9．連通圖與連通分量：在無(wú)向圖中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱(chēng)頂點(diǎn)vi與vj是連通的。如果無(wú)向圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱(chēng)此無(wú)向圖是連通圖。非連通圖的極大連通子圖（包括所有連通的頂點(diǎn)和這些頂點(diǎn)依附的所有的邊）叫做連通分量。如右圖（a）所示是一個(gè)非連通圖，圖（b）所示是相應(yīng)的三個(gè)連通分量。10．強(qiáng)連通圖與強(qiáng)連通分量(stronglyconnecteddigraph)：在有向圖中，若對(duì)于頂點(diǎn)vi和vj，存在一條從vi到vj和從vj到vi的路徑，則稱(chēng)頂點(diǎn)vi和頂點(diǎn)vj是強(qiáng)連通。如果有向圖中任意兩個(gè)頂點(diǎn)都是強(qiáng)連通的，則稱(chēng)此有向圖為強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。11．生成樹(shù)(spanningtree)：一個(gè)連通圖的生成樹(shù)是它的極小連通子圖，它包含圖中全部n個(gè)頂點(diǎn)和僅使這n個(gè)頂點(diǎn)連通的n-1條邊。如果一個(gè)有向圖只有一個(gè)入度為零的頂點(diǎn)，且其它頂點(diǎn)的入度均為1，則稱(chēng)這個(gè)有向圖為有向樹(shù)。一個(gè)有向圖的生成森林由若干棵有向樹(shù)組成，生成森林含有圖中所有的頂點(diǎn)，且只有足以構(gòu)成若干棵互不相交的有向樹(shù)的弧。圖的基本操作圖的基本操作一般有：（1）InsertVertex（vertex）：在圖中插入一個(gè)頂點(diǎn)vertex。（2）InsertEdge（v1，v2）：在圖中插入一條邊（v1,v2）。（3）DeleteVertex（v）：在圖中刪除一個(gè)頂點(diǎn)v及依附于v的邊。（4）DeleteEdge（v1，v2）：在圖中刪除一條邊（或?。＃?）GetWeight（v1，v2）：在圖中取邊（v1、v2）上的權(quán)。（6）GetFirstNeighbor（intv）：在圖中取頂點(diǎn)v的第一個(gè)鄰接點(diǎn)。（7）GetNextNeighbor（intv1，intv2）：在圖中取頂點(diǎn)v1的在v2后的下一個(gè)鄰接點(diǎn)。（8）Travers（）：遍歷圖，按某種次序依次訪(fǎng)問(wèn)圖中的每一個(gè)頂點(diǎn)，并使每一個(gè)頂點(diǎn)只被訪(fǎng)問(wèn)一次。（9）IsEmpty（）：判斷圖是否為空。

由于在圖中，任何兩個(gè)頂點(diǎn)之間都可能存在聯(lián)系，所以無(wú)法在存儲(chǔ)位置上反映數(shù)據(jù)元素之間的聯(lián)系，因此圖沒(méi)有順序存貯結(jié)構(gòu)。

按圖中頂點(diǎn)之間的聯(lián)系，圖的存儲(chǔ)結(jié)構(gòu)似乎采用多重鏈表表示比較恰當(dāng)。

但是若采用多重鏈表，則鏈表中結(jié)點(diǎn)的結(jié)構(gòu)難以確定。因?yàn)榻Y(jié)點(diǎn)中的指針數(shù)若按頂點(diǎn)度的最大值來(lái)設(shè)置，則會(huì)浪費(fèi)空間，因?yàn)橛泻芏囗旤c(diǎn)的度小于最大值；若頂點(diǎn)的指針數(shù)按每個(gè)頂點(diǎn)的度數(shù)來(lái)設(shè)置，則存儲(chǔ)結(jié)構(gòu)中會(huì)有很多頂點(diǎn)的結(jié)構(gòu)不一致，給圖的運(yùn)算帶來(lái)困難。因此，圖的存儲(chǔ)結(jié)構(gòu)不宜采用多重鏈表。

圖的存貯結(jié)構(gòu)應(yīng)根據(jù)具體問(wèn)題的要求來(lái)設(shè)計(jì)。常用的存貯結(jié)構(gòu)有鄰接矩陣、鄰接表、鄰接多重表和十字鏈表。

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

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

下圖給出了無(wú)向圖、有向圖和有向網(wǎng)的鄰接矩陣。其中一維數(shù)組Vertexes[]用于存儲(chǔ)頂點(diǎn)的信息，二維數(shù)組Arcs[][]用于存儲(chǔ)邊（或?。┑男畔?。

從圖中可知，無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，將第i行的元素值或第i列的元素值累加起來(lái)就得到頂點(diǎn)i的度。

有向圖的鄰接矩陣可能不對(duì)稱(chēng)。如果第i行第j列為1，則表示有一條從頂點(diǎn)Vi到頂點(diǎn)Vj的有向邊，將第j列的所有元素值累加起來(lái)就得到頂點(diǎn)Vj的入度ID(Vj)；將第i行的所有元素值累加起來(lái)就得到頂點(diǎn)Vi的出度OD(Vi)。即鄰接矩陣作為存儲(chǔ)表示的圖的類(lèi)聲明：const

intMaxVertexes=20;//最大的頂點(diǎn)數(shù)template<classvertexType,classarcType>classGraph{private:SeqList<vertexType>Vertexes(MaxVertexes);//存儲(chǔ)頂點(diǎn)信息的順序表

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

intCurrentNumArcs;//當(dāng)前的邊（或?。?shù)

intFindVertex(SeqList<vertexType>&L;constvertexType&v)//查找頂點(diǎn)v是否存在{returnL.Find(v);}

intGetVertexPos(constvertexType&v)//取頂點(diǎn)v在數(shù)組中的位置{returnFindVertex(Vertexes,v);}public:Graph(

intnum=MaxVertexes);//構(gòu)造函數(shù)

intIsEmpty()const{returnVertexes.IsEmpty();}

//判斷圖是否為空

intNumberOfVertexes(){returnVertexes.size;}

//取圖的頂點(diǎn)數(shù)

intNumberOfArcs(){returnCurrentNumArcs;}//取圖的邊（或?。?shù)

vertexTypeGetValue(

intv)

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

arcTypeGetWeight(

intv1,

intv2);

//取邊(v1,v2)(或弧<v1,v2>)上的權(quán)

intGetFirstNeighbor(

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

intGetNextNeighbor(

intv1,

intv2);//取圖中頂點(diǎn)v1的在v2之后的下一個(gè)鄰接點(diǎn)的序號(hào)。如果不存在返回-1

intInsertVertex(vertexType&v);//在圖中插入頂點(diǎn)v

intInsertArc(

intv1,

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

voidDeleteVertex(

intv);

//刪除頂點(diǎn)v，及依附于v的邊（或?。?/p>

voidDeleteArc(

intv1,

intv2);//在圖中刪除依附于頂點(diǎn)v1和v2的邊（或弧）}在鄰接矩陣上，圖的部分成員函數(shù)的實(shí)現(xiàn):template<classvertexType,classarcType>Graph<vertexType,arcType>::Graph(

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

for(

inti=0;i<num;i++)//鄰接矩陣初始化

for(

intj=0;j<num;j++)arc[i][j]=0;CurrentNumArcs=0;//當(dāng)前邊（或弧）數(shù)為0}template<classvertexType,classarcType>

vertexTypeGraph<vertexType,arcType>::GetValue(

intv){//取圖中第v個(gè)頂點(diǎn)

if(v<0||v>=Vertexes.len)//如果頂點(diǎn)v不存在，則返回空

return

NULL;

else

returnVertexes.GetData[v];}template<classvertexType,classarcType>arcTypeGraph<vertexType,arcType>::GetWeight(

intv1,

intv2){//取出以頂點(diǎn)v1和v2為兩端點(diǎn)的邊上的權(quán)值

if(v1<0||v1>=Vertexes.len||v2<0||v2>Vertexes.len)

return-1;//如果頂點(diǎn)v1或v2不存在，則返回-1

else

returnArcs[v1][v2];}template<classvertexType,classarcType>intGraph<vertexType,arcType>::GetFirstNeighbor(const

intv){//取出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置

if(v>=0&&v<Vertexes.len){

for(

intj=0;j<Vertexes.len;j++)

if(Arcs[v][j]==1)

returnj}

return

-1;}template<classvertexType,classarcType>

intGraph<vertexType,arcType>::GetNextNeighbor(

intv1,

intv2){//取圖中頂點(diǎn)v1的在v2之后的下一個(gè)鄰接點(diǎn)的序號(hào)。如果不存在返回-1

if(v1>=0&&v1<Vertexes.len

&&v2>=0&&v2<Vertexes.len){

for(

intj=v2+1;j<Vertexes.len;col++)

if(Arcs[v1][j]==1)

returnj;}

return

-1;}template<classvertexType,classarcType>

intGraph<vertexType,arcType>::InsertVertex(vertexType&v){//在圖中插入頂點(diǎn)v。插入成功，返回1；否則返回0

returnVertexes.insert(v,Vertexes.len);//在頂點(diǎn)數(shù)組Vertexes的最后插入v}template<classvertexType,classarcType>

intGraph<vertexType,arcType>::InsertArc(

intv1,intv2,arcTypeweight){//在圖中插入弧<v1v2>。插入成功，返回1；否則返回0。weight是相應(yīng)弧的信息

if(v1<0||v1>=Vertexes.len||v2<0||v2>Vertexes.len)//如果頂點(diǎn)v1或v2不存在，則返回0

return0;Arcs[v1][v2]=weight;CurrentNumArcs++;

return1;}template<classvertexType,classarcType>voidGraph<vertexType,arcType>::DeleteVertex(

intv){//刪除頂點(diǎn)v，及依附于v的弧

for(

inti=0;i<Vertexes.len;i++)//鄰接矩陣初始化

for(

intj=0;j<Vertexes.len;j++)

if(i==v||j==v)&&arc[i][j]!=0){arc[i][j]=0;CurrentNumArcs--;}Vertexes.Delete(v);}template<classvertexType,classarcType>voidGraph<vertexType,arcType>::DeleteArc(

intv1,

intv2);//在圖中刪除弧<v1,v2>

if(v1<0||v1>=Vertexes.len||v2<0||v2>Vertexes.len)

return0;//如果頂點(diǎn)v1或v2不存在，則返回0

Arcs[v1][v2]=0;CurrentNumArcs--;

return1;}鄰接表

鄰接表是鄰接矩陣的改進(jìn)。它把鄰接矩陣的每一行改為一個(gè)單鏈表。

對(duì)于無(wú)向圖，把依附于同一個(gè)頂點(diǎn)的邊鏈接在同一個(gè)單鏈表中稱(chēng)為邊鏈表，邊鏈表中的每一個(gè)結(jié)點(diǎn)代表一條邊叫做邊結(jié)點(diǎn)。在邊結(jié)點(diǎn)中保存著與該邊相關(guān)聯(lián)的另一頂點(diǎn)的序號(hào)和指向同一鏈表中下一個(gè)邊結(jié)點(diǎn)的指針；

對(duì)于有向圖，把從同一個(gè)頂點(diǎn)發(fā)出的弧鏈接在同一個(gè)單鏈表中稱(chēng)為弧鏈表，弧鏈表的每一個(gè)結(jié)點(diǎn)代表一條弧叫做弧結(jié)點(diǎn)，在弧結(jié)點(diǎn)中保存著該弧的弧頭頂點(diǎn)序號(hào)和指向同一鏈表中下一個(gè)弧結(jié)點(diǎn)的指針。如果是帶權(quán)圖，則在邊（?。┙Y(jié)點(diǎn)中還要保存該邊（或弧）上的權(quán)值。

在鄰接表中，對(duì)于圖中的每一個(gè)頂點(diǎn)也用一個(gè)結(jié)點(diǎn)表示，稱(chēng)為頂點(diǎn)結(jié)點(diǎn)。頂點(diǎn)結(jié)點(diǎn)中保存了該頂點(diǎn)的信息和指向該頂點(diǎn)相應(yīng)的邊（?。╂湵淼闹羔槨Ｋ械捻旤c(diǎn)結(jié)點(diǎn)用順序表存儲(chǔ)，并假設(shè)頂點(diǎn)的序號(hào)為數(shù)組的下標(biāo)。

下圖給出了無(wú)向圖的鄰接表表示。從無(wú)向圖的鄰接表中可以看到，同一條邊在鄰接表中出現(xiàn)了兩次，這是因?yàn)?vi，vj)與(vj，vi)雖是同一條邊，但在鄰接表中，(vi，vj)對(duì)應(yīng)的邊結(jié)點(diǎn)在頂點(diǎn)vi的邊鏈表中；(vj，vi)對(duì)應(yīng)的邊結(jié)點(diǎn)在頂點(diǎn)vj的邊鏈表中。如果想知道頂點(diǎn)vi的度，只需統(tǒng)計(jì)頂點(diǎn)vi的邊鏈表中邊結(jié)點(diǎn)的個(gè)數(shù)即可。

下圖（b）所示的是有向圖的鄰接表表示。在有向圖的鄰接表中，一條弧在鄰接表中只出現(xiàn)一次。如果統(tǒng)計(jì)頂點(diǎn)vi的弧鏈表中的弧結(jié)點(diǎn)個(gè)數(shù)，只能得到該頂點(diǎn)的出度，所以這種鏈表也稱(chēng)為出弧表；若想要知道該頂點(diǎn)的入度，必須檢測(cè)其它所有的弧鏈表，看有多少個(gè)弧結(jié)點(diǎn)的弧頭頂點(diǎn)序號(hào)為vi，顯然，這是十分不方便的。

為此，對(duì)有向圖可以建立逆鄰接表，如圖(c)所示。在有向圖的逆鄰接表中，頂點(diǎn)vi的弧鏈表中鏈接的是所有進(jìn)入該頂點(diǎn)的弧，所以也稱(chēng)為入弧表。

對(duì)于帶權(quán)圖(網(wǎng)絡(luò))，必須在鄰接表的邊結(jié)點(diǎn)中增加一個(gè)存放邊上的權(quán)值的域weight。如下圖所示的是一個(gè)帶權(quán)圖的鄰接表表示。圖的鄰接表表示的類(lèi)定義：const

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

structArcNode{//定義邊結(jié)點(diǎn)friend

classGraph<classvertexType,classarcType>;

intadjvex;//和邊（或?。┫嚓P(guān)聯(lián)的另一個(gè)頂點(diǎn)序號(hào)

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ù)}template<classarcType,classvertexType>

structVertexNode{//定義頂點(diǎn)結(jié)點(diǎn)friend

classGraph<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ù)組中的位置public:Graph:CurrentNumVertexes(0),CurrentNumArcs(0){}Graph(vertexTypev[],

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

intIsEmpty()const{returnCurrentNumVertexes==0;}

intNumberOfVertexes(){returnCurrentNumVertexes;}

intNumberOfArcs(){returnCurrentNumArcs;}

vertexTypeGetValue(

intv)

arcTypeGetWeight(

intv1,

intv2);

intGetFirstNeighbor(

intv);

intGetNextNeighbor(

intv1,

intv2);

intInsertVertex(vertexType&v);

intInsertArc(

intv1,

intv2,arcTypew);

voidDeleteVertex(

intv);

voidDeleteArc(

intv1,

intv2);}在鄰接矩陣上，圖的部分成員函數(shù)的實(shí)現(xiàn)：template<classvertexType,classarcType>intGraph<vertexType,arcType>::GetVertexPos(constvertexType&v){//根據(jù)頂點(diǎn)名vertex查找該頂點(diǎn)在鄰接表中的位置

for(

inti=0;i<CurrentNumVertex;i++)

if(VertexesTable[i].data==v)returni;

return-1;}template<classvertexType,classarcType>Graph<vertexType,arcType>::Graph(vertexTypev[],

intnum=MaxVertexes):CurrentNumVertexes(0),CurrentNumArcs(0){

inte,t,h;

vertexTypetail,head;

arcTypew;VertexesTable=newVertexNode<arcType,vertexType>[MaxVertexes];//創(chuàng)建頂點(diǎn)表}for(

inti=0;i<num;i++)//輸入各頂點(diǎn)信息{InsertVertex(v[i]);}//在頂點(diǎn)表中插入頂點(diǎn)v[i]

cin>>e;//輸入邊的條數(shù)

for(i=0;i<e;i++){//逐條輸入邊

cin>>tail>>head>>w;//輸入一條邊

while((t=GetVertexPos(tail))==-1)

cout<<”輸入的頂點(diǎn)(tail)不存在”;

while((h=GetVertexPos(head))==-1)

cout<<”輸入的頂點(diǎn)(head)不存在”;;

InsertArc(k,j,weight);//插入一條邊}

template<classvertexType,classarcType>Graph<vertexType,arcType>::~Graph(){

for(

inti=0;i<CurrentNumVertexes;i++){ArcNode<ArcType>*p=VertexesTable[i].firstadj;

while(p!=NULL){//逐條邊釋放

VertexesTable[i].firstadj=p→nextarc;

deletep;p=VertexesTable[i].firstadj;}}

delete[]VertexesTable;//釋放頂點(diǎn)表}template<ClassvertexType,classarcType>

vextexTypeGraph<vertexType,arcType>::GetValue(

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

if(v>=0&&v<CurrentNumVertexes)

return

VertexesTable[v].data;

return

NULL;}template<ClassvertexType,classarcType>arcTypeGraph<vertexType,arcType>::GetWeight(

intv1,

intv2)

if(v1>=0&&v1<CurrentNumVertexes&&v2>=0&&v2<CurrentNumVertexes){ArcNode<ArcType>*p=NodeTable[v1].firstarc;

while(p!=NULL){

if(p→adjvex==v2)returnp→weight;

elsep=p→nextarc

}}

return

NULL;}template<ClassvertexType,classarcType>

intGraph<vertexType,arcType>::GetFirstNeighbor(

intv){

if(v>=0&&v<CurrentNumVertexes){

ArcNode<ArcType>*p=VertexesTable[v].firstadj;

if(p!=NULL)

returnp→adjvex;}

return–1;//若頂點(diǎn)不存在或頂點(diǎn)無(wú)關(guān)聯(lián)的邊}template<ClassvertexType,classarcTypeType>

intGraph<vertexType,arcType>::GetNextNeighbor(

intv1,

intv2){

if(v1!=-1){Edge<ArcType>*p=VertexesTable[v1].firstadj;

while(p!=NULL){

if(p→adjvex==v2&&p→nextarc!=NULL)

returnp→nextarc→adjvex;

elsep=p→nextarc;}}

return-1;//沒(méi)有查到下一個(gè)鄰接頂點(diǎn)返回-1}template<ClassvertexType,classarcTypeType>

intGraph<vertexType,arcType>::

InsertVertex(vertexType&v){

if(CurrentNumVertexes<MaxVertexes-1){

VertexesTable[CurrentNumVertexes].data=v;VertexesTable[CurrentNumVertexes].firstadj=NULL;CurrentNumVertexes++;

return1;}

return0;//否則返回0}鄰接多重表

在無(wú)向圖的鄰接多重表中，圖的每一條邊用一個(gè)邊結(jié)點(diǎn)表示，它由六個(gè)域組成。

其中，tag是標(biāo)記域，標(biāo)記該邊是否被處理或被搜索過(guò)；wieght為邊的信息域，用于存儲(chǔ)邊的權(quán)值；adjvex1和adjvex2是頂點(diǎn)域，表示該邊所依附的兩個(gè)頂點(diǎn)在圖中的序號(hào)；

nextarc1域是鏈接指針，指向下一條依附于頂點(diǎn)adjvex1的邊；nextarc2也是鏈接指針，指向下一條依附于頂點(diǎn)adjvex2的邊。對(duì)圖中的每一個(gè)頂點(diǎn)用一個(gè)頂點(diǎn)結(jié)點(diǎn)表示，它有兩個(gè)域組成。其中，data域存儲(chǔ)有關(guān)頂點(diǎn)的信息；firstarc域是鏈接指針，指向第一條依附于該頂點(diǎn)的邊。所有的頂點(diǎn)結(jié)點(diǎn)組成一個(gè)順序表。下圖所示，給出了無(wú)向圖的鄰接多重表表示，及其這兩種結(jié)點(diǎn)的示例。在無(wú)向圖的鄰接多重表中，所需存儲(chǔ)空間與表示無(wú)向圖的鄰接表相同。

下面給出鄰接多重表的類(lèi)定義：const

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

structArcNode{friend

classGraph<classvertexType,classarcType>;

inttag;//邊的處理標(biāo)志

arcTypeweight;//邊（或弧）上的信息（權(quán)）

intadjvex1,adjvex2;//和邊相關(guān)聯(lián)的兩個(gè)頂點(diǎn)序號(hào)

ArcNode<arcType>*nextarc1,*nextarc2;}template<classarcType,classvertexType>

structVertexNode{//定義頂點(diǎn)結(jié)點(diǎn)friend

classGraph<classvertexType,class

arcType>;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);public:Graph:CurrentNumVertexes(0),CurrentNumArcs(0){}Graph(vertexTypev[],

intnum=MaxVertexes);//構(gòu)造函數(shù)~Graph();//析構(gòu)函數(shù)}十字鏈表

在有向圖的十字鏈表中，圖中的每一條弧用一個(gè)弧結(jié)點(diǎn)表示?；〗Y(jié)點(diǎn)的結(jié)構(gòu)與無(wú)向圖鄰接多重表中的邊結(jié)點(diǎn)結(jié)構(gòu)類(lèi)似，也有六個(gè)域。其中，tag是標(biāo)記域，標(biāo)記該弧是否被處理或被搜索過(guò)；wieght為弧的信息域，用于存儲(chǔ)弧的權(quán)值等信息；tailvex和headvex是分別表示弧尾頂點(diǎn)序號(hào)和弧頭頂點(diǎn)序號(hào)的頂點(diǎn)域；tailnextarc域是鏈接指針，指向下一條以頂點(diǎn)tailvex為始點(diǎn)（弧尾）的??；

eadnextarc也是鏈接指針，指向下一條以頂點(diǎn)headvex為終點(diǎn)（弧頭）的弧。對(duì)有向圖中的每一個(gè)頂點(diǎn)也用一個(gè)頂點(diǎn)結(jié)點(diǎn)表示，它由三個(gè)域組成。其中，data域存儲(chǔ)有關(guān)頂點(diǎn)的信息；firstinarc域是鏈接指針，指向第一條以該頂點(diǎn)為終點(diǎn)的?。籪irstoutarc域也是鏈接指針，指向第一條以該頂點(diǎn)為始點(diǎn)的弧。所有的頂點(diǎn)結(jié)點(diǎn)組成一個(gè)順序表。

下圖給出了有向圖十字鏈表表示示例及其頂點(diǎn)結(jié)點(diǎn)和弧結(jié)點(diǎn)的結(jié)構(gòu)。

在有向圖的十字鏈表中，從頂點(diǎn)結(jié)點(diǎn)中的firstoutarc域出發(fā)，由弧結(jié)點(diǎn)中的tailnextarc域鏈接起來(lái)的鏈表，正好是原來(lái)的鄰接表結(jié)構(gòu)。統(tǒng)計(jì)該鏈表中弧結(jié)點(diǎn)的個(gè)數(shù)，可求得該頂點(diǎn)的出度。若從頂點(diǎn)結(jié)點(diǎn)的firstoutarc域出發(fā)，由弧結(jié)點(diǎn)中的headnextarc域鏈接起來(lái)的鏈表，正好是原來(lái)的逆鄰接表結(jié)構(gòu)。統(tǒng)計(jì)該鏈表中弧結(jié)點(diǎn)的個(gè)數(shù)，可求得該頂點(diǎn)的入度。圖的遍歷與連通性

對(duì)于給定的圖，沿著一些邊（或弧）訪(fǎng)問(wèn)圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次，這個(gè)過(guò)程叫做圖的遍歷。

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

圖的深度優(yōu)先遍歷基于深度優(yōu)先搜索DFS(DepthFirstSearch)，

深度優(yōu)先搜索是從圖中某一頂點(diǎn)v出發(fā)，在訪(fǎng)問(wèn)頂點(diǎn)v后，再依次從v的任一還沒(méi)有被訪(fǎng)問(wèn)的鄰接頂點(diǎn)w出發(fā)進(jìn)行深度優(yōu)先搜索，直到圖中所有與頂點(diǎn)v由路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。這是一個(gè)遞歸定義，所以圖的深度優(yōu)先搜索可以用遞歸算法實(shí)現(xiàn)。

下圖（a）給出了深度優(yōu)先搜索的示例。由于該圖是連通的，所以從頂點(diǎn)A出發(fā)，通過(guò)一次深度優(yōu)先搜索，就可以訪(fǎng)問(wèn)圖中的所有頂點(diǎn)。

圖的深度優(yōu)先遍歷的訪(fǎng)問(wèn)順序與樹(shù)的前序遍歷順序類(lèi)似。圖(b)給出了在深度優(yōu)先遍歷的過(guò)程中，訪(fǎng)問(wèn)的所有頂點(diǎn)和經(jīng)過(guò)的邊，圖中各頂點(diǎn)旁附加的數(shù)字表示各頂點(diǎn)被訪(fǎng)問(wèn)的次序。在圖(b)中，共有n-1條邊連結(jié)了所有n個(gè)頂點(diǎn)，在此把它稱(chēng)為圖（a）的深度優(yōu)先搜索生成樹(shù)。從指定的結(jié)點(diǎn)v開(kāi)始進(jìn)行深度優(yōu)先搜索的算法的步驟是：（1）訪(fǎng)問(wèn)結(jié)點(diǎn)v，并標(biāo)記v已被訪(fǎng)問(wèn)；（2）取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)w；（3）若頂點(diǎn)w不存在，算法結(jié)束；否則繼續(xù)步驟（4）（4）若頂點(diǎn)w未被訪(fǎng)問(wèn)，則訪(fǎng)問(wèn)結(jié)點(diǎn)w，并標(biāo)記w已被訪(fǎng)問(wèn)；（5）使w為頂點(diǎn)v的在原來(lái)w之后的下一個(gè)鄰接頂點(diǎn)，轉(zhuǎn)到步驟（3）。下面給出深度優(yōu)先搜索和深度優(yōu)先遍歷的算法：template<classvertexType,classarcType>voidGraph<vertexType,arcType>::DFTraverse(voidvisit(vertexTypev)){

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

int*visited=new

int[n];//定義訪(fǎng)問(wèn)標(biāo)記數(shù)組

visited

for(i=0;i<n;i++)visited[i]=0;//訪(fǎng)問(wèn)標(biāo)記數(shù)組visited初始化

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

if(!visited[i])DFS(v,visited,visit);

delete[]visited;//釋放

visited}template<classvertexType,class

arcType>void

Graph<vertexType,arcType>::DFS(const

intv,

intvisited[],voidvisit(vertexTypev)){

visit(GetValue(v));//訪(fǎng)問(wèn)頂點(diǎn)

vvisited[v]=1;//頂點(diǎn)v作訪(fǎng)問(wèn)標(biāo)記

intw=GetFirstNeighbor(v);

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

if(!visited[w])DFS(w,visited);

w=GetNextNeighbor(v,w);}//重復(fù)檢測(cè)v的所有鄰接頂點(diǎn)}廣度優(yōu)先遍歷

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

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

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

從指定的結(jié)點(diǎn)v開(kāi)始進(jìn)行廣度優(yōu)先搜索的算法步驟是：（1）訪(fǎng)問(wèn)結(jié)點(diǎn)v，并標(biāo)記v已被訪(fǎng)問(wèn)，同時(shí)頂點(diǎn)v入隊(duì)列；（2）當(dāng)隊(duì)列空時(shí)算法結(jié)束，否則繼續(xù)步驟（3）；（3）隊(duì)頭頂點(diǎn)出隊(duì)列為v；（4）取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)w；（5）若頂點(diǎn)w不存在，轉(zhuǎn)步驟（3）；否則繼續(xù)步驟（6）（6）若頂點(diǎn)w未被訪(fǎng)問(wèn)，則訪(fǎng)問(wèn)結(jié)點(diǎn)w，并標(biāo)記w已被訪(fǎng)問(wèn)，同時(shí)頂點(diǎn)w入隊(duì)列；否則繼續(xù)步驟（7）；（7）使w為頂點(diǎn)v的在原來(lái)w之后的下一個(gè)鄰接頂點(diǎn)，轉(zhuǎn)到步驟（5）。廣度優(yōu)先遍歷的算法：template<classvertexType,classarcType>voidGraph<vertexType,arcType>::BFTraverse(voidvisit(vertexTypev)){

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

int*visited=new

int[n];//定義訪(fǎng)問(wèn)標(biāo)記數(shù)組visited

for(i=0;i<n;i++)visited[i]=0;//訪(fǎng)問(wèn)標(biāo)記數(shù)組visited初始化

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

if(!visited[i])BFS(i,visited,visit);

delete[]visited;//釋放visited}template<classvertexType,classarcType>voidGraph<vertexType,arcType>::BFS(const

intv,

intvisited[],voidvisit(vertexTypev)){

linkqueue<int>q;//定義隊(duì)列qvisit(GetValue(v));//訪(fǎng)問(wèn)頂點(diǎn)vvisited[v]=1;//頂點(diǎn)v作已訪(fǎng)問(wèn)標(biāo)記

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

while(!q.IsEmpty()){

v=q.DeQueue();//否則,隊(duì)頭元素出隊(duì)列

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

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

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

q.EnQueue(w);//頂點(diǎn)w進(jìn)隊(duì)列q}w=GetNextNeighbor(v,w);}//重復(fù)檢測(cè)v的所有鄰接頂點(diǎn)

}//外層循環(huán)，判隊(duì)列空否}連通分量對(duì)于連通圖，從任一頂點(diǎn)出發(fā)，只需一次調(diào)用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法就可以訪(fǎng)問(wèn)到圖中的所有頂點(diǎn)；

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

最小生成樹(shù)

一個(gè)連通圖的生成樹(shù)是原圖的極小連通子圖，它包含原圖中的所有n個(gè)頂點(diǎn)和使n個(gè)頂點(diǎn)連通的n-1條邊。

這意味著對(duì)于生成樹(shù)來(lái)說(shuō)，若刪除它的一條邊，就會(huì)使生成樹(shù)變成非連通圖；若給它增加一條邊，就會(huì)形成圖中的一個(gè)回路。

另一方面，一個(gè)連通圖的生成樹(shù)不是唯一的，使用不同的方法遍歷圖，可以得到不同的生成樹(shù)；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)；而且生成樹(shù)有時(shí)還和圖的存儲(chǔ)結(jié)構(gòu)中具體的結(jié)點(diǎn)順序有關(guān)。

對(duì)于一個(gè)帶權(quán)的連通圖(即網(wǎng)絡(luò))，如何找出一棵生成樹(shù)，使得各邊上的權(quán)值總和達(dá)到最小，這是一個(gè)有實(shí)際意義的問(wèn)題。對(duì)于這樣一個(gè)有n個(gè)頂點(diǎn)的網(wǎng)絡(luò)，可以有不同的生成樹(shù)，每一棵生成樹(shù)都可以構(gòu)成通信網(wǎng)絡(luò)。我們希望能夠根據(jù)各條邊上的權(quán)值，選擇一棵總造價(jià)最小的生成樹(shù)，這就是構(gòu)造網(wǎng)絡(luò)的最小(代價(jià))生成樹(shù)(Minimum-costSpanningTree)問(wèn)題。

克魯斯卡爾算法

克魯斯卡爾(Kruskal)算法的基本思想是：

設(shè)一個(gè)有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)G＝{V，E}，最初先構(gòu)造一個(gè)包括全部n個(gè)頂點(diǎn)和0條邊的森林F＝{T0、T1、…、Tn-1}，

以后每一步向F中加入一條邊（v、u），該邊應(yīng)當(dāng)是所依附的兩個(gè)頂點(diǎn)v和u分別在森林F的兩棵不同的樹(shù)上的所有邊中具有最小權(quán)值的邊。由于這條邊的加入，使F中的某兩棵樹(shù)合并為一棵，樹(shù)的棵數(shù)減一。如此，經(jīng)過(guò)n—1步，最終得到一棵有n—1條邊且各邊權(quán)值總和達(dá)到最小的生成樹(shù)——最小生成樹(shù)。對(duì)于前圖(a)所示的連通網(wǎng)絡(luò)，下圖中(a)(f)給出了按克魯斯卡爾算法生成最小生成樹(shù)的過(guò)程。在克魯斯卡爾算法中，利用最小堆來(lái)存放連通網(wǎng)絡(luò)中的邊，堆中每個(gè)元素代表連通網(wǎng)絡(luò)中的一條邊，它有三個(gè)域組成：adjvex1、adjvex2和weight，其中adjvex1和adjvex2存儲(chǔ)該邊所依附的兩個(gè)頂點(diǎn)的序號(hào)，weight存儲(chǔ)邊上的權(quán)值；在利用并查集存放所有連通分量，同一個(gè)連通分量的頂點(diǎn)組成并查集的一個(gè)子集（等價(jià)類(lèi)）?？唆斔箍査惴ú襟E如下：（1）初始化，在并查集中，連通網(wǎng)絡(luò)的每一個(gè)頂點(diǎn)獨(dú)立成一個(gè)等價(jià)類(lèi)，連通網(wǎng)絡(luò)的所有的邊建立最小堆，最小生成樹(shù)T中沒(méi)有任何邊，T中邊的條數(shù)計(jì)數(shù)器i為0；（2）如果T中邊的條數(shù)計(jì)數(shù)器i等于頂點(diǎn)數(shù)減1，則算法結(jié)束；否則繼續(xù)步驟（3）；（3）選取堆頂元素代表的邊（v，u），同時(shí)調(diào)整堆；（4）利用并查集的運(yùn)算檢查依附于邊（v，u）的兩個(gè)頂點(diǎn)v和u是否在同一個(gè)連通分量(即并查集的同一個(gè)子集合)上，如果是則轉(zhuǎn)步驟（2）；否則繼續(xù)步驟（5）；（5）將邊（v，u）加入到最小生成樹(shù)T中，同時(shí)將這兩個(gè)頂點(diǎn)所在的連通分量合并成一個(gè)連通分量(即并查集中的相應(yīng)兩個(gè)子集合并成一個(gè)子集)，繼續(xù)步驟（2）。最小生成樹(shù)的類(lèi)聲明：const

intMAXNUM=機(jī)器可表示的最大整數(shù)const

intMaxNumArc=20//圖中最大的邊數(shù)classMinSpanTree;classMSTArcNode{//生成樹(shù)邊結(jié)點(diǎn)的類(lèi)定義friend

classMinSpanTree;private:

intadjvex1,adjvex2;//一條邊所依附的兩個(gè)頂點(diǎn)

floatweight;//邊的代價(jià)（權(quán)值）};class

MinSpanTree{//生成樹(shù)的類(lèi)定義public:MinSpanTree():CurrentNumArc(0){arctable=newMSTArcNode[MaxNumArc];}

intInsert(MSTArcNode&e);//將邊e加到最小生成樹(shù)中protected:MSTArcNode*arctable;//存放邊的數(shù)組

intCurrentNumArc;//當(dāng)前邊數(shù)};右圖給出了對(duì)于前圖（a）所示的連通網(wǎng)絡(luò)，按克魯斯卡爾算法構(gòu)造最小生成樹(shù)時(shí)最小堆和并查集的變化過(guò)程。在初始建堆時(shí)，邊的輸入順序?yàn)椋?A、B)，（A、C），（A、F），（B、E），（C、D），（C、F），（D、E），（D、F），（E，F(xiàn)）?？唆斔箍査惴ǖ腃++描述：voidGraph<string,float>::Kruskal(MinSpanTree&T){

intv,u,i=1;MSTArcNodee;//邊結(jié)點(diǎn)輔助單元

MinHeap<MSTArcNode>h(CurrentNumArcs);

intNum=NumberOfVertexes();//取圖的頂點(diǎn)個(gè)數(shù)

UFSetsf(Vertexes,Num);

for(u=0;u<Num;u++)//建立初始最小堆h

for(v=u+1;v<Num;v++)

if(Arcs[u][v]!=MAXNUM){//把圖中的所有邊

e.adjvex1=u;e.adjvex2=v;e.weight=Arcs[u][v];h.Insert(e);//把e插入堆}while(i<Num){//最小生成樹(shù)中的邊數(shù)不到頂點(diǎn)數(shù)減一

e=h.DeleteTop();//從堆中退出一條邊

u=f.Find(e.adjvex1);//取兩個(gè)頂點(diǎn)所在的等價(jià)類(lèi)的根

v=f.Find(e.adjvex2);

if(u!=v){//如果兩個(gè)頂點(diǎn)不在同一連通分量

f.Union(u,v);//合并

T.Insert(e);//該邊存入最小生成樹(shù)Ti++;//計(jì)數(shù)器自增}}}普里姆算法

普里姆(Prim)算法的基本思想是：假設(shè)連通網(wǎng)絡(luò)為N＝(V，E)；TE為N的最小生成樹(shù)上邊的集合，開(kāi)始時(shí)TE=；U為算法在構(gòu)造最小生成樹(shù)過(guò)程中已得到的頂點(diǎn)集，開(kāi)始時(shí)U={u0}（u0V）。

算法從N中的某一頂點(diǎn)u0出發(fā)，選擇與u0關(guān)聯(lián)的具有最小權(quán)值的邊(u0、vi)，將頂點(diǎn)vi加入到生成樹(shù)的頂點(diǎn)集合U中，(u0，vi)加入到集合TE中，以后每一步從一個(gè)頂點(diǎn)在U中，而另一個(gè)頂點(diǎn)在V-U中的各條邊當(dāng)中選擇權(quán)值最小的邊(u、v)（uU，vV-U），把頂點(diǎn)v加入到集合U中，邊(v、u)加入到集合TE中。如此重復(fù)，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹(shù)頂點(diǎn)集合U（U=V）中為止。此時(shí)，TE中剛好有n-1條邊，則T=（V，TE）為N的最小生成樹(shù)。對(duì)于前圖（a）所示的連通網(wǎng)絡(luò)，下圖(a)(f)給出了按普里姆算法從頂點(diǎn)A開(kāi)始構(gòu)造最小生成樹(shù)的過(guò)程。class

MinSpanTree{//生成樹(shù)的類(lèi)定義public:MinSpanTree():CurrentNumArc(0){arctable=newMSTArcNode[MaxNumArc];}

intInsert(MSTArcNode&e);//將邊e加到最小生成樹(shù)中protected:MSTArcNode*arctable;//存放邊的數(shù)組

intCurrentNumArc;//當(dāng)前邊數(shù)};在利用普里姆算法構(gòu)造最小生成樹(shù)過(guò)程中，需要設(shè)置了一個(gè)輔助數(shù)組closearc[]，以記錄從V-U中頂點(diǎn)到U中頂點(diǎn)具有最小權(quán)值的邊。

對(duì)每一個(gè)頂點(diǎn)vV-U，在輔助數(shù)組中有一個(gè)分量closearc[v]，它包括兩個(gè)域：lowweight和nearvertex。其中，lowweight中存放頂點(diǎn)v到U中的各頂點(diǎn)的邊上的當(dāng)前最小權(quán)值(lowweight=0表示vU)；nearvertex記錄頂點(diǎn)v到U中具有最小權(quán)值的那條邊的另一個(gè)鄰接頂點(diǎn)u（nearvertex=-1表示該頂點(diǎn)v為開(kāi)始頂點(diǎn)）。在下面的普里姆算法描述中，連通網(wǎng)絡(luò)采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，并假設(shè)普里姆算法從頂點(diǎn)A（設(shè)頂點(diǎn)A的序號(hào)為0）出發(fā)（即u0=0）。普里姆算法步驟如下：（1）初始化輔助數(shù)組closearc[]；（2）重復(fù)下列步驟（3）和（5）n-1次（3）在closearc[]中選擇lowweight0&&

lowweight最小的頂點(diǎn)v，即選中的權(quán)值最小的邊為(closearc[v].nearvertex,i)。（4）將closearc[v].lowweight改為0，表示頂點(diǎn)i已加入頂點(diǎn)集U中。并將邊(closearc[v].nearvertex、v)加入生成樹(shù)T的邊集合。（5）對(duì)V-U中的每一個(gè)頂點(diǎn)j，如果依附于頂點(diǎn)j和剛加入U(xiǎn)集合的新頂點(diǎn)v的邊的權(quán)值A(chǔ)rcs[v][j]小于原來(lái)依附于j和生成樹(shù)頂點(diǎn)集合中頂點(diǎn)的邊的最短距離closearc[j].lowweight，則修改closearc[j]，使其lowweight=Arcs[v][j]}，nearvertex=v。下圖給出了對(duì)于前圖（a）所示的連通網(wǎng)絡(luò)，按普里姆算法構(gòu)造最小生成樹(shù)時(shí)輔助數(shù)組closearc[]的變化過(guò)程。普里姆算法的C++描述：classMinSpanTree;classCloseArcType{//輔助數(shù)組closearc[]的元素類(lèi)定義friend

classMinSpanTree;private:

floatlowweight;//邊的代價(jià)（權(quán)值）

intnearvertex;//U中的頂點(diǎn)};voidGraph<string,float>::Prim(MinSpanTree&T){

intNum=NumberOfVertexes();//取連通網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù)

CloseArcType*closearc=newclosearctype[Num];

MSTArcNodee;//定義最小生成樹(shù)邊結(jié)點(diǎn)輔助變量

floatmin;

intv,i,j;

for(i=1;i<Num;i++){//初始化輔助數(shù)組closearc[]closearc[i].lowweight=Arcs[0][i];closearc[i].nearvertex=0;}closearc[0].lowweight=0;//頂點(diǎn)0加到生成樹(shù)頂點(diǎn)集合

closearc[0].nearvertex=-1;

for(i=1;i<Num;i++){//循環(huán)n-1次,加入n-1條邊

min=MAXNUM;v=0;

for(

intj=0;j<Num;j++)

if(closearc[j].lowweight!=0&&closearc[j].lowweight<min){v=j;min=closearc[j].lowweight;}//選取兩個(gè)鄰接頂點(diǎn)分別在U-V和U且具有最小權(quán)值的邊

if(v){//v==0表示再也找不到所求的邊

e.adjvex1=closearc[v].nearvertex;e.adjvex2=v;e.weight=closearc[v].lowweight;

T.Insert(e);//把選出的邊加入到生成樹(shù)中

closearc[v].lowweight=0;//把頂點(diǎn)v加入U(xiǎn)中

for(j=1;j<Num;j++)

if(closearc[j].lowweight!=0&&

Arcs[v][j]<closearc[j].lowweight){//對(duì)U-V中的每一個(gè)頂點(diǎn)考察是否要修改它在輔助數(shù)組中的值