數(shù)據(jù)結構課件：圖

圖8.1圖的基本概念8.2圖的設計和實現(xiàn)8.3圖的遍歷8.4最小生成樹8.5最短路徑8.6本章小結圖是又一種非線性數(shù)據(jù)結構。

在圖結構中，

數(shù)據(jù)元素之間的關系是多對多的，

即圖中每一個數(shù)據(jù)元素可以和圖中任意別的數(shù)據(jù)元素相關。

圖用于表示數(shù)據(jù)元素之間存在的網(wǎng)狀結構關系。

本章首先介紹有關圖的一些基本概念和圖的基本操作，

然后討論圖的存儲結構以及圖基本操作的算法實現(xiàn)，

最后討論了圖的最小生成樹和最短路徑問題。

圖的最小生成樹和圖的最短路徑是圖的兩種最主要的應用。

8.1.1圖的基本概念

圖是由頂點集合及頂點間的關系集合組成的一種數(shù)據(jù)結構。

圖G的定義是：

G＝(V，

E)

式中

V＝

{x|x∈某個數(shù)據(jù)元素集合}

E＝{(x，

y)|x，

y∈V}

或E＝

{＜x，-y＞|x，

y∈V并且Path(x，-y)}

其中，

Path(x，

y)表示從

x到y(tǒng)的一條單向通路，即Path(x，y)是有方向的。8.1圖的基本概念圖有許多復雜結構，本課程只討論最基本的圖，因此，本章討論的圖中不包括圖8-1所示兩種形式的圖。圖8-1(a)中有從自身到自身的邊存在，稱為帶自身環(huán)的圖，圖8-1(b)中從頂點B到頂點D有兩條無向邊，稱為多重圖。

我們首先給出圖的基本術語。為方便術語解釋，圖8-２給出了4個典型圖例。

圖8-1帶自身環(huán)的圖和多重圖

(a)帶自身環(huán)的圖；(b)多重圖

圖8-2四個圖例

(a)G1；(b)G2；(c)G3；(d)G4

(1)頂點和邊：圖中的結點稱作頂點，圖中的第i個頂點記做vi。兩個頂點vi和vj相關聯(lián)稱作頂點vi和vj之間有一條邊，圖中的第k條邊記做ek，ek

＝(vi，vj)或＜vi，vj＞。

(2)有向圖和無向圖：在有向圖中，頂點對＜x，y＞是有序的，頂點對＜x，y＞稱為從頂點x到頂點y的一條有向邊，因此，＜x，y＞與＜y，x＞是兩條不同的邊。有向圖中的頂點對＜x，y＞用一對尖括號括起來，x是有向邊的始點，y是有向邊的終點，有向圖中的邊也稱作?。辉跓o向圖中，頂點對(x，y)是無序的，頂點對(x，y)稱為與頂點x和頂點y相關聯(lián)的一條邊，這條邊沒有特定的方向，因此，(x，y)與(y，x)是同一條邊。

圖8-２給出的4個圖例中，圖G1和G2是無向圖。G1的頂點集合為V(G1)＝{0，1，2，3}，邊集合為E(G1)＝{(0，1)，(0，2)，(0，3)，(1，2)，(1，3)，(2，3)}；圖G3和G4是有向圖，G3的頂點集合為V(G3)＝{0，1，2}，邊集合為E(G3)＝{＜0，1＞，＜l，0＞，＜1，2＞}。對于有向邊，邊的方向用箭頭畫出，箭頭從有向邊的始點指向有向邊的終點。

(3)完全圖：在有n個頂點的無向圖中，若有n(n-1)/2條邊，即任意兩個頂點之間有且只有一條邊，則稱此圖為無向完全圖。圖8-２(a)所示的G1就是無向完全圖；在有n個頂點的有向圖中，若有n(n-1)條邊，即任意兩個頂點之間有且只有方向相反的兩條邊，則稱此圖為有向完全圖。圖8-２(d)所示的G4就是有向完全圖。

(4)鄰接頂點：在無向圖G中，若(u，v)是E(G)中的一條邊，則稱u和v互為鄰接頂點，并稱邊(u，v)依附于頂點u和v。在圖8-２(a)所示的無向圖G1中，頂點0的鄰接頂點有頂點1，2和3；在有向圖G中，若＜u，v＞是E(G)中的一條邊，則稱頂點u鄰接到頂點v，頂點v鄰接自頂點u，并稱邊＜u，v＞與頂點u和頂點v相關聯(lián)。在圖8-２(c)所示的有向圖G3中，頂點1因邊＜1，2＞鄰接到頂點2。

(5)頂點的度：頂點v的度是與它相關聯(lián)的邊的條數(shù)，記作TD(v)。對于有向圖，頂點的度等于該頂點的入度和出度之和，即TD(v)＝ID(v)＋OD(v)。其中，頂點v的入度ID(v)是以v為終點的有向邊的條數(shù)；頂點v的出度OD(v)是以v為始點的有向邊的條數(shù)。在圖8-２(c)所示的有向圖G3中，頂點1的入度ID(1)＝1，頂點1的出度OD(1)＝2，所以，頂點1的度TD(v)＝ID(v)＋OD(v)＝1＋2＝3。對于無向圖，頂點的度等于該頂點的入度或出度，即TD(v)＝ID(v)＝OD(v)。

(6)路徑：在圖G＝(V，E)中，若從頂點vi出發(fā)有一組邊可到達頂點vj，則稱頂點vi到頂點vj的頂點序列為從頂點vi到頂點vj的路徑。在圖8-2(b)所示的圖G2中，從頂點0到頂點3的路徑為0，1，3。

(7)權：有些圖的邊附帶有數(shù)據(jù)信息，這些附帶的數(shù)據(jù)信息稱為權。第i條邊的權用符號wi表示。權可以表示實際問題中從一個頂點到另一個頂點的距離、花費的代價、所需的時間等等。帶權的圖也稱作網(wǎng)絡或網(wǎng)。圖8-3就是帶權圖，其中，圖8-3(a)是一個工程的施工進度圖，圖8-3(b)是一個交通網(wǎng)絡圖。

圖8-3帶權圖

(a)施工進度圖；(b)交通網(wǎng)絡圖

