數(shù)據(jù)結(jié)構(gòu)課件：12 第五章 圖1[新]

1、第五章 圖圖（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)用極為廣泛，特別是近年來(lái)的迅速發(fā)展，已經(jīng)滲透到諸如語(yǔ)言學(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)連接起來(lái)。當(dāng)時(shí)當(dāng)?shù)鼐用駸嶂杂谝豁?xiàng)

2、非常有趣的消遣活動(dòng)：在星期六作一次走過(guò)所有七座橋的散步，每座橋只能經(jīng)過(guò)一次而且起點(diǎn)與終點(diǎn)必須是同一地點(diǎn)，這就是柯尼斯堡七橋問(wèn)題。為了解決七橋問(wèn)題，歐拉第一次提出了“圖”的概念。歐拉用點(diǎn)表示島和陸地，兩點(diǎn)之間的連線（邊）表示連接它們的橋，將河流、小島和橋簡(jiǎn)化為一幅圖。定義與頂點(diǎn)相連的邊的數(shù)目為頂點(diǎn)的度，歐拉證明了如果這個(gè)問(wèn)題有答案的話只有在每個(gè)頂點(diǎn)的度都是偶數(shù)的情況下才成立，而在七橋所形成的圖中沒(méi)有一個(gè)點(diǎn)具有偶數(shù)條邊，因此七橋問(wèn)題不存在解。圖狀結(jié)構(gòu)的實(shí)際背景 在城市之間建立通訊網(wǎng)絡(luò)，使得其中的任意兩個(gè)城市之間有直接或間接的通訊線路，假設(shè)已知每對(duì)城市之間通訊線路的造價(jià)，要求找出一個(gè)造價(jià)最低的通訊網(wǎng)

3、絡(luò)。 城市航線網(wǎng)天津北京上海廣州深圳計(jì)算機(jī)網(wǎng)絡(luò)computerconnection 不一定具有一個(gè)根結(jié)點(diǎn) 沒(méi)有明顯的父子關(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為有向圖。如果

4、頂點(diǎn)對(duì)是無(wú)序?qū)?，則稱G是無(wú)向圖。 5.1 圖的基本概念定義5.2 若G = (V, E)是有向圖，則它的一條有向邊是由V中兩個(gè)頂點(diǎn)構(gòu)成的有序?qū)?，亦稱為弧，記為，其中w是邊的始點(diǎn)，又稱弧尾；v是邊的終點(diǎn)，又稱弧頭。有向圖G=（V，E）V= v1，v2，v3，v4E=,v1v3v2v4無(wú)向圖G=(V,E)V=V1, V2, V3, V4 ,V5E=(V1, V4 ), (V1, V2), (V2, V3 ), (V2, V5 ), (V3, V4 ), (V3, V5 ) V1V4V3V2V5定義5.3 在無(wú)向圖中，若兩個(gè)頂點(diǎn)w和v之間存在一條邊(w, v)，則稱w, v是相鄰的，二者互為鄰接頂點(diǎn)

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

6、圖。將多個(gè)城市構(gòu)成頂點(diǎn)集V，如果城市a和城市b之間有一條高速公路，則在a和b之間連接一條邊。允許在兩個(gè)城市之間修建多條高速公路。按照這種方式建立的圖是多重圖。定義5.5 設(shè)G是無(wú)向圖，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(可以為有向

7、或無(wú)向圖)共有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)序列 使得 或 屬于E(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, v

8、4, v3, v1是一條簡(jiǎn)單回路。 (a) (b) (c)V5V4V2V1V3V1V2V3V4路徑：v1 v3 v4 v3 v5簡(jiǎn)單路徑：v1 v3 v5簡(jiǎn)單回路：v1 v2 v3 v1路徑：v1 v3 v2 v4 v3 v2簡(jiǎn)單路徑：v1 v3 v2簡(jiǎn)單回路：v1 v3 v2 v1定義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的支撐子圖。V5V1V2V3V4V1V1V2V5V2V3V5V1V2V3V4V4V3V2V1V1V2V1V4V3V2V1V4V3V1定義5.8 設(shè)G是圖，若存

9、在一條從頂點(diǎn)vi到頂點(diǎn)vj的路徑，則稱vi與vj可及(連通)。若G為無(wú)向圖，且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)是無(wú)向（或有向）圖，若G的子圖GK是一個(gè)（強(qiáng)）連通圖，則稱GK 為G的（強(qiáng)）連通子圖。定義5.10 對(duì)于G的一個(gè)連通子圖GK，如果不存在G的另一個(gè)連通子圖G，使得V(GK)V(G)，則稱G

