大二上學(xué)期學(xué)習(xí)第

第五章圖圖（Graph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，對(duì)結(jié)點(diǎn)（圖中常稱為頂點(diǎn)）的前趨和后繼個(gè)數(shù)不加限制，即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)。圖狀結(jié)構(gòu)可以描述各種復(fù)雜的數(shù)據(jù)對(duì)象。圖的應(yīng)用極為廣泛，特別是近年來的迅速發(fā)展，已經(jīng)滲透到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。圖的出現(xiàn)最早可以追溯到1736年，著名的數(shù)學(xué)家歐拉使用它解決了經(jīng)典的柯尼斯堡七橋難題。從此，有關(guān)圖的理論形成了一個(gè)專門的數(shù)學(xué)分支——圖論?？履崴贡な?8世紀(jì)初普魯士的一個(gè)小鎮(zhèn)，普雷格爾河流經(jīng)此鎮(zhèn)，共有7座橋橫跨河上，把全鎮(zhèn)連接起來。當(dāng)時(shí)當(dāng)?shù)鼐用駸嶂杂谝豁?xiàng)非常有趣的消遣活動(dòng)：在星期六作一次走過所有七座橋的散步，每座橋只能經(jīng)過一次而且起點(diǎn)與終點(diǎn)必須是同一地點(diǎn)，這就是柯尼斯堡七橋問題。為了解決七橋問題，歐拉第一次提出了“圖”的概念。歐拉用點(diǎn)表示島和陸地，兩點(diǎn)之間的連線（邊）表示連接它們的橋，將河流、小島和橋簡(jiǎn)化為一幅圖。定義與頂點(diǎn)相連的邊的數(shù)目為頂點(diǎn)的度，歐拉證明了如果這個(gè)問題有答案的話只有在每個(gè)頂點(diǎn)的度都是偶數(shù)的情況下才成立，而在七橋所形成的圖中沒有一個(gè)點(diǎn)具有偶數(shù)條邊，因此七橋問題不存在解。圖狀結(jié)構(gòu)的實(shí)際背景

在城市之間建立通訊網(wǎng)絡(luò)，使得其中的任意兩個(gè)城市之間有直接或間接的通訊線路，假設(shè)已知每對(duì)城市之間通訊線路的造價(jià)，要求找出一個(gè)造價(jià)最低的通訊網(wǎng)絡(luò)。

城市航線網(wǎng)天津北京上海廣州深圳計(jì)算機(jī)網(wǎng)絡(luò)computerconnection

不一定具有一個(gè)根結(jié)點(diǎn)沒有明顯的父子關(guān)系從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)可能有多個(gè)（或0個(gè)）路徑圖

VS.樹

第五章圖5.1基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4拓?fù)渑判?.5關(guān)鍵路徑5.6最短路徑5.7最小支撐樹5.8圖的應(yīng)用定義5.1：圖G由兩個(gè)集合V和E組成，記為G=(V,E)；其中V是頂點(diǎn)的有限集合，E是連接V中兩個(gè)不同頂點(diǎn)的邊的有限集合。通常，也將圖G的頂點(diǎn)集和邊集分別記為V(G)和E(G)。如果E中的頂點(diǎn)對(duì)是有序的，即E中的每條邊都是有方向的，則稱G為有向圖。如果頂點(diǎn)對(duì)是無序?qū)?，則稱G是無向圖。5.1圖的基本概念定義5.2

若G=(V,E)是有向圖，則它的一條有向邊是由V中兩個(gè)頂點(diǎn)構(gòu)成的有序?qū)?，亦稱為弧，記為<w,v>，其中w是邊的始點(diǎn)，又稱弧尾；v是邊的終點(diǎn)，又稱弧頭。有向圖G=（V，E）V={v1，v2，v3，v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}v1v3v2v4無向圖G=(V,E)V={V1,V2,V3,V4,V5}E={(V1,V4),(V1,V2),(V2,V3),(V2,V5),(V3,V4),(V3,V5)}V1V4V3V2V5定義5.3

在無向圖中，若兩個(gè)頂點(diǎn)w和v之間存在一條邊(w,v)，則稱w,v是相鄰的，二者互為鄰接頂點(diǎn)。在有向圖中，若存在一條邊<w,v>，則稱頂點(diǎn)w鄰接到頂點(diǎn)v，頂點(diǎn)v鄰接自頂點(diǎn)w.v3v4v1v2oooov1v2v3v4定義5.4