(8)路徑長度：對于不帶權的圖，一條路徑的路徑長度是指該路徑上的邊的條數(shù)；對于帶權的圖，一條路徑的路徑長度是指該路徑上各個邊權值的總和。在圖8-２(b)所示的無向圖G2中，路徑0，1，3的路徑長度為2；在圖8-3(a)所示的帶權圖中，路徑1，3，6，7的路徑長度為16。

(9)子圖：設有圖G1＝{V1，E1}和圖G2＝{V2，E2}，若V2

V1且E2

E1，則稱圖G2是圖G1的子圖。

(10)連通圖和連通分量：在無向圖中，若從頂點vi到頂點vj有路徑，則稱頂點vi和頂點vj是連通的。如果圖中任意一對頂點都是連通的，則稱該圖是連通圖。非連通圖的最大連通子圖稱作連通分量。圖8-2中的無向圖G1和G2都是連通圖。

(11)生成樹：一個連通圖的最小連通子圖稱作該圖的生成樹。有n個頂點的連通圖的生成樹有n個頂點和n-1條邊。

(12)簡單路徑和回路：若路徑上各頂點v1，v2，…，vm互不重復，則稱這樣的路徑為簡單路徑；若路徑上第一個頂點v1與最后一個頂點vm重合，則稱這樣的路徑為回路或環(huán)。8.1.2圖的抽象數(shù)據(jù)類型

1.數(shù)據(jù)集合

圖的數(shù)據(jù)集合由一組頂點集合{vi}和一組邊{ej}集合組成。當為帶權圖時每條邊上權wj構成權集合{wj}。

2.操作集合

(1)初始化Initiate(G，n)：初始化圖G，n為頂點個數(shù)。

(2)插入頂點InsertVertex(G，vertex)：在圖G中插入頂點vertex。

(3)插入邊InsertEdgeG，-v1，v2，weight)：在圖G中插入邊<v1，v2>，邊<v1，v2>的權值為weight。

(4)刪除邊DeleteEdge(G，v1，v2)：在圖G中刪除邊<v1，v2>。

(5)第一個鄰接頂點GetFirstVex(G，v)：在圖G中尋找頂點v的第一個鄰接頂點。

注：圖中每個頂點的若干個鄰接頂點之間是沒有先后次序的，但對于一個具體的圖，一旦該圖建立完畢，則圖中每一個頂點的所有鄰接頂點之間就有次序之分。

(6)下一個鄰接頂點GetNextVex(G，intv1，v2)：在圖G中尋找頂點v1的鄰接頂點v2的下一個鄰接頂點。

(7)深度優(yōu)先遍歷DepthFirstSearch(G)：深度優(yōu)先遍歷圖G。

(8)廣度優(yōu)先遍歷BroadFirstSearch(G)：廣度優(yōu)先遍歷圖G。

和樹的遍歷類同，圖的遍歷也是訪問圖中的每一個頂點且每個頂點只被訪問一次。

從圖的定義可知，圖的信息包括兩部分，圖中頂點的信息和描述頂點之間關系的邊的信息。頂點信息的描述問題是一個簡單的表存儲結構問題，可采用第2章討論的順序表或鏈表存儲。8.2圖的設計和實現(xiàn)

對于一個有n個頂點的圖，由于每個頂點都可能和其他n-1個頂點成為鄰接頂點，所以邊之間的關系的描述問題實際上是一個n×n矩陣的計算機存儲表示問題。

圖的存儲結構主要是圖中邊的存儲結構。圖的存儲結構主要有鄰接矩陣和鄰接表兩種。一旦確定了圖的存儲結構，即可具體設計和實現(xiàn)圖的抽象數(shù)據(jù)類型。8.2.1圖的鄰接矩陣存儲結構

我們首先定義鄰接矩陣。假設圖G＝(V，E)有n個頂點，即V＝{v0，v1，…，vn-1}，E可用如下形式的矩陣A描述，對于A中的每一個元素aij，滿足：

由于矩陣A中的元素aij表示了頂點vi和頂點vj之間邊的關系，或者說，A中的元素aij表示了頂點vi和頂點vj(0≤j≤n-1)的鄰接關系，所以矩陣A稱作鄰接矩陣。在圖的鄰接矩陣存儲結構中，頂點信息使用一維數(shù)組存儲，邊信息的鄰接矩陣使用二維數(shù)組存儲。圖8-4(a)是一個無向圖，圖8-4(b)是該圖的鄰接矩陣存儲結構，其中，V表示了圖的頂點集合，A表示了圖的鄰接矩陣。無向圖的鄰接矩陣一定是對稱矩陣。

圖8-4無向圖及其鄰接矩陣

(a)無向圖；(b)鄰接矩陣圖8-5(a)是一個有向圖，圖8-5(b)是對應的鄰接矩陣存儲結構，其中，V表示了圖的頂點集合，A表示了圖的鄰接矩陣。有向圖的鄰接矩陣一般是非對稱矩陣。

圖8-5有向圖及其鄰接矩陣

(a)有向圖；(b)鄰接矩陣對于帶權圖，鄰接矩陣A定義為：

其中，wij>0。(有一種特殊的帶權圖允許wij為負值，這里不做討論。)根據(jù)不同的應用問題，鄰接矩陣A也可定義為：

鄰接矩陣A還可定義為(本書帶權圖的鄰接矩陣使用此定義)：

圖8-6(a)是一個帶權圖，圖8-6(b)是對應的鄰接矩陣存儲結構，其中，V表示了圖的頂點集合，A表示了圖的鄰接矩陣。對于帶權圖，鄰接矩陣第i行中所有0<aij<∞的元素個數(shù)等于第i個頂點的出度，鄰接矩陣第j列中所有0<aij<∞的元素個數(shù)等于第j個頂點的入度。

圖8-6帶權圖及其鄰接矩陣

(a)帶權圖；(b)鄰接矩陣8.2.2圖的鄰接表存儲結構