10、K為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，都有

11、實(shí)數(shù)w(l)與其對(duì)應(yīng)，則稱G為權(quán)圖，記為G = (V, E, w)。記w(u,v)表示w(u,v)或w()，規(guī)定： uV, 有w(u,u)=0或w()=0 u,vV, 若(u,v)E(G)或E(G)則w(u,v)=或w()=定義5.12 若 是權(quán)圖G中的一條路徑，則 稱為加權(quán)路徑 的長(zhǎng)度或權(quán)重。權(quán)通常用來(lái)表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或費(fèi)用。V1V2V3V42357 無(wú)向圖 有向圖 端點(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

12、.8 圖的應(yīng)用鄰接矩陣 鄰接表(逆鄰接表)1、 圖的存儲(chǔ)結(jié)構(gòu)用順序方式或鏈接方式存儲(chǔ)圖的頂點(diǎn)表v0,v1,vn-1 ,圖的邊用nn階矩陣A =(aij)表示，A的定義如下：（a）若圖為權(quán)圖，aij對(duì)應(yīng)邊的權(quán)值；（b）若圖為非權(quán)圖，則（1） aii=0；（2） aij=1，當(dāng)ij且或(vi,vj)存在時(shí)； （3）aij=0，當(dāng)ij且或(vi,vj)不存在時(shí)。稱矩陣A為圖的鄰接矩陣。1、鄰接矩陣?yán)?無(wú)向圖的鄰接矩陣無(wú)向圖的鄰接矩陣是對(duì)稱陣。0123 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 00 1 2 3V0V3V2V1 例2有向圖的鄰接矩陣V0V3V4V1V201234 0

13、1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 00 1 2 3 4 例3權(quán)圖的鄰接矩陣0123 0 3 5 8 3 0 4 5 0 2 8 4 2 00 1 2 3V0V3V2V135284特點(diǎn)：無(wú)向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)，有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n(n+1)/2有向圖鄰接矩陣不一定對(duì)稱，有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n 借助鄰接矩陣，可以很容易地求出圖中頂點(diǎn)的度。無(wú)向圖 鄰接矩陣的第i行（或第i列）的非零元素的個(gè)數(shù)是頂點(diǎn)Vi的度。有向圖 鄰接矩陣第i行的非零元素的個(gè)數(shù)為頂點(diǎn)Vi的出度；第i列的非零元素的個(gè)數(shù)為頂點(diǎn)Vi的入度。Graph

14、1V4V3V2V1Graph2V5V1V2V3V4 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 02、鄰接表鄰接表是圖的一種鏈?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)被稱為鄰接表。 V0V3V2V1V0V1V2V302311230120303頂點(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）

15、VerName adjacentVerAdj cost linkVerAdj link 例1無(wú)向圖的鄰接表V0V3V2V1V0V1V2V302311230120303例2有向圖的鄰接表V0V1V2V3V4024311300413V0V3V4V1V2對(duì)于用鄰接表存儲(chǔ)的有向圖，每條邊只對(duì)應(yīng)一個(gè)邊結(jié)點(diǎn)；而對(duì)于用鄰接表存儲(chǔ)的無(wú)向圖，每條邊則對(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)系

16、與鄰接表恰好相反)，根據(jù)逆鄰接表，很容易統(tǒng)計(jì)出圖中每個(gè)頂點(diǎn)的入度。例3有向圖的逆鄰接表V0V3V4V1V2V0V1V2V3V4024311022413例4 權(quán)圖的鄰接表V0V3V2V135284V0V1V2V3023113382508221405320334采用鄰接矩陣還是用鄰接表來(lái)存儲(chǔ)圖，要視對(duì)給定圖實(shí)施的具體操作而定。對(duì)于邊很多的圖(也稱稠密圖)，適于用鄰接矩陣存儲(chǔ)，因?yàn)檎加玫目臻g少。而對(duì)于頂點(diǎn)多而邊少的圖(也稱稀疏圖)，若用鄰接矩陣存儲(chǔ)，對(duì)應(yīng)的鄰接矩陣將是一個(gè)稀疏矩陣，存儲(chǔ)利用率很低。因此，頂點(diǎn)多而邊少的圖適于用鄰接表存儲(chǔ)。鄰接矩陣存儲(chǔ)的圖類Graph_Matrix鄰接表存儲(chǔ)的圖類Gra