由于E是邊的集合，故一個(gè)圖中不會(huì)多次出現(xiàn)一條邊。若去掉此限制，則由此產(chǎn)生的結(jié)構(gòu)稱為多重圖。圖(c)就是一個(gè)多重圖。

(a)(b)(c)很多問題都可以抽象成一個(gè)圖結(jié)構(gòu)，考慮如下三個(gè)例子：將電影界的所有演員構(gòu)成頂點(diǎn)集V，其中兩位演員u和v如果共同出演過至少一部影片，那么在u和v之間連接一條邊。演員之間的這種合作關(guān)系看作對(duì)等關(guān)系。按照這種方式建立的圖是無向圖。將C++程序中所有的類構(gòu)成頂點(diǎn)集V，且如果類a是類b的子類，則定義一條從b指向a的有向邊。按照這種方式建立的圖是有向圖。將多個(gè)城市構(gòu)成頂點(diǎn)集V，如果城市a和城市b之間有一條高速公路，則在a和b之間連接一條邊。允許在兩個(gè)城市之間修建多條高速公路。按照這種方式建立的圖是多重圖。定義5.5

設(shè)G是無向圖，vV(G)，E(G)中以v為端點(diǎn)的邊的個(gè)數(shù)，稱為頂點(diǎn)的度。若G是有向圖，則v的出度是以v為始點(diǎn)的邊的個(gè)數(shù)，v的入度是以v為終點(diǎn)的邊的個(gè)數(shù)。有向圖中，以某頂點(diǎn)為弧頭的弧的數(shù)目稱為該頂點(diǎn)的入度。以某頂點(diǎn)為弧尾的弧的數(shù)目稱為該頂點(diǎn)的出度。頂點(diǎn)的度=入度+出度。度:D(v)入度:ID(v)出度:OD(v)D(v)=ID(v)+OD(v)Graph2V5V1V2V3V4V4V3V2V1Graph1設(shè)圖G(可以為有向或無向圖)共有n個(gè)頂點(diǎn)，e條邊，若頂點(diǎn)vi的度數(shù)為D(vi)，則因?yàn)橐粭l邊關(guān)聯(lián)兩個(gè)頂點(diǎn)，而且使得這兩個(gè)頂點(diǎn)的度數(shù)分別增加1。因此頂點(diǎn)的度數(shù)之和就是邊的兩倍。定義5.6

設(shè)G是圖，若存在一個(gè)頂點(diǎn)序列使得或?qū)儆贓(G)，則稱vp到vq存在一條路徑，其中vp

稱為起點(diǎn)，vq稱為終點(diǎn)。

路徑的長(zhǎng)度是該路徑上邊的個(gè)數(shù)。如果一條路徑上除了起點(diǎn)和終點(diǎn)可以相同外，再不能有相同的頂點(diǎn)，則稱此路徑為簡(jiǎn)單路徑。如果一條簡(jiǎn)單路徑的起點(diǎn)和終點(diǎn)相同，且路徑長(zhǎng)度大于等于2，則稱之為簡(jiǎn)單回路。圖(a)中，v1到v3之間存在一條路徑v1,v2,v5,v4,v3，同時(shí)這也是一條簡(jiǎn)單路徑；v1,v2,v5,v4,v3,v1是一條簡(jiǎn)單回路。

(a)(b)(c)V5V4V2V1V3V1V2V3V4路徑：v1v3v4v3v5簡(jiǎn)單路徑：v1v3v5簡(jiǎn)單回路：v1v2v3v1路徑：v1v3v2v4v3v2簡(jiǎn)單路徑：v1v3v2簡(jiǎn)單回路：v1v3v2v1定義5.7

設(shè)G，H是圖，如果V(H)V(G)，E(H)E(G)，則稱H是G的子圖，G是H的母圖。如果H是G的子圖，并且V(H)=V(G)，則稱H為G的支撐子圖?！璙5V1V2V3V4V1V1V2V5V2V3V5V1V2V3V4V4V3V2V1V1V2V1V4V3V2V1V4V3V1……定義5.8

設(shè)G是圖，若存在一條從頂點(diǎn)vi到頂點(diǎn)vj的路徑，則稱vi與vj可及(連通)。若G為無向圖，且V(G)中任意兩頂點(diǎn)都可及，則稱G為連通圖。若G為有向圖，且對(duì)于V(G)中任意兩個(gè)不同的頂點(diǎn)vi和vj