圖的鄰接矩陣存儲結構的主要特點是把圖的邊信息存儲在一個n×n矩陣中，其中n為圖中的頂點個數(shù)。當這個n×n矩陣是稠密矩陣時，圖的鄰接矩陣存儲結構是最常用也是最高效的存儲結構。但當圖的邊數(shù)少于頂點個數(shù)且頂點個數(shù)值較大時，n×n矩陣的存儲問題就變成了稀疏矩陣的存儲問題，此種情況時鄰接表就是一種較鄰接矩陣更為有效的存儲結構。

圖8-7(a)是一個有向圖，圖8-7(b)是該有向圖的鄰接表存儲結構。

圖8-7有向圖及其鄰接表

(a)有向圖；(b)鄰接表圖8-7(b)中行數(shù)組的data域存儲圖的頂點信息，adj域為該頂點的鄰接頂點單鏈表的頭指針。第i行單鏈表中的dest域存儲所有起始頂點為vi的鄰接頂點vj，因第i行單鏈表表示的邊<vi，vj>的所有起始頂點均為vi，所以不需要再另外存儲。next域為下一個結點的指針域。如果是帶權圖，單鏈表中需再增加cost域，第i行單鏈表中的dest域值為j的cost域中存儲邊<vi，vj>的權值wij。

對比圖8-7(b)和第5章的圖5-6行指針數(shù)組結構的三元組鏈表，可以發(fā)現(xiàn)，兩者講述的是同一種存儲結構。

當圖中頂點數(shù)目較小且邊較多時，采用圖的鄰接矩陣存儲結構效率較高；當圖中頂點數(shù)目較大且邊的數(shù)目遠小于相同頂點的完全圖的邊數(shù)時，采用圖的鄰接表存儲結構效率較高。

另外，圖的存儲結構還有十字鏈表存儲結構等。圖的十字鏈表存儲結構原理和第5章的圖5-7所示的三元組十字鏈表存儲結構的原理完全相同，此處不再贅述。8.2.3鄰接矩陣存儲結構下圖的操作實現(xiàn)

鄰接矩陣存儲結構下圖的頂點信息存儲在一個順序表中，圖的邊信息存儲在一個二維數(shù)組中。鄰接矩陣的存儲結構以及圖的各種操作實現(xiàn)算法設計如下：

＃include"SeqList.h"--------/*包含順序表頭文件*/

typedefstruct

{

----SeqListVertices;----------/*存放頂點的順序表*/

----intedge［MaxVertices］［MaxVertices］;/*存放邊的鄰接矩陣*/

----intnumOfEdges;-----------/*邊的條數(shù)*/

}AdjMWGraph;------------------/*圖的結構體定義*/

voidInitiate(AdjMWGraph*G，intn)-------/*初始化*/

{

----inti，j;

----for(i＝0;i<n;i＋＋)

--------for(j＝0;j<n;j＋＋)

--------{

------------if(i＝＝j)G->edge［i］［j］＝0;

------------elseG->edge［i］［j］＝MaxWeight;

--------}

----G->numOfEdges＝0;--------/*邊的條數(shù)置為0*/

----ListInitiate(&G->Vertices);---/*順序表初始化*/

}

voidInsertVertex(AdjMWGraph*G，DataTypevertex)

/*在圖G中插入頂點vertex*/

{

----ListInsert(&G->Vertices，G->Vertices.size，vertex);-/*順序表尾插入*/

}

voidInsertEdge(AdjMWGraph*G，intv1，intv2，intweight)

/*在圖G中插入邊<v1，v2>，邊<v1，v2>的權為weight*/

{

--if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size)

----{

--------printf("參數(shù)v1或v2越界出錯!＼n");

--------exit(1);

----}

----G->edge［v1］［v2］＝weight;

----G->numOfEdges＋＋;

}

voidDeleteEdge(AdjMWGraph*G，intv1，intv2)

/*在圖G中刪除邊<v1，v2>*/

{

----if(v1<0||v1>G->Vertices.size||v2<0

---||v2>G->Vertices.size||v1＝＝v2)

----{

--------printf("參數(shù)v1或v2越界出錯!＼n");

--------exit(1);

----}

----G->edge［v1］［v2］＝MaxWeight;

----G->numOfEdges--;

}

intGetFirstVex(AdjMWGraphG，intv)

/*在圖G中尋找序號為v的頂點的第一個鄰接頂點*/

/*如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1*/

{

----intcol;

----if(v<0||v>G.Vertices.size)

----{

--------printf("參數(shù)v1越界出錯!＼n");

--------exit(1);

----}

----for(col＝0;col<＝G.Vertices.size;col＋＋)

--if(G.edge［v］［col］>0&&G.edge［v］［col］<MaxWeight)returncol;

----return-1;

}

intGetNextVex(AdjMWGraphG，intv1，intv2)

/*在圖G中尋找v1頂點的鄰接頂點v2的下一個鄰接頂點*/

/*如果這樣的鄰接頂點存在則返回該鄰接頂點的序號，否則返回-1*/

/*這里v1和v2都是相應頂點的序號*/

{

----intcol;

----if(v1<0||v1>G.Vertices.size||v2<0||v2>G.Vertices.size)

----{

--------printf("參數(shù)v1或v2越界出錯!＼n");

--------exit(1);

----}

----for(col＝v2＋1;col<＝G.Vertices.size;col＋＋)

--if(G.edge［v1］［col］>0&&G.edge［v1］［col］<MaxWeight)returncol;

----return-1;

}以圖8-8所示的有向帶權圖為例編寫測試上述圖操作函數(shù)的程序。

圖8-8有向帶權圖設計設上述圖操作的函數(shù)存放在文件AdjMGraph.h中。為方便以后設計測試程序時調(diào)用方便，我們把創(chuàng)建圖的過程單獨設計為一個函數(shù)。圖的創(chuàng)建函數(shù)設計如下：

typedefstruct

{

----introw;--------/*行下標*/

----intcol;---------------/*列下標*/

----intweight;-------------/*權值*/

}RowColWeight;----------------/*邊信息結構體定義*/

voidCreatGraph(AdjMWGraph*G，DataTypeV［］，intn，RowColWeightE［］，inte)

/*在圖G中插入n個頂點信息V和e條邊信息E*/