17、ph_List2、 圖的實(shí)現(xiàn)1. 用鄰接矩陣存儲(chǔ)的圖類 Graph_Matrix類聲明const int MaxGraphSize = 256 ; / 圖的最大頂點(diǎn)個(gè)數(shù)const int MaxWeight = 1000 ; /邊的最大權(quán)值template class Graph_Matrix private: SLList VertexList ; /頂點(diǎn)表int edge MaxGraphSize MaxGraphSize ; /鄰接矩陣int graphsize ; /當(dāng)前頂點(diǎn)數(shù)public: /I. 構(gòu)造函數(shù)與析構(gòu)函數(shù)Graph_Matrix( ) ;Graph_Matrix( ) ;

18、 /II. 圖的維護(hù)函數(shù)int GraphEmpty(void) const /檢測(cè)圖是否為空int GraphFull(void) const ; /檢測(cè)圖是否已滿，即頂點(diǎn)個(gè)數(shù)是否越界int NumberOfVertices( void ) const ;/返回圖的頂點(diǎn)個(gè)數(shù)int NumberOfEdges( void ) const ; /返回圖的邊個(gè)數(shù) int GetWeight( const int v1, const int v2 ) ; / 返回指定邊的權(quán)值int* & GetNeighbors( const int v ) ;/ 返回頂點(diǎn)v的鄰接頂點(diǎn)表 int GetFirstN

19、eighbor( const int v ) ; / 返回序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號(hào) int GetNextNeighbor( const int v1, const int v2 ) ; /返回序號(hào)為v1的頂點(diǎn)相對(duì)于序號(hào)為v2的頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)的序號(hào)void InsertVertex( const int & v) ; / 向圖中插入一個(gè)頂點(diǎn)void InsertEdge( const int & v1, const int & v2, int weight ); /向圖中插入一條邊void DeleteVertex( const int & v ) ; /從圖中刪除一個(gè)頂點(diǎn)v

20、oid DeleteEdge( const int & v1, const int & v2 ) ; /從圖中刪除一條邊 / III. 圖的基本算法 void DepthFirstSearch( ) ;/圖的深度優(yōu)先搜索(遞歸) void DFS(const int v) ; /從頂點(diǎn)v開(kāi)始進(jìn)行圖的深度優(yōu)先搜索(迭代方法) void BFS( const int v ) ; /從頂點(diǎn)v開(kāi)始進(jìn)行圖的廣度優(yōu)先搜索 void TopoOrder( ) ; / 圖的拓?fù)渑判?void CriticalPath( ) ; / 輸出圖的關(guān)鍵路徑 void ShortestPath(const int v

21、) ; / 求無(wú)權(quán)圖中頂點(diǎn)v到其他頂點(diǎn)的最短路徑 void DShortestPath(const int v ) ; / 求正權(quán)圖中頂點(diǎn)v到其他頂點(diǎn)的最短路徑 void AllLength( ) ; / 求正權(quán)圖中每對(duì)頂點(diǎn)間的最短路徑 void Prim( ) ; / 構(gòu)造圖的最小支撐樹的普里姆算法 ;/ 構(gòu)造函數(shù), 創(chuàng)建一個(gè)圖Graph_Matrix : Graph_Matrix () cin graphsize;for( int i = 0 ; i graphsize ; i + ) for( int j = 0 ; j edgeij;0123 0 3 5 8 3 0 4 5 0 2 8

22、 4 2 00 1 2 3ADCB35284/ 取得序號(hào)為v的頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)的序號(hào)int Graph_Matrix :GetFirstNeighbor( const int v ) if (v = = -1) return -1; for( int i = 0 ; i 0 & edgevi MaxWeight) return i ; return -1 ; / 若v沒(méi)有鄰接頂點(diǎn)，則返回-10123 0 3 5 8 3 0 4 5 0 2 8 4 2 00 1 2 3ADCB35284/取得頂點(diǎn)v1相對(duì)于v2的下一個(gè)鄰接頂點(diǎn)的序號(hào)int Graph_Matrix :GetNextNeigh