，vi與vj可及，vj與vi也可及，則稱G為強(qiáng)連通圖。也可以定義“弱連通圖”的概念，即在任何頂點(diǎn)u和v之間，至少存在一條從u到v的路徑或者存在一條從v到u的路徑。V5V4V2V1V3V1V2V3V4定義5.9設(shè)圖G=(V，E)是無向（或有向）圖，若G的子圖GK是一個(gè)（強(qiáng)）連通圖，則稱GK

為G的（強(qiáng)）連通子圖。定義5.10對(duì)于G的一個(gè)連通子圖GK，如果不存在G的另一個(gè)連通子圖G′，使得V(GK)?V(G′)，則稱GK為G的連通分量。(a)(b)(c)(d)(e)一個(gè)圖的連通子圖e是a的連通分量連通分量V4V3V1V2V4V3V2V1連通分量BAEJKGLMDIFCHALJCFBMDEKIHG有時(shí)候，圖不僅要表示出元素之間是否存在某種關(guān)系，同時(shí)還需要表示與這一關(guān)系相關(guān)的某些信息。例如在計(jì)算機(jī)網(wǎng)絡(luò)對(duì)應(yīng)的圖中，頂點(diǎn)表示計(jì)算機(jī)，頂點(diǎn)之間的邊表示計(jì)算機(jī)之間的通訊鏈路。實(shí)際中，為了管理計(jì)算機(jī)網(wǎng)絡(luò)，我們需要這個(gè)圖包含更多的信息，例如每條通訊鏈路的物理長(zhǎng)度、成本和帶寬等信息。為此，我們?yōu)閭鹘y(tǒng)圖中的每條邊添加相應(yīng)的數(shù)據(jù)域以記錄所需要的信息。定義5.11

設(shè)G=(V,E)是圖，若對(duì)圖中的任意一條邊l，都有實(shí)數(shù)w(l)與其對(duì)應(yīng)，則稱G為權(quán)圖，記為G=(V,E,w)。記w(u,v)表示w((u,v))或w(<u,v>)，規(guī)定：?u∈V,有w((u,u))=0或w(<u,u>)=0?u,v∈V,若(u,v)?E(G)或<u,v>?E(G)

則w((u,v))=＋∞或w(<u,v>)=＋∞定義5.12

若是權(quán)圖G中的一條路徑，則稱為加權(quán)路徑

的長(zhǎng)度或權(quán)重。權(quán)通常用來表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或費(fèi)用。V1V2V3V42357

無向圖

有向圖端點(diǎn)弧弧頭弧尾相鄰的鄰接到鄰接自度出度入度連通圖強(qiáng)連通圖

第五章圖5.1基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4拓?fù)渑判?.5關(guān)鍵路徑5.6最短路徑5.7最小支撐樹5.8圖的應(yīng)用鄰接矩陣鄰接表(逆鄰接表)1、圖的存儲(chǔ)結(jié)構(gòu)用順序方式或鏈接方式存儲(chǔ)圖的頂點(diǎn)表v0,v1,…vn-1,圖的邊用n×n階矩陣A=(aij)表示，A的定義如下：（a）若圖為權(quán)圖，aij對(duì)應(yīng)邊<vi,vj>的權(quán)值；（b）若圖為非權(quán)圖，則（1）aii=0；（2）aij=1，當(dāng)i≠j且<vi,vj>或(vi,vj)存在時(shí)；（3）aij=0，當(dāng)i≠j且<vi,vj>或(vi,vj)不存在時(shí)。稱矩陣A為圖的鄰接矩陣。1、鄰接矩陣[例1]無向圖的鄰接矩陣無向圖的鄰接矩陣是對(duì)稱陣。0123

01111001100111100123V0V3V2V1[例2]有向圖的鄰接矩陣V0V3V4V1V201234

010001000101010100000001001234

[例3]權(quán)圖的鄰接矩陣0123035830

∞45∞0284200123V0V3V2V135284特點(diǎn)：無向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)，有n個(gè)頂點(diǎn)的無向圖需存儲(chǔ)空間為n(n+1)/2有向圖鄰接矩陣不一定對(duì)稱，有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2

借助鄰接矩陣，可以很容易地求出圖中頂點(diǎn)的度。無向圖

鄰接矩陣的第i行（或第i列）的非零元素的個(gè)數(shù)是頂點(diǎn)Vi的度。有向圖鄰接矩陣第i行的非零元素的個(gè)數(shù)為頂點(diǎn)Vi的出度；第i列的非零元素的個(gè)數(shù)為頂點(diǎn)Vi的入度。Graph1V4V3V2V1Graph2V5V1V2V3V4