{

----inti，k;

----Initiate(G，n);---------/*頂點順序表初始化*/

----for(i＝0;i<n;i＋＋)

--------InsertVertex(G，V［i］);--/*頂點插入*/

----for(k＝0;k<e;k＋＋)

---InsertEdge(G，E［k］.row，E［k］.col，E［k］.weight);-/*邊插入*/

}測試程序設計如下：-＃include<stdio.h>

＃include<stdlib.h>

typedefcharDataType;---

＃defineMaxSize100

＃defineMaxVertices10

＃defineMaxEdges100

＃defineMaxWeight10000

＃include"AdjMGraph.h"

＃include"AdjMGraphCreate.h"

voidmain(void)

{

----AdjMWGraphg1;

----DataTypea［］＝{′A′，′B′，′C′，′D′，′E′};

--RowColWeightrcw［］＝{{0，1，10}，{0，4，20}，{1，3，30}，{2，1，40}，{3，2，50}};

----intn＝5，e＝5;

----inti，j;

----CreatGraph(&g1，a，n，rcw，e);

----printf("頂點集合為：-");

---for(i＝0;i<g1.Vertices.size;i＋＋)

--------printf("%c-"，g1.Vertices.list［i］);

----printf("＼n");

----printf("權值集合為：＼n");

----for(i＝0;i<g1.Vertices.size;i＋＋)

----{

--------for(j＝0;j<g1.Vertices.size;j＋＋)

------------printf("%5d"，g1.edge［i］［j］);

--------printf("＼n");

----}

}程序運行輸出結果如下：

頂點集合為：-A-B-C-D-E

權值集合為：

--0--10-10000-10000-20

-10000--0-10000-30-10000

-10000--40--0-10000-10000

-10000-10000-50--0-10000

-10000-10000-10000-10000--0

8.3.1圖的深度和廣度優(yōu)先遍歷算法

和樹的遍歷操作類同，圖的遍歷操作的定義是訪問圖中的每一個頂點且每個頂點只被訪問一次。圖的遍歷方法主要有兩種：一種是深度優(yōu)先搜索遍歷，另一種是廣度優(yōu)先搜索遍歷。8.3圖的遍歷

圖的深度優(yōu)先搜索遍歷類同于樹的先根遍歷，圖的廣度優(yōu)先搜索遍歷類同于樹的層序遍歷。

圖的遍歷算法設計需要考慮三個問題：

(1)圖的特點是沒有首尾之分，所以算法的參數(shù)要指定訪問的第一個頂點。

(2)對圖的遍歷路徑有可能構成一個回路，從而造成死循環(huán)，所以算法設計要考慮遍歷路徑可能出現(xiàn)的死循環(huán)問題。

(3)一個頂點可能和若干個頂點都是鄰接頂點，要使一個頂點的所有鄰接頂點按照某種次序被訪問。對于連通圖，從初始頂點出發(fā)一定存在路徑和圖中的所有其他頂點相連，所以對于連通圖從初始頂點出發(fā)一定可以遍歷該圖。圖的深度優(yōu)先遍歷算法是遍歷時深度優(yōu)先的算法，即在圖的所有鄰接頂點中每次都在訪問完當前頂點后首先訪問當前頂點的第一個鄰接頂點，這樣的算法是一個遞歸算法。連通圖的深度優(yōu)先搜索遍歷遞歸算法為：

(1)訪問頂點v并標記頂點v為已訪問；

(2)查找頂點v的第一個鄰接頂點w；

(3)若頂點v的鄰接頂點w存在，則繼續(xù)執(zhí)行，否則算法結束；

(4)若頂點w尚未被訪問，則深度優(yōu)先搜索遞歸訪問頂點w；

(5)查找頂點v的w鄰接頂點的下一個鄰接頂點w，轉到步驟(3)。

上述遞歸算法屬于回溯算法，當尋找頂點v的鄰接頂點w成功時繼續(xù)進行，當尋找頂點v的鄰接頂點w失敗時回溯到上一次遞歸調(diào)用的地方繼續(xù)進行。

對于圖8-8所示的有向連通圖，若頂點A為初始訪問的頂點，則深度優(yōu)先搜索遍歷的頂點訪問順序是：

-ABDCE圖的廣度優(yōu)先遍歷算法是一個分層搜索的過程，和樹的層序遍歷算法類同，圖的廣度優(yōu)先搜索遍歷算法也需要一個隊列以保持訪問過的頂點的順序，以便按順序訪問這些頂點的鄰接頂點。連通圖的廣度優(yōu)先搜索遍歷算法為：

(1)訪問初始頂點v并標記頂點v為已訪問；

(2)頂點v入隊列；

(3)當隊列非空時則繼續(xù)執(zhí)行，否則算法結束；

(4)出隊列取得隊頭頂點u；

(5)查找頂點u的第一個鄰接頂點w；

(6)若頂點u的鄰接頂點w不存在，則轉到步驟(3)，否則執(zhí)行后序語句：

①若頂點w尚未被訪問，則訪問頂點w并標記頂點w為已訪問；

②頂點w入隊列；

③查找頂點u的w鄰接頂點后的下一個鄰接頂點w，轉到步驟(6)。

對于圖8-8所示的有向連通圖，若頂點A為初始訪問的頂點，則廣度優(yōu)先搜索遍歷的頂點訪問順序是：

-ABEDC對于連通圖，從圖的任意一個頂點開始深度或廣度優(yōu)先遍歷一定可以訪問圖中的所有頂點，但對于非連通圖，從圖的任意一個頂點開始深度或廣度優(yōu)先遍歷并不能訪問圖中的所有頂點。對于非連通圖，從圖的任意一個頂點開始深度或廣度優(yōu)先遍歷只能訪問和初始頂點連通的所有頂點。

對于非連通圖，當我們把每一個頂點都作為一次初始頂點進行深度或廣度優(yōu)先遍歷搜索，并根據(jù)頂點的訪問標記來判斷是否需要訪問該頂點，就一定可以訪問非連通圖中的所有頂點。8.3.2圖的深度和廣度優(yōu)先遍歷算法設計和實現(xiàn)

設圖采用鄰接矩陣存儲結構，鄰接矩陣存儲結構下圖的操作實現(xiàn)函數(shù)(如第一個鄰接頂點函數(shù)GetFirstVex(G，v)和下一個鄰接頂點函數(shù)GetNextVex(G，v，w))已經(jīng)提供。為方便后邊測試程序的設計且不失一般性，我們這里假設圖的頂點信息為字母類型，并假設對頂點信息的訪問為輸出該頂點字母，實際應用中對頂點的訪問可以是任意一個函數(shù)。