23、bor( const int v1 , const int v2 ) if (v1 = = -1 | v2= = -1) return -1; for( int i = v2 + 1 ; i 0 & edgev1i MaxWeight)return i ; return -1 ; /若在v2之后沒(méi)有與v1鄰接的頂點(diǎn)，則返回-10123 0 3 5 8 3 0 4 5 0 2 8 4 2 00 1 2 3ADCB35284刪除頂點(diǎn)Vertex算法思想：不僅要從頂點(diǎn)表中刪除該頂點(diǎn)，還需要?jiǎng)h除該頂點(diǎn)所發(fā)出的邊以及所有的入邊，即在鄰接矩陣中刪除相應(yīng)的行和列。2. 用鄰接表存儲(chǔ)的圖類Graph_List

24、V0V3V2V1V0V1V2V3023112301203032. 用鄰接表存儲(chǔ)的圖類Graph_List/ 邊結(jié)點(diǎn)的結(jié)構(gòu)體struct Edge friend class Graph_List ; int VerAdj ; / 鄰接頂點(diǎn)序號(hào)，從0開(kāi)始編號(hào) int cost ; / 邊的權(quán)值 Edge *link ; / 指向下一個(gè)邊結(jié)點(diǎn)的指針 ;/ 頂點(diǎn)表中結(jié)點(diǎn)的結(jié)構(gòu)體struct Vertexfriend class Graph_List;int VerName;/ 頂點(diǎn)的名稱Edge *adjacent;/ 邊鏈表的頭指針/采用鄰接表存儲(chǔ)的Graph_List類定義class Graph_

25、List private:Vertex *Head; / 頂點(diǎn)表頭指針int graphsize; / 圖中當(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)int Graph_List: GetFirstNeighbor( const int v ) if ( v = = -1 ) return -1; Edge *p = Headv

26、.adjacent ; if (p != NULL) return pVerAdj ; else return -1;ADCBABCD02311230120303/ 求序號(hào)為v1的頂點(diǎn)相對(duì)于序號(hào)為v2的頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)的序號(hào)int Graph_List : GetNextNeighbor( const int v1 , const int v2 ) if ( v1 != -1 & v2 != -1 ) Edge *p = Headv1.adjacent ; while( pVerAdj != v2 & p!=NULL )/ 令p指向v2所在的邊結(jié)點(diǎn) p = plink ; if (p =

27、= NULL) return -1; p = p link ; /找v2的下一個(gè)邊結(jié)點(diǎn) if (p = = NULL) return -1; return p VerAdj ; return -1 ;ADCBABCD02311230120303 第五章 圖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)僅被訪問(wèn)一次，就叫做圖的遍歷 ( Graph Traversal )。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問(wèn)完某個(gè)頂

28、點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。為了避免重復(fù)訪問(wèn)，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問(wèn)過(guò)的輔助數(shù)組 visited ，它的初始狀態(tài)為 0，在圖的遍歷過(guò)程中，一旦某一個(gè)頂點(diǎn) i 被訪問(wèn)，就立即讓 visitedi 為 1，防止它被多次訪問(wèn)。5.3.1 深度優(yōu)先遍歷 深度優(yōu)先遍歷又被稱為深度優(yōu)先搜索 DFS ( Depth First Search ) 基本思想: DFS 在訪問(wèn)圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn) w1；再?gòu)?w1 出發(fā)，訪問(wèn)與 w1鄰接但還沒(méi)有訪問(wèn)過(guò)的頂點(diǎn) w2；然后再?gòu)?w2 出發(fā)，進(jìn)行類似的訪問(wèn)， 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)

29、過(guò)的頂點(diǎn) u 為止。接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。如果有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問(wèn)；如果沒(méi)有，就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。深度優(yōu)先搜索DFS ( Depth First Search )深度優(yōu)先搜索的示例1. 遞歸算法算法DepthFirstSearch (v, visited)/* 圖的深度優(yōu)先遍歷的遞歸算法*/DFSearch1初始化 PRINT(v).visitedv 1. p adjacent(Headv) .DFSearch2深度優(yōu)先遍歷圖WHILE pDO( I

30、F visitedVerAdj(p)1 THEN DepthFirstSearch (VerAdj(p), visited) . p link(p) . )算法 DFS_Main( ) visited = new intgraphsize ;/ 為輔助數(shù)組申請(qǐng)空間 for( int k = 0 ; k graphsize ; k + + )visitedk = 0 ; / 數(shù)組初始化 / 從序號(hào)為0的頂點(diǎn)出發(fā)，深度優(yōu)先遍歷圖 DepthFirstSearch( 0 , visited ) ; delete visited ; / 釋放輔助數(shù)組空間DFSearch1初始化 PRINT(v). v