0

1

1

000000001

1000

01010101010101110100011002、鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表（n個(gè)頂點(diǎn)建立n個(gè)單鏈表），第i個(gè)單鏈表中的結(jié)點(diǎn)包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。由順序存儲(chǔ)的頂點(diǎn)表和鏈接存儲(chǔ)的邊鏈表構(gòu)成的圖的存儲(chǔ)結(jié)構(gòu)被稱為鄰接表。

V0V3V2V1V0V1V2V30231123∧012∧03∧03∧頂點(diǎn)的結(jié)構(gòu)

非權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu)為（VerAdj,link）權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu)為（VerAdj,cost,link）VerNameadjacentVerAdjcostlinkVerAdjlink[例1]無向圖的鄰接表V0V3V2V1V0V1V2V30231123∧012∧03∧03∧[例2]有向圖的鄰接表V0V1V2V3V4024311∧3∧0∧0∧4∧1∧3∧V0V3V4V1V2對(duì)于用鄰接表存儲(chǔ)的有向圖，每條邊只對(duì)應(yīng)一個(gè)邊結(jié)點(diǎn)；而對(duì)于用鄰接表存儲(chǔ)的無向圖，每條邊則對(duì)應(yīng)兩個(gè)邊結(jié)點(diǎn)。根據(jù)鄰接表，可以統(tǒng)計(jì)出有向圖中每個(gè)頂點(diǎn)的出度。但是，如果要統(tǒng)計(jì)頂點(diǎn)的入度，每統(tǒng)計(jì)一個(gè)頂點(diǎn)，就要遍歷所有的邊結(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(e)(e為圖中邊的個(gè)數(shù))，從而統(tǒng)計(jì)所有頂點(diǎn)入度的時(shí)間復(fù)雜度為O(ne)(n為圖的頂點(diǎn)個(gè)數(shù))。建立逆鄰接表(頂點(diǎn)的指向關(guān)系與鄰接表恰好相反)，根據(jù)逆鄰接表，很容易統(tǒng)計(jì)出圖中每個(gè)頂點(diǎn)的入度。[例3]有向圖的逆鄰接表V0V3V4V1V2V0V1V2V3V4024311∧0∧2∧2∧4∧1∧3∧∧[例4]權(quán)圖的鄰接表V0V3V2V135284V0V1V2V30231133∧825082∧214053∧2033∧4采用鄰接矩陣還是用鄰接表來存儲(chǔ)圖，要視對(duì)給定圖實(shí)施的具體操作而定。對(duì)于邊很多的圖(也稱稠密圖)，適于用鄰接矩陣存儲(chǔ)，因?yàn)檎加玫目臻g少。而對(duì)于頂點(diǎn)多而邊少的圖(也稱稀疏圖)，若用鄰接矩陣存儲(chǔ)，對(duì)應(yīng)的鄰接矩陣將是一個(gè)稀疏矩陣，存儲(chǔ)利用率很低。因此，頂點(diǎn)多而邊少的圖適于用鄰接表存儲(chǔ)。鄰接矩陣存儲(chǔ)的圖類Graph_Matrix鄰接表存儲(chǔ)的圖類Graph_List2、圖的實(shí)現(xiàn)1.用鄰接矩陣存儲(chǔ)的圖類●Graph_Matrix類聲明constintMaxGraphSize=256;//圖的最大頂點(diǎn)個(gè)數(shù)constintMaxWeight=1000;//邊的最大權(quán)值template<classT>