圖的深度優(yōu)先遍歷函數(shù)實現(xiàn)如下：

-DepthFSearch(AdjMWGraphG，intv，intvisited［］)

/*連通圖G以v為初始頂點序號的深度優(yōu)先遍歷*/

/*數(shù)組visited標記了相應頂點是否已訪問過，0表示未訪問，1表示已訪問*/

{

----intw;

----printf("%c-"，G.Vertices.list［v］);--/*輸出頂點字母*/

----visited［v］＝1;

----w＝GetFirstVex(G，v);

----while(w!＝-1)

----{

--------if(!visited［w］)DepthFSearch(G，w，visited);

--------w＝GetNextVex(G，v，w);

----}

}

voidDepthFirstSearch(AdjMWGraphG)

/*非連通圖G的深度優(yōu)先遍歷*/

{

----inti;

----int*visited＝(int*)malloc(sizeof(int)*G.Vertices.size);

----for(i＝0;i<G.Vertices.size;i＋＋)

--------visited［i］＝0;

----for(i＝0;i<G.Vertices.size;i＋＋)

--------if(!visited［i］)DepthFSearch(G，i，visited);

----free(visited);

}圖的廣度優(yōu)先遍歷函數(shù)實現(xiàn)如下：-＃include"SeqCQueue.h"-----/*包括順序循環(huán)隊列*/

voidBroadFSearch(AdjMWGraphG，intv，intvisited［］)

/*連通圖G以v為初始頂點序號的廣度優(yōu)先遍歷*/

/*數(shù)組visited標記了相應頂點是否已訪問過，0表示未訪問，1表示已訪問*/

{

----DataTypeu，w;

----SeqCQueuequeue;

----printf("%c-"，G.Vertices.list［v］);-/*輸出頂點字母*/

----visited［v］＝1;

----QueueInitiate(&queue);

----QueueAppend(&queue，v);

----while(QueueNotEmpty(queue))

----{

--------QueueDelete(&queue，&u);

--------w＝GetFirstVex(G，u);

--------while(w!＝-1)

--------{

------------if(!visited［w］)

------------{

------printf("%c-"，G.Vertices.list［w］);-/*輸出頂點字母*/

------visited［w］＝1;

----------------QueueAppend(&queue，w);

------------}

------------w＝GetNextVex(G，u，w);

--------}

----}

}

voidBroadFirstSearch(AdjMWGraphG)

/*非連通圖G的廣度優(yōu)先遍歷*/

{

----inti;

----int*visited＝(int*)malloc(sizeof(int)*G.Vertices.size);

----for(i＝0;i<G.Vertices.size;i＋＋)

--------visited［i］＝0;

----for(i＝0;i<G.Vertices.size;i＋＋)

--------if(!visited［i］)BroadFSearch(G，i，visited);

----free(visited);

}以圖8-8所示的帶權有向圖為例編寫測試上述圖的深度優(yōu)先和廣度優(yōu)先遍歷函數(shù)的程序。

設計設圖的基本操作函數(shù)存放在文件AdjMGraph.h中，上述圖的深度優(yōu)先和廣度優(yōu)先遍歷函數(shù)存放在文件AdjMGraphTraverse.h中，因順序循環(huán)隊列中保存的是頂點序號，所以定義int為DataType。測試程序設計如下：-＃include<stdio.h>

＃include<stdlib.h>

＃include<malloc.h>

typedefintDataType;----/*順序循環(huán)隊列中保存頂點序號*/

＃defineMaxSize100

＃defineMaxVertices10

＃defineMaxEdges100

＃defineMaxWeight10000

＃defineMaxQueueSize100

＃include"AdjMGraph.h"＃include"AdjMGraphCreate.h"

＃include"AdjMGraphTraverse.h"

voidmain(void)

{

----AdjMWGraphg1;

----DataTypea［］＝{′A′，′B′，′C′，′D′，′E′};

---RowColWeightrcw［］＝{{0，1，10}，{0，4，20}，{1，3，30}，{2，1，40}，{3，2，50}};

----intn＝5，e＝5;

----CreatGraph(&g1，a，n，rcw，e);

----printf("深度優(yōu)先搜索序列為：");

----DepthFirstSearch(g1);

----printf("＼n廣度優(yōu)先搜索序列為：");

----BroadFirstSearch(g1);

}程序運行輸出結果如下：

-深度優(yōu)先搜索序列為：A-B-D-C-E

-廣度優(yōu)先搜索序列為：A-B-E-D-C

8.4.1最小生成樹的基本概念

一個有n個頂點的連通圖的生成樹是原圖的極小連通子圖，它包含原圖中的所有n個頂點，并且有保持圖連通的最少的邊。8.4最小生成樹由生成樹的定義可知：

(1)若在生成樹中刪除一條邊就會使該生成樹因變成非連通圖而不再滿足生成樹的定義；

(2)若在生成樹中增加一條邊就會使該生成樹中因存在回路而不再滿足生成樹的定義；

(3)一個連通圖的生成樹可能有許多。使用不同的尋找方法可以得到不同的生成樹。另外，從不同的初始頂點出發(fā)也可以得到不同的生成樹。

圖8-9給出了一個無向圖和它的兩棵不同的生成樹。

圖8-9無向圖和它的不同的生成樹

(a)無向圖；(b)生成樹1；(c)生成樹2從生成樹的定義顯然可以證明，對于有n個頂點的無向連通圖，無論它的生成樹的形狀如何，一定有且只有n-1條邊。

如果無向連通圖是一個帶權圖，那么它的所有生成樹中必有一棵邊的權值總和最小的生成樹，我們稱這棵生成樹為最小代價生成樹，簡稱最小生成樹。

許多應用問題都是一個求無向連通圖的最小生成樹問題。例如要在n個城市之間鋪設光纜，鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同。