31、isitedv 1. p adjacent(Headv) .DFSearch2深度優(yōu)先遍歷圖 WHILE p DO ( IF visitedVerAdj(p)1 THEN DepthFirstSearch (VerAdj(p), visited) . p link(p) . )V1V2V4V3V8V7V6V51234051717262534V1V2V3V4V5V6V7V86001234567V1V2V4V3V8V7V6V5V1V2V4V3V8V7V6V51234051717262534V1V2V3V4V5V6V7V86001234567 可以利用堆棧實(shí)現(xiàn)深度優(yōu)先遍歷的非遞歸算法。 堆棧中存放已

32、訪問(wèn)結(jié)點(diǎn)的未被訪問(wèn)的鄰接頂點(diǎn)，每次彈出棧頂元素時(shí)，如其未被訪問(wèn)，則訪問(wèn)該頂點(diǎn)，并檢查當(dāng)前頂點(diǎn)的邊鏈表，將其未被訪問(wèn)的鄰接頂點(diǎn)入棧，循環(huán)進(jìn)行。2. 迭代算法 首先將所有頂點(diǎn)的visited值置為0, 初始頂點(diǎn)壓入堆棧； 檢測(cè)堆棧是否為空。若堆棧為空，則迭代結(jié) 束；否則，從棧頂彈出一個(gè)頂點(diǎn)v； 如果v未被訪問(wèn)過(guò)，則訪問(wèn)v，將visitedv值更新為1，然后根據(jù)v的鄰接頂點(diǎn)表，將v的未被訪問(wèn)的鄰接頂點(diǎn)壓入棧，執(zhí)行步驟 。A0243156BCDEFG162345054ACGBFED算法DFS (Head, v , visited. visited)/* 圖的深度優(yōu)先遍歷的非遞歸算法*/DFS1初始化

33、CREATS(S) . /*創(chuàng)建堆棧 S */ FOR i = 1 TO n DO visitedi 0. S v. /* 將v壓入棧中 */DFS2利用堆棧S深度優(yōu)先遍歷圖 WHILE NOT(ISEMTS(S) DO /* 當(dāng)S不空時(shí) */( v S. /*彈出堆棧頂元素 */ IF visitedv = 0 THEN ( PRINT(v) . visitedv 1. p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN S VerAdj(p) . p link(p). ) ) )算法分析圖中有 n 個(gè)頂點(diǎn)，e 條邊。如

34、果用鄰接表表示圖，沿頂點(diǎn)的adjacent可以找到某個(gè)頂點(diǎn)v 的所有鄰接頂點(diǎn)w。由于總共有2e 個(gè)邊結(jié)點(diǎn)，所以掃描邊的時(shí)間為O(e)。而且對(duì)所有頂點(diǎn)遞歸訪問(wèn)1次，所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為O(n2)。ACGBFED非連通圖需要多次調(diào)用深度優(yōu)先遍歷算法For i=0 to n-1 DOvisitedi 0.For j=0 to n-1 DOIF visitedj=0 THENDepthFirstSearch (vj, visited)V1V2V35.3.2 廣度優(yōu)先遍歷 基本思想：首

35、先訪問(wèn)初始點(diǎn)頂點(diǎn)v0，之后依次訪問(wèn)與v0鄰接的全部頂點(diǎn)w1，w2，.，wk。然后，再順次訪問(wèn)與w1，w2，.，wk鄰接的尚未訪問(wèn)的全部頂點(diǎn)，再?gòu)倪@些被訪問(wèn)過(guò)的頂點(diǎn)出發(fā)，逐個(gè)訪問(wèn)與它們鄰接的尚未訪問(wèn)過(guò)的全部頂點(diǎn)。依此類推，直到連通圖中的所有頂點(diǎn)全部訪問(wèn)完為止。廣度優(yōu)先搜索BFS ( Breadth First Search )廣度優(yōu)先搜索的示例 廣度優(yōu)先搜索過(guò)程 廣度優(yōu)先生成樹廣度優(yōu)先搜索類似于樹的層次遍歷，是一種分層的搜索過(guò)程，每向前走一步可能訪問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程，其算法也不是遞歸的。為了實(shí)現(xiàn)逐層訪問(wèn)，算法中使用一個(gè)隊(duì)列，以便于向