classGraph_Matrix{private:

SLList<T>VertexList;//頂點(diǎn)表

intedge[MaxGraphSize][MaxGraphSize];//鄰接矩陣

intgraphsize;//當(dāng)前頂點(diǎn)數(shù)public://I.構(gòu)造函數(shù)與析構(gòu)函數(shù)

Graph_Matrix(); ~Graph_Matrix();//II.圖的維護(hù)函數(shù)

intGraphEmpty(void)const//檢測(cè)圖是否為空

intGraphFull(void)const;//檢測(cè)圖是否已滿，即頂點(diǎn)個(gè)數(shù)是否越界

intNumberOfVertices(void)const;//返回圖的頂點(diǎn)個(gè)數(shù)

intNumberOfEdges(void)const;//返回圖的邊個(gè)數(shù)

intGetWeight(constintv1,constintv2);//返回指定邊的權(quán)值

int*&GetNeighbors(constintv);//返回頂點(diǎn)v的鄰接頂點(diǎn)表

intGetFirstNeighbor(constintv);//返回序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號(hào)

intGetNextNeighbor(constintv1,constintv2);//返回序號(hào)為v1的頂點(diǎn)相對(duì)于序號(hào)為v2的頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)的序號(hào)

voidInsertVertex(constint&v);//向圖中插入一個(gè)頂點(diǎn)

voidInsertEdge(constint&v1,constint&v2,intweight);//向圖中插入一條邊

voidDeleteVertex(constint&v);//從圖中刪除一個(gè)頂點(diǎn)

voidDeleteEdge(constint&v1,constint&v2);//從圖中刪除一條邊

//III.圖的基本算法

voidDepthFirstSearch();//圖的深度優(yōu)先搜索(遞歸)voidDFS(constintv);//從頂點(diǎn)v開始進(jìn)行圖的深度優(yōu)先搜索(迭代方法)voidBFS(constintv);//從頂點(diǎn)v開始進(jìn)行圖的廣度優(yōu)先搜索

voidTopoOrder();//圖的拓?fù)渑判?/p>

voidCriticalPath();//輸出圖的關(guān)鍵路徑

voidShortestPath(constintv);//求無權(quán)圖中頂點(diǎn)v到其他頂點(diǎn)的最短路徑

voidDShortestPath(constintv);//求正權(quán)圖中頂點(diǎn)v到其他頂點(diǎn)的最短路徑

voidAllLength();//求正權(quán)圖中每對(duì)頂點(diǎn)間的最短路徑

voidPrim();//構(gòu)造圖的最小支撐樹的普里姆算法

};//構(gòu)造函數(shù),創(chuàng)建一個(gè)圖Graph_Matrix::Graph_Matrix(){cin>>graphsize;for(inti=0;i<graphsize;i++)for(intj=0;j<graphsize;j++)cin>>edge[i][j]; }0123035830

∞45∞0284200123ADCB35284//取得序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號(hào)intGraph_Matrix::GetFirstNeighbor(constintv){if(v==-1)return-1;for(inti=0;i<graphsize;i++) if(edge[v][i]>0&&edge[v][i]<MaxWeight) returni;return-1;//若v沒有鄰接頂點(diǎn)，則返回-1}0123035830

∞45∞0284200123ADCB35284//取得頂點(diǎn)v1相對(duì)于v2的下一個(gè)鄰接頂點(diǎn)的序號(hào)intGraph_Matrix::GetNextNeighbor(constintv1,constintv2){if(v1==-1||v2==-1)return-1;for(inti=v2+1;i<graphsize;i++) if(edge[v1][i]>0&&edge[v1][i]<MaxWeight) returni; return-1;//若在v2之后沒有與v1鄰接的頂點(diǎn)，則返回-1}0123035830

∞45∞0284200123ADCB35284刪除頂點(diǎn)Vertex算法思想：不僅要從頂點(diǎn)表中刪除該頂點(diǎn)，還需要?jiǎng)h除該頂點(diǎn)所發(fā)出的邊以及所有的入邊，即在鄰接矩陣中刪除相應(yīng)的行和列。2.用鄰接表存儲(chǔ)的圖類Graph_ListV0V3V2V1V0V1V2V30231123∧012∧03∧03∧2.用鄰接表存儲(chǔ)的圖類Graph_List//邊結(jié)點(diǎn)的結(jié)構(gòu)體structEdge{friendclassGraph_List;intVerAdj;//鄰接頂點(diǎn)序號(hào)，從0開始編號(hào)

intcost; //邊的權(quán)值

Edge*link;//指向下一個(gè)邊結(jié)點(diǎn)的指針};//頂點(diǎn)表中結(jié)點(diǎn)的結(jié)構(gòu)體structVertex{ friendclassGraph_List; intVerName; //頂點(diǎn)的名稱

Edge*adjacent; //邊鏈表的頭指針}

//采用鄰接表存儲(chǔ)的Graph_List類定義classGraph_List{private:Vertex*Head;//頂點(diǎn)表頭指針intgraphsize;//圖中當(dāng)前頂點(diǎn)的個(gè)數(shù)