一個目標是要使這n個城市的任意兩個之間都可以直接或間接通信，另一個目標是要使鋪設光纜的總費用最低。解決這個問題的方法就是在由n個城市頂點、(n-1)!條不同費用的邊構成的無向連通圖中找出最小生成樹，該最小生成樹的方案就可以達到既滿足使這n個城市的任意兩個之間都可以直接或間接通信的目標，又可以滿足使鋪設光纜的總費用最低的目標。從最小生成樹的定義可知，構造有n個頂點的無向連通帶權圖的最小生成樹必須滿足以下三條：

(1)構造的最小生成樹必須包括n個頂點；

(2)構造的最小生成樹中有且只有n-1條邊；

(3)構造的最小生成樹中不存在回路。

構造的最小生成樹的方法有許多種，典型的構造方法有兩種，一種稱作普里姆(Prim)算法，另一種稱作克魯斯卡爾(Kruskal)算法。8.4.2普里姆算法

假設G＝(V，E)為一個帶權圖，其中V為網(wǎng)中頂點的集合，E為帶權圖中帶權邊的集合。設置兩個新的集合U和T，其中U用于存放帶權圖G的最小生成樹的頂點的集合，T用于存放帶權圖G的最小生成樹的帶權邊的集合。普里姆算法的思想是：令集合U的初值為U＝{u0}(即假設構造最小生成樹時均從頂點u0開始)，集合T的初值為T＝{}。從所有頂點u∈U和頂點v∈V-U的帶權邊中選出具有最小權值的邊(u，v)，將頂點v加入集合U中，將邊(u，v)加入集合T中。如此不斷重復直到U＝V時即構造完畢。此時集合U中存放著最小生成樹的頂點的集合，集合T中存放著最小生成樹的帶權邊的集合。

圖8-10給出了用普里姆算法構造最小生成樹的過程。圖8-10(a)為一個有7個頂點10條無向邊的帶權圖；初始時算法的集合U＝{A}，集合V-U＝{B，C，D，E，F(xiàn)，G}，T＝{}，如圖8-10(b)所示；在所有u為集合U中頂點，v為集合V-U中頂點的邊(u，v)中尋找具有最小權值的邊(u，v)，尋找到的是邊(A，B)，權為50，把頂點B從集合V-U加入到集合U中，

把邊(A，B)加入到T中，如圖8-10(c)所示；在所有u為集合U中頂點，v為集合V-U中頂點的邊(u，v)中尋找具有最小權值的邊(u，v)，尋找到的是邊(B，E)，權為40，把頂點E從集合V-U加入到集合U中，把邊(B，E)加入到T中，如圖8-10(d)所示；隨后依次從集合V-U加入到集合U中的頂點為D，F(xiàn)，G，C，依次加入到T中的邊為(E，D)(權為50)、(D，F(xiàn))(權為30)、(D，G)(權為42)、(G，C)(權為45)，分別如圖8-10(e)、(f)、(g)、(h)所示。最后得到的圖8-10(h)就是原帶權連通圖的最小生成樹。

圖8-10普里姆算法構造最小生成樹的過程*8.4.3普里姆函數(shù)設計和實現(xiàn)

這里我們規(guī)定，當弧頭頂點等于弧尾頂點時權值等于0(即鄰接矩陣中對角線元素值均為0)。

函數(shù)中定義了一個臨時數(shù)組lowCost，數(shù)組元素lowCost［v］中保存了集合U中頂點u與集合V-U中頂點v的所有邊中當前具有最小權值的邊(u，v)。

集合U的初值為U＝{u0}可以設計為從序號為0的頂點開始。令lowCost的初始值為鄰接矩陣中第0行的值，這樣lowCost就表示了從集合U中第一個頂點到達集合V-U中各個頂點的代價。

然后我們從lowCost中尋找具有最小權值的邊，這樣的邊也就意味著其弧頭頂點為集合U中的頂點，其弧尾頂點為集合V-U中的頂點。每選到一條這樣的邊(u，v)，就輸出顯示所選到的最小生成樹的頂點信息和邊的權值信息，并將lowCost［v］置為0，表示序號為v的頂點已從集合V-U中加入到集合U中。當頂點v從集合V-U加入到了集合U，若當前l(fā)owCost中從集合U中頂點到達集合V-U中頂點存在更小代價的邊時，則用這樣的邊的權值修改lowCost中的權值。普里姆算法要處理的帶權圖G可以采用前面討論過的鄰接矩陣或鄰接表存儲結構存儲頂點信息和邊信息，下面設計的普里姆函數(shù)采用鄰接矩陣存儲結構。普里姆函數(shù)如下：

voidPrim(AdjMWGraphG)

/*用普里姆得到帶權圖G的最小生成樹，并把結果輸出顯示*/

{

----intn＝G.Vertices.size，minCost;

----int*lowCost＝(int*)malloc(sizeof(int)*n);

----inti，j，k;

----/*從序號為0的頂點出發(fā)得到最小生成樹*/

----printf("頂點值＝%c＼n"，G.Vertices.list［0］);

----for(i＝1;i<n;i＋＋)---------------

--------lowCost［i］＝G.edge［0］［i］;

----for(i＝1;i<n;i＋＋)

----{

--------/*尋找當前最小權值的邊的頂點*/

------minCost＝MaxWeight;-/*MaxWeight為定義的最大權值*/

--------j＝1;

-----k＝1;---/*保存當前最小權值邊的弧尾頂點序號*/

--------while(j<n)

--------{

---/*尋找最小權值的邊*/

----------if(lowCost［j］<minCost&&lowCost［j］!＝0)

------------{

----------------minCost＝lowCost［j］;

-----k＝j;----/*保存當前最小權值邊的弧尾頂點序號*/

------------}

------------j＋＋;

--------}

--------printf("頂點值＝%c-邊的權值＝%d＼n"，

----G.Vertices.list［k］，minCost);

--------lowCost［k］＝0;---/*標記該頂點已在集合U中*/

--------/*修改經(jīng)序號為k的頂點到其他頂點的最小代價值*/

--------for(j＝1;j<n;j＋＋)

--------{

------------if(G.edge［k］［j］<lowCost［j］)

----------------lowCost［j］＝G.edge［k］［j］;

--------}

----}

}分析上述普里姆函數(shù)，函數(shù)主要是一個兩重循環(huán)，其中每一重循環(huán)的次數(shù)均為頂點個數(shù)n，所以該算法的時間復雜度為O(n2)。由于該算法的時間復雜度只與圖中頂點的個數(shù)有關，而與圖中邊的條數(shù)無關，所以當該算法用于頂點個數(shù)不很多而邊稠密的圖時時間效率較好。