36、下一層訪問(wèn)。與深度優(yōu)先搜索過(guò)程一樣，為避免重復(fù)訪問(wèn)，需要一個(gè)輔助數(shù)組visited 。算法BFS (Head, v, visited. visited) /*廣度優(yōu)先遍歷算法 */BFS1初始化 CREATQ(Q). /*創(chuàng)建隊(duì)列 Q */ FOR i = 1 TO n DO visitedi 0. PRINT(v) . visitedv 1. Qv. /* 入隊(duì) */BFS2廣度優(yōu)先遍歷 WHILE NOT(ISEMTQ(Q) DO /* 當(dāng)隊(duì)列不空時(shí) */ ( v Q. /* 出隊(duì) */ p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p

37、) = 0 THEN( Q VerAdj(p) . PRINT(VerAdj(p) ) . visitedVerAdj(p) 1. ) . p link(p). ) ) WHILE NOT(ISEMTQ(Q) DO /* 當(dāng)隊(duì)列不空時(shí) */ ( v Q. /* 出隊(duì) */ p adjacent(Headv) . WHILE p DO( IF visitedVerAdj(p) = 0 THEN ( Q VerAdj(p) . PRINT(VerAdj(p) ) . visitedVerAdj(p) 1. ) p link(p). ) ) 01234567024315670123457612043

38、065172727364517算法分析如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為 d0 + d1 + + dn-1 = O(e)，其中的 di 是頂點(diǎn) i 的度?？偟臅r(shí)間復(fù)雜度為O(n+e)。如果使用鄰接矩陣，則對(duì)于每一個(gè)被訪問(wèn)的頂點(diǎn)，循環(huán)要檢測(cè)矩陣中的 n 個(gè)元素，總的時(shí)間代價(jià)為O(n2)。定理5.1 設(shè)圖G = (V, E), V = 1, 2, , n, 頂點(diǎn)s V. 令 (這里假定 ) , 則算法DFS(或BFS) 運(yùn)行結(jié)束后有：圖的深度優(yōu)先樹的先根遍歷回溯法（試探法）圖的廣度優(yōu)先樹的層次遍歷分支限界法 進(jìn)行問(wèn)題搜索時(shí)，哪種方法更好？ 深度優(yōu)先 優(yōu)點(diǎn)：存儲(chǔ)空間少； 缺點(diǎn)：會(huì)面臨“鉆牛角

39、尖”的問(wèn)題，有時(shí)找不到解； 寬度優(yōu)先 優(yōu)點(diǎn)：只要存在解，則一定能找到； 缺點(diǎn)：經(jīng)常會(huì)面臨組合爆炸問(wèn)題。例： n-皇后問(wèn)題在國(guó)際象棋中，最強(qiáng)大的棋子是皇后，因?yàn)樗芄羲谛?、所在列?nèi)或沿對(duì)角方向的任何一個(gè)棋子。n-皇后問(wèn)題要求在棋盤上放置n個(gè)皇后，使得沒(méi)有哪個(gè)皇后能攻擊其他的皇后。 （X1, X2, , Xn)算法NQUEENS( k)/*此算法使用遞歸算法求出在一個(gè)nn的棋盤上放置n個(gè)皇后，使其不能互相攻擊的所有可能位置 */NQUEENS1 FOR i = 1 TO n DO ( PLACE(k,i. canPlace). /*此處能放這個(gè)皇后嗎*/ IF canPlace = true

40、 THEN /*能放置*/ ( queenInRowki. IF k= n THEN PRINT(queenInRow). /*找到一個(gè)解，打印*/ ELSE NQUEENS(k+1). /*考慮下一個(gè)皇后*/ ) ) 第五章 圖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ù)渑判?計(jì)劃、施工過(guò)程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。AOV網(wǎng):在有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)之間的先后