public://I.圖的構(gòu)造函數(shù)和析構(gòu)函數(shù)Graph_List();~Graph_List(); //II.圖的維護(hù)函數(shù)與Graph_Matrix類中的維護(hù)函數(shù)相同。//III.圖的基本算法與Graph_Matrix類中的基本算法相同。

};//求序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號(hào)intGraph_List::GetFirstNeighbor(constintv){if(v==-1)return-1;Edge*p=Head[v].adjacent;if(p!=NULL)returnpVerAdj;elsereturn-1;}ADCBABCD0231123∧012∧03∧03∧//求序號(hào)為v1的頂點(diǎn)相對(duì)于序號(hào)為v2的頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)的序號(hào)intGraph_List::GetNextNeighbor(constintv1,constintv2){if(v1!=-1&&v2!=-1){Edge*p=Head[v1].adjacent;while(pVerAdj!=v2&&p!=NULL) //令p指向v2所在的邊結(jié)點(diǎn)

p=plink;if(p==NULL)return-1;p=plink;//找v2的下一個(gè)邊結(jié)點(diǎn)

if(p==NULL)return-1;returnpVerAdj;}return-1;}ADCBABCD0231123∧012∧03∧03∧

第五章圖5.1基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4拓?fù)渑判?.5關(guān)鍵路徑5.6最短路徑5.7最小支撐樹5.8圖的應(yīng)用從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，就叫做圖的遍歷(GraphTraversal)。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組visited[]，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個(gè)頂點(diǎn)

i

被訪問，就立即讓visited[i]

為1，防止它被多次訪問。5.3.1深度優(yōu)先遍歷●深度優(yōu)先遍歷又被稱為深度優(yōu)先搜索DFS

(DepthFirstSearch)●基本思想:

DFS在訪問圖中某一起始頂點(diǎn)v后，由v出發(fā)，訪問它的任一鄰接頂點(diǎn)w1；再?gòu)膚1出發(fā)，訪問與w1鄰接但還沒有訪問過的頂點(diǎn)w2；然后再?gòu)膚2出發(fā)，進(jìn)行類似的訪問，…如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn)u為止。接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。深度優(yōu)先搜索DFS(DepthFirstSearch)深度優(yōu)先搜索的示例1.遞歸算法算法DepthFirstSearch(v,visited)/*圖的深度優(yōu)先遍歷的遞歸算法*/DFSearch1[初始化]PRINT(v). visited[v]

1.

p

adjacent(Head[v]).DFSearch2[深度優(yōu)先遍歷圖] WHILEp≠∧DO (IFvisited[VerAdj(p)]≠1THEN

DepthFirstSearch(VerAdj(p),visited).

p

link(p).)?算法DFS_Main(){visited=newint[graphsize];//為輔助數(shù)組申請(qǐng)空間

for(intk=0;k<graphsize;k++) visited[k]=0;//數(shù)組初始化

//從序號(hào)為0的頂點(diǎn)出發(fā)，深度優(yōu)先遍歷圖

DepthFirstSearch(0,visited[]);delete[]visited; //釋放輔助數(shù)組空間

}DFSearch1[初始化]PRINT(v).visited[v]

1.

p

adjacent(Head[v]).DFSearch2[深度優(yōu)先遍歷圖]WHILEp≠∧DO(IFvisited[VerAdj(p)]≠1THEN

DepthFirstSearch(VerAdj(p),visited).

p

link(p).)?V1V2V4V3V8V7V6V51234051717262534V1V2V3V4V5V6V7V86001234567V1V2V4V3V8V7V6V5V1V2V4V3V8V7V6V51234051717262534V1V2V3V4V5V6V7V86001234567

可以利用堆棧實(shí)現(xiàn)深度優(yōu)先遍歷的非遞歸算法。堆棧中存放已訪問結(jié)點(diǎn)的未被訪問的鄰接頂點(diǎn)，每次彈出棧頂元素時(shí)，如其未被訪問，則訪問該頂點(diǎn)，并檢查當(dāng)前頂點(diǎn)的邊鏈表，將其未被訪問的鄰接頂點(diǎn)入棧，循環(huán)進(jìn)行。2.非遞歸算法（迭代）算法

首先將所有頂點(diǎn)的visited[]值置為0,初始頂點(diǎn)壓入堆棧；①檢測(cè)堆棧是否為空。若堆棧為空，則迭代結(jié)束；否則，從棧頂彈出一個(gè)頂點(diǎn)v；②如果v未被訪問過，則訪問v，將visited[v]值更新為1，然后根據(jù)v的鄰接頂點(diǎn)表，將v的未被訪問的鄰接頂點(diǎn)壓入棧，執(zhí)行步驟①。A0243156BCDEFG16∧2∧34∧5∧0∧5∧4∧ACGBFED算法DFS(Head,v

,visited.visited)/*圖的深度優(yōu)先遍歷的非遞歸算法*/DFS1[初始化]CREATS(S)./*創(chuàng)建堆棧S*/FORi=1TOnDOvisited[i]0.S