以圖8-10(a)所示的無向連通帶權圖為例設計測試上述普里姆函數(shù)的程序。設計設上述普里姆函數(shù)存放在文件Prim.h中，測試程序設計如下：

＃include<stdio.h>

＃include<stdlib.h>

＃include<malloc.h>

typedefcharDataType;---

＃defineMaxSize100

＃defineMaxVertices10

＃defineMaxWeight10000

＃include"AdjMGraph.h"

＃include"AdjMGraphCreate.h"

＃include"Prim.h"

voidmain(void)

{

----AdjMWGraphg;

----chara［］＝{′A′，′B′，′C′，′D′，′E′，′F′，′G′};

RowColWeightrcw［］＝{{0，1，50}，{1，0，50}，{0，2，60}，{2，0，60}，{1，3，65}，

--{3，1，65}，{1，4，40}，{4，1，40}，{2，3，52}，{3，2，52}，{2，6，45}，{6，2，45}，

--{3，4，50}，{4，3，50}，{3，5，30，}，{5，3，30}，{3，6，42}，{6，3，42}，{4，5，70}，

--{5，4，70}};

---intn＝7，e＝20;

----CreatGraph(&g，a，n，rcw，e);

----Prim(g);

}程序的運行結果為：

頂點值＝A

頂點值＝B--邊的權值＝50

頂點值＝E--邊的權值＝40

頂點值＝D--邊的權值＝50頂點值＝F--邊的權值＝30

頂點值＝G--邊的權值＝42

頂點值＝C--邊的權值＝45

程序輸出的頂點序列和邊的權值序列對應了圖8-10(b)到圖8-10(h)的最小生成樹構造過程。在解決實際問題時，我們根據(jù)上述程序運行的結果，再結合原問題的帶權圖，即可構造出圖8-10(a)的最小生成樹圖8-10(h)。8.4.4克魯斯卡爾算法

不同于普里姆算法，克魯斯卡爾算法是一種按照帶權圖中邊的權值的遞增順序構造最小生成樹的方法?？唆斔箍査惴ǖ乃枷胧牵涸O無向連通帶權圖G＝(V，E)，其中V為頂點的集合，E為邊的集合。設帶權圖G的最小生成樹T由頂點集合和邊的集合構成，其初值為T＝(V，{})，即初始時最小生成樹T只由帶權圖G中的頂點集合組成，各頂點之間沒有一條邊。這樣，最小生成樹T中的各個頂點各自構成一個連通分量。然后，按照邊的權值遞增的順序考察帶權圖G中的邊集E中的各條邊，若被考察的邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊加入到最小生成樹T，同時把兩個連通分量連接為一個連通分量；若被考察的邊的兩個頂點屬于T的同一個連通分量，則將此邊舍去。如此下去，當T中的連通分量個數(shù)為1時，T中的該連通分量即為帶權圖G的一棵最小生成樹。對于圖8-10(a)所示的無向連通帶權圖，按照克魯斯卡爾算法構造最小生成樹的過程如圖8-11(a)~(f)所示。根據(jù)克魯斯卡爾算法構造最小生成樹的方法，按照帶權圖G中邊的權值從小到大的順序，反復選擇當前尚未被選取的邊集合中權值最小的邊加入到最小生成樹中，直到帶權圖中所有頂點都加入到最小生成樹中為止。最后圖8-11(f)所示就是所構造的最小生成樹。

圖8-11克魯斯卡爾算法構造最小生成樹的過程按照上述克魯斯卡爾算法思想設計克魯斯卡爾算法函數(shù)主要包括兩個部分：首先是帶權圖G中e條邊的權值的排序；其次是判斷新選取的邊的兩個頂點是否屬于同一個連通分量。對帶權圖G中e條邊的權值的排序方法可以有很多種，各自的時間復雜度均不相同，對e條邊的權值排序算法時間復雜度較好的算法有快速排序法、堆排序法等，這些排序算法的時間復雜度均可以達到O(elbe)。判斷新選取的邊的兩個頂點是否屬于同一個連通分量的問題是一個在最多有n個頂點的生成樹中遍歷尋找新選取的邊的兩個頂點是否存在的問題，此算法的時間復雜度最壞情況下為O(n)。

從上述分析我們可以得出，克魯斯卡爾算法的時間復雜度主要由排序方法決定，而克魯斯卡爾算法的排序方法只與帶權圖中邊的個數(shù)有關，而與帶權圖中頂點的個數(shù)無關，當使用時間復雜度為O(elbe)的排序方法時，克魯斯卡爾算法的時間復雜度即為O(elbe)，因此當帶權圖的頂點個數(shù)較多、而邊的條數(shù)較少時，使用克魯斯卡爾算法構造最小生成樹效果較好。

8.5.1最短路徑的基本概念

在一個圖中，若從一個頂點到另一個頂點存在著路徑，定義路徑長度為一條路徑上所經(jīng)過的邊的數(shù)目。圖中從一個頂點到另一個頂點可能存在著多條路徑，我們把路徑長度最短的那條路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離。8.5最短路徑在一個帶權圖中，若從一個頂點到另一個頂點存在著一條路徑，則稱該路徑上所經(jīng)過邊的權值之和為該路徑上的帶權路徑長度。帶權圖中從一個頂點到另一個頂點可能存在著多條路徑，我們把帶權路徑長度值最小的那條路徑也叫做最短路徑，其帶權路徑長度也叫做最短路徑長度或最短距離。

實際上，不帶權的圖上的最短路徑問題也可以歸結為帶權圖上的最短路徑問題。因只要把不帶權的圖上的所有邊的權值均定義為1，則不帶權的圖上的最短路徑問題也就歸結為帶權圖上的最短路徑問題。因此不失一般性，我們這里只討論帶權圖上的最短路徑問題。帶權圖分無向帶權圖和有向帶權圖，當把無向帶權圖中的每一條邊(vi，vj)都定義為弧<vi，vj>和弧<vj，vi>，則有向帶權圖就變成了無向帶權圖。因此不失一般性，我們這里只討論有向帶權圖上的最短路徑問題。