41、關(guān)系，稱這樣的有向圖為AOV網(wǎng)(Activity On Vertex Network)。例如，計(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é) 無(wú) C1 程序設(shè)計(jì)基礎(chǔ) 無(wú) C2 離散數(shù)學(xué) C0,C1 C3 數(shù)據(jù)結(jié)構(gòu) C2,C4 C4 程序設(shè)計(jì)語(yǔ)言 C1 C5 編譯技術(shù) C3,C4 C6 操作系統(tǒng) C3,C8 C7 普通物理 C0 C8 計(jì)算機(jī)原理 C7 C0C2C3C5C4C1C

42、7C6C8在AOV網(wǎng)絡(luò)中，如果活動(dòng)Vi 必須在活動(dòng)Vj 之前進(jìn)行，則存在有向邊， AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)絡(luò)中如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。因此，對(duì)給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。拓?fù)湫蛄校喊袮OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列，使每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前邊。拓?fù)渑判颍簶?gòu)造AOV網(wǎng)的拓?fù)湫蛄械倪^(guò)程被稱為拓?fù)渑判?。拓?fù)湫蛄校篊0 , C1 , C2 , C4 , C3 , C5 , C7 , C8 , C6C0C2C3C5C4C1C7C6C8 拓?fù)渑判蚧静襟E： 從網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)且輸出之。 從網(wǎng)中刪除該頂

43、點(diǎn)及其所有出邊。執(zhí)行 ，直至所有頂點(diǎn)已輸出，或網(wǎng)中剩余頂點(diǎn)入度均不為0 (說(shuō)明網(wǎng)中存在回路，無(wú)法繼續(xù)拓?fù)渑判?C0C2C3C5C4C1C7C6C8 回路與拓?fù)渑判蛉魏螣o(wú)回路的AOV網(wǎng)，其頂點(diǎn)均可排成拓?fù)湫蛄?其拓?fù)湫蛄胁灰欢ㄎㄒ?；如果能將AOV網(wǎng)的所有頂點(diǎn)都排入一個(gè)拓?fù)湫蛄?，則該AOV網(wǎng)中必定無(wú)有向環(huán)；如果得不到所有頂點(diǎn)的拓?fù)湫蛄校瑒t說(shuō)明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 ，counti

44、的元素值取對(duì)應(yīng)頂點(diǎn)i的入度；建立一個(gè)堆棧，棧中存放入度為0的頂點(diǎn)，每當(dāng)一個(gè)頂點(diǎn)的入度為0，就將其壓入棧。拓?fù)渑判蛩惴?25140002123013425count02431524235355用一個(gè)堆棧存放入度為 0 的頂點(diǎn)。虛擬的堆棧利用變量top和count數(shù)組元素的值來(lái)模擬堆棧的壓入和彈出。 top:“棧頂”位置，初始為-1counttop：次棧頂元素入棧：counti = top; top = i;出棧：j = top; top = counttop;算法TopoOrder(n) /* 圖的拓?fù)渑判蛩惴?*/TOrder1初始化 /* 計(jì)算count數(shù)組 */ FOR i = 0 TO

45、n-1 DO counti 0. FOR i = 0 TO n-1 DO ( p adjacent( Headi ) . WHILE p DO (countVerAdj(p) countVerAdj(p)+1. p link (p). ) )325140002123013425count拓?fù)渑判蛩惴ǎ?top -1./棧頂指針top FOR i = 0 TO n-1 DO/將入度為0的頂點(diǎn)入棧IF counti = 0 THEN ( counti top. top i. )top102123013425count325140102123013425counttop1拓?fù)渑判蛩惴ǎ?top -1

46、./棧頂指針top FOR i = 0 TO n-1 DO/將入度為0的頂點(diǎn)入棧IF counti = 0 THEN ( counti top. top i. )325140TOrder2拓?fù)渑判?FOR i = 1 TO n DO IF top = - 1 THEN / 若循環(huán)體尚未被執(zhí)行n次，棧頂指針已為-1 (PRINT “有回路! ”. RETURN. ) /說(shuō)明有回路，終止程序 ELSE ( j top. top counttop . /* 彈出棧頂j */ PRINT ( j ) . p adjacent( Headj ) . / 掃描j的邊鏈表 WHILE p DO ( k VerAdj(p) . countk countk-1. / 頂點(diǎn)k的入度減1 IF countk = 0 THEN /若入度為0，則k入棧 (countk top. top k.) p link (p). ) ) j top. top counttop .