v./*將v壓入棧中*/DFS2[利用堆棧S深度優(yōu)先遍歷圖]WHILENOT(ISEMTS(S))DO/*當(dāng)S不空時(shí)*/

(vS./*彈出堆棧頂元素*/IFvisited[v]=0THEN//若v未被訪問

(PRINT(v).visited[v]1.

p

adjacent(Head[v]).//找v的第一個(gè)鄰接頂點(diǎn)pWHILEpDO (IFvisited[VerAdj(p)]=0THENS

VerAdj(p).//把所有未被訪問的鄰接頂點(diǎn)入棧p

link(p).))

)?算法分析圖中有n個(gè)頂點(diǎn)，e條邊。如果用鄰接表表示圖，沿頂點(diǎn)的adjacent可以找到某個(gè)頂點(diǎn)v的所有鄰接頂點(diǎn)w。由于總共有2e個(gè)邊結(jié)點(diǎn)，所以掃描邊的時(shí)間為O(e)。而且對(duì)所有頂點(diǎn)遞歸訪問1次，所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為O(n2)。非連通圖需要多次調(diào)用深度優(yōu)先遍歷算法Fori=0ton-1DO visited[i]0.Forj=0ton-1DO IFvisited[j]=0THEN

DepthFirstSearch(v[j],visited)V1V2V35.3.2廣度優(yōu)先遍歷

●

基本思想：首先訪問初始點(diǎn)頂點(diǎn)v0，之后依次訪問與v0鄰接的全部頂點(diǎn)w1，w2，...，wk。然后，再順次訪問與w1，w2，...，wk鄰接的尚未訪問的全部頂點(diǎn)，再?gòu)倪@些被訪問過的頂點(diǎn)出發(fā)，逐個(gè)訪問與它們鄰接的尚未訪問過的全部頂點(diǎn)。依此類推，直到連通圖中的所有頂點(diǎn)全部訪問完為止。廣度優(yōu)先搜索BFS(BreadthFirstSearch

)廣度優(yōu)先搜索的示例

廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先搜索類似于樹的層次遍歷，是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。為了實(shí)現(xiàn)逐層訪問，算法中使用一個(gè)隊(duì)列，以便于向下一層訪問。與深度優(yōu)先搜索過程一樣，為避免重復(fù)訪問，需要一個(gè)輔助數(shù)組visited[]

。算法BFS(Head,v,visited.visited)/*廣度優(yōu)先遍歷算法*/BFS1[初始化]CREATQ(Q)./*創(chuàng)建隊(duì)列Q*/FORi=1TOnDOvisited[i]0.

PRINT(v).visited[v]1.Qv./*入隊(duì)*/BFS2[廣度優(yōu)先遍歷]WHILENOT(ISEMTQ(Q))DO/*當(dāng)隊(duì)列不空時(shí)*/

(vQ./*出隊(duì)*/

p

adjacent(Head[v]). WHILEpDO/*依次處理v的每個(gè)未被訪問的鄰接頂點(diǎn)*/ (IFvisited[VerAdj(p)]=0THEN (Q

VerAdj(p). PRINT(VerAdj(p)).visited[VerAdj(p)]1.).

p

link(p).)

)?

WHILENOT(ISEMTQ(Q))DO/*當(dāng)隊(duì)列不空時(shí)*/(vQ./*出隊(duì)*/

p

adjacent(Head[v]).WHILEpDO (IFvisited[VerAdj(p)]=0THEN (Q

VerAdj(p). PRINT(VerAdj(p)).

visited[VerAdj(p)]1.)

p

link(p).))

01234567024315670123457612∧04∧306∧517∧27∧27∧36∧4517∧算法分析如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為d0+d1+…+dn-1=O(e)，其中的di是頂點(diǎn)i的度?？偟臅r(shí)間復(fù)雜度為O(n+e)。如果使用鄰接矩陣，則對(duì)于每一個(gè)被訪問的頂點(diǎn)，循環(huán)要檢測(cè)矩陣中的n個(gè)元素，總的時(shí)間代價(jià)為O(n2)。