圖8-12是一個有向帶權圖及其鄰接矩陣。該帶權圖從頂點A到頂點D有4條路徑，分別為：路徑(A，D)，其帶權路徑長度為30；路徑(A，C，F(xiàn)，D)，其帶權路徑長度為22；

路徑(A，C，B，E，D)，其帶權路徑長度為32；路徑(A，C，F(xiàn)，E，D)，其帶權路徑長度為34。路徑(A，C，F(xiàn)，D)稱為最短路徑，其帶權路徑長度22稱為最短距離。

圖8-12有向帶權圖及其鄰接矩陣

(a)有向帶權圖；(b)鄰接矩陣8.5.2從一個頂點到其余各頂點的最短路徑

對于從有向帶權圖中一個確定頂點(稱為源點)到其余各頂點的最短路徑問題，狄克斯特拉(Dijkastra)提出了一個按路徑長度遞增的順序逐步產(chǎn)生最短路徑的構造算法。狄克斯特拉算法的思想是：設置兩個頂點的集合S和T，集合S中存放已找到最短路徑的頂點，集合T中存放當前還未找到最短路徑的頂點。初始狀態(tài)時，集合S中只包含源點，設為v0，然后從集合T中選擇到源點v0路徑長度最短的頂點u加入到集合S中，

集合S中每加入一個新的頂點u都要修改源點v0到集合T中剩余頂點的當前最短路徑長度值，集合T中各頂點的新的當前最短路徑長度值為原來的當前最短路徑長度值與從源點過頂點u到達該頂點的路徑長度中的較小者。此過程不斷重復，直到集合T中的頂點全部加入到集合S中為止。

對于圖8-12所示的有向帶權圖，圖8-13(a)~(f)給出了狄克斯特拉算法求從頂點A到其余各頂點的最短路徑的過程。圖中虛線表示當前可選擇的邊，實線表示算法已確定包括到集合S中的頂點所對應的邊。

圖8-13狄克斯特拉算法求從頂點A到其余各頂點最短路徑的過程*8.5.3狄克斯特拉算法設計和實現(xiàn)

根據(jù)狄克斯特拉算法，設計實現(xiàn)從一個頂點到其余各頂點的最短路徑函數(shù)的具體方法如下：設計函數(shù)有2個輸入?yún)?shù)——帶權圖G和源點序號v0；函數(shù)有2個輸出參數(shù)——最短距離distance［n］和最短路徑下標path［n］。函數(shù)把帶權圖G從源點v0到其余各頂點的最短距離數(shù)值存放在數(shù)組distance中，把帶權圖G從源點v0到其余各頂點的最短路徑上到達目標頂點的前一頂點序號存放在數(shù)組path中。初始狀態(tài)時若從源點v0到頂點vi有邊，有distance［i］為該邊的權值，則令path［i］為源點v0；若從源點v0到頂點vi無邊，有distance［i］為定義的最大權值(這里為10000)，則令distance［i］為-1。

函數(shù)設計成迭代過程。設從源點v0到其余各頂點中最短的一條路徑為(v0，vk)，其中vk滿足：

distance［vk］＝min{distance［vi］|vi∈V-v0}-V是帶權圖G的頂點一旦確定distance［vk］且distance［vk］小于最大權值，則標識頂點vk已從集合T到集合S中。迭代構造下一條最短路徑的方法是：假設下次最短路徑的頂點是vj，則可想而知，最短路徑或者是(v0，vj)，或者是(v0，vk，vj)；其最短距離distance［vj］或者是從頂點v0到頂點vj有向邊的權值，或者是從頂點v0到頂點vk有向邊的權值與從頂點vk到頂點vj有向邊的權值之和，即distance［vk］與從頂點vk到頂點vj有向邊的權值之和。同樣地，一旦確定distance［vj］且distance［vj］小于最大權值，則標識頂點vj已從集合T到集合S中。這樣的迭代過程一直進行到所有頂點都從集合T到了集合S中或目前已不存在任何一條邊可選擇為止。要說明的是，這樣的迭代過程要確定從源點v0到各個頂點的最短路徑序列(如(v0，vk，vj))的算法很復雜，但要確定從源點v0到各個頂點的最短路徑的前一個頂點的序號卻很容易。

下面函數(shù)的數(shù)組path中就存放了從源點v0到各個頂點的最短路徑的前一個頂點的序號。voidDijkstra(AdjMWGraphG，intv0，intdistance［］，intpath［］)

/*帶權圖G從下標v0頂點到其他頂點的最短距離distance和最短路徑下標path*/

{

----intn＝G.Vertices.size;

----int*s＝(int*)malloc(sizeof(int)*n);

----intminDis，i，j，u;

----/*初始化*/

----for(i＝0;i<n;i＋＋)---------------------

----{

--------distance［i］＝G.edge［v0］［i］;

--------s［i］＝0;

--------if(i!＝v0&&distance［i］<MaxWeight)path［i］＝v0;

--------elsepath［i］＝-1;

----}

----s［v0］＝1;--/*標記頂點v0已從集合T加入到集合S中*/

----/*在當前還未找到最短路徑的頂點集中選取具有最短距離的頂點u*/

----for(i＝1;i<n;i＋＋)

----{

--------minDis＝MaxWeight;

--------for(j＝0;j<＝n;j＋＋)

------------if(s［j］＝＝0&&distance［j］<minDis)

------------{

----------------u＝j;

----------------minDis＝distance［j］;

------------}

--------/*當已不再存在路徑時算法結束；此語句對非連通圖是必須的*/

--------if(minDis＝＝MaxWeight)return;-----

--------s［u］＝1;-/*標記頂點u已從集合T加入到集合S中*/

--------/*修改從v0到其他頂點的最短距離和最短路徑*/

--------for(j＝0;j<n;j＋＋)

-------if(s［j］＝＝0&&G.edge［u］［j］<MaxWeight&&

-------distance［u］＋G.edge［u］［j］<distance［j］)

------------{

--------/*頂