第五章圖5.1基本概念5.2圖的存儲(chǔ)結(jié)構(gòu)5.3圖的遍歷5.4拓?fù)渑判?.5關(guān)鍵路徑5.6最短路徑5.7最小支撐樹5.8圖的應(yīng)用

5.4拓?fù)渑判?/p>

1、拓?fù)渑判騿栴}：計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。AOV網(wǎng):在有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)之間的先后關(guān)系，稱這樣的有向圖為AOV網(wǎng)(ActivityOnVertexNetwork)。例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。

[例]按拓?fù)浯涡虬才庞?jì)算機(jī)專業(yè)必修課程計(jì)算機(jī)專業(yè)必修課程課程代號(hào) 課程名稱 先修課程

C0

高等數(shù)學(xué) 無

C1

程序設(shè)計(jì)基礎(chǔ) 無

C2 離散數(shù)學(xué)C0,C1

C3

數(shù)據(jù)結(jié)構(gòu) C2,C4

C4

程序設(shè)計(jì)語言

C1

C5

編譯技術(shù)

C3,C4

C6

操作系統(tǒng)

C3,C8

C7

普通物理 C0

C8

計(jì)算機(jī)原理C7

C0C2C3C5C4C1C7C6C8AOV網(wǎng)中，如果活動(dòng)Vi必須在活動(dòng)Vj之前進(jìn)行，則存在有向邊<Vi

,Vj>.

AOV網(wǎng)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)中如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件，表示該網(wǎng)絡(luò)的構(gòu)建存在邏輯錯(cuò)誤。拓?fù)湫蛄校喊袮OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列，使每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前邊。拓?fù)渑判颍簶?gòu)造AOV網(wǎng)的拓?fù)湫蛄械倪^程被稱為拓?fù)渑判颉Ｐ蛄蠧0,C1,C2,C4,C3,C5,C7,C8,C6序列C1,C4,C0,C2,C7,C8,C3,C5,C6是否為拓?fù)湫蛄?？C0C2C3C5C4C1C7C6C82、拓?fù)渑判蚧静襟E：①

從網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)且輸出之。②

從網(wǎng)中刪除該頂點(diǎn)及其所有出邊。③

執(zhí)行①②，直至所有頂點(diǎn)已輸出，或網(wǎng)中剩余頂點(diǎn)入度均不為0(說明網(wǎng)中存在回路，無法繼續(xù)拓?fù)渑判?C0C2C3C5C4C1C7C6C8

回路與拓?fù)渑判蛉魏螣o回路的AOV網(wǎng)，其頂點(diǎn)均可排成拓?fù)湫蛄?其拓?fù)湫蛄胁灰欢ㄎㄒ?；如果能將AOV網(wǎng)的所有頂點(diǎn)都排入一個(gè)拓?fù)湫蛄校瑒t該AOV網(wǎng)中必定無有向環(huán)；如果得不到所有頂點(diǎn)的拓?fù)湫蛄?，則說明AOV網(wǎng)中存在有向環(huán)(AOV網(wǎng)所代表的工程是不可行的)。存在回路的AOV網(wǎng)，找不到所有頂點(diǎn)的拓?fù)湫蛄小Ｒ虼?，可以用拓?fù)渑判蚺袛嘤邢驁D中是否有回路假定AOV網(wǎng)用鄰接表的形式存儲(chǔ)。為實(shí)現(xiàn)拓?fù)渑判蛩惴?，事先需做好兩?xiàng)準(zhǔn)備工作：建立一個(gè)數(shù)組count[]，count[i]的元素值取對(duì)應(yīng)頂點(diǎn)i的入度；建立一個(gè)堆棧，棧中存放入度為0的頂點(diǎn)，每當(dāng)一個(gè)頂點(diǎn)的入度為0，就將其壓入棧。3、拓?fù)渑判蛩惴?25140002123013425count0243152∧42∧3∧53∧5∧5∧在初始化堆棧和入度數(shù)組count基礎(chǔ)上，拓?fù)渑判蛩惴ê诵牟襟E：FORi=1TOnDO (jPop(S)

/*彈出棧頂j*/PRINT(j). p

adjacent(Head[j]).//掃描j的邊鏈表

WHILEp

DO

(k

VerAdj(p).count[k]

count[k]-1.//k的入度減1IFcount[k]=0THEN//若入度為0，

Push(S,k).//則k入棧

p

link(p).))?用一個(gè)堆