1、第五章 圖圖（Graph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，對結(jié)點（圖中常稱為頂點）的前趨和后繼個數(shù)不加限制，即結(jié)點之間的關(guān)系是任意的。圖中任意兩個結(jié)點之間都可能相關(guān)。圖狀結(jié)構(gòu)可以描述各種復(fù)雜的數(shù)據(jù)對象。圖的應(yīng)用極為廣泛，特別是近年來的迅速發(fā)展，已經(jīng)滲透到諸如語言學、邏輯學、物理、化學、電訊工程、計算機科學以及數(shù)學的其它分支中。 圖的出現(xiàn)最早可以追溯到1736年，著名的數(shù)學家歐拉使用它解決了經(jīng)典的柯尼斯堡七橋難題。從此，有關(guān)圖的理論形成了一個專門的數(shù)學分支圖論?？履崴贡な?8世紀初普魯士的一個小鎮(zhèn)，普雷格爾河流經(jīng)此鎮(zhèn)，共有7座橋橫跨河上，把全鎮(zhèn)連接起來。當時當?shù)鼐用駸嶂杂谝豁?/p>

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

3、絡(luò)。 城市航線網(wǎng)天津北京上海廣州深圳計算機網(wǎng)絡(luò)computerconnection 不一定具有一個根結(jié)點 沒有明顯的父子關(guān)系 從一個頂點到另一個頂點可能有多個（或0個）路徑圖 VS. 樹 第五章 圖5.1 基本概念5.2 圖的存儲結(jié)構(gòu)5.3 圖的遍歷5.4 拓撲排序5.5 關(guān)鍵路徑 5.6 最短路徑5.7 最小支撐樹5.8 圖的應(yīng)用定義5.1：圖G由兩個集合V和E組成，記為G=(V, E)；其中 V 是頂點的有限集合，E 是連接 V 中兩個不同頂點的邊的有限集合。通常，也將圖G的頂點集和邊集分別記為V(G)和E(G)。 如果E中的頂點對是有序的，即E中的每條邊都是有方向的，則稱G為有向圖。如果

4、頂點對是無序?qū)?，則稱G是無向圖。 5.1 圖的基本概念定義5.2 若G = (V, E)是有向圖，則它的一條有向邊是由V中兩個頂點構(gòu)成的有序?qū)?，亦稱為弧，記為，其中w是邊的始點，又稱弧尾；v是邊的終點，又稱弧頭。有向圖G=（V，E）V= v1，v2，v3，v4E=,v1v3v2v4無向圖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和v之間存在一條邊(w, v)，則稱w, v是相鄰的，二者互為鄰接頂點

5、。在有向圖中，若存在一條邊，則稱頂點w鄰接到頂點v，頂點v鄰接自頂點w.v3v4v1v2oooov1v2v3v4定義5.4 由于E是邊的集合，故一個圖中不會多次出現(xiàn)一條邊。若去掉此限制，則由此產(chǎn)生的結(jié)構(gòu)稱為多重圖。圖 (c)就是一個多重圖。 (a) (b) (c)很多問題都可以抽象成一個圖結(jié)構(gòu)，考慮如下三個例子：將電影界的所有演員構(gòu)成頂點集V，其中兩位演員u和v如果共同出演過至少一部影片，那么在u和v之間連接一條邊。演員之間的這種合作關(guān)系看作對等關(guān)系。按照這種方式建立的圖是無向圖。將C+程序中所有的類構(gòu)成頂點集V，且如果類a是類b的子類，則定義一條從b指向a的有向邊。按照這種方式建立的圖是有向

6、圖。將多個城市構(gòu)成頂點集V，如果城市a和城市b之間有一條高速公路，則在a和b之間連接一條邊。允許在兩個城市之間修建多條高速公路。按照這種方式建立的圖是多重圖。定義5.5 設(shè)G是無向圖，vV(G)，E(G)中以v為端點的邊的個數(shù)，稱為頂點的度。若G是有向圖，則v的出度是以v為始點的邊的個數(shù)，v的入度是以v為終點的邊的個數(shù)。有向圖中，以某頂點為弧頭的弧的數(shù)目稱為該頂點的入度。以某頂點為弧尾的弧的數(shù)目稱為該頂點的出度。 頂點的度=入度+出度。度: D(v)入度: ID(v)出度: OD(v)D(v)=ID(v)+OD(v)Graph2V5V1V2V3V4V4V3V2V1Graph1設(shè)圖G(可以為有向

7、或無向圖)共有n個頂點， e條邊，若頂點vi的度數(shù)為D(vi)，則因為一條邊關(guān)聯(lián)兩個頂點，而且使得這兩個頂點的度數(shù)分別增加1。因此頂點的度數(shù)之和就是邊的兩倍。定義5.6 設(shè)G是圖，若存在一個頂點序列 使得 或 屬于E(G)，則稱vp到vq存在一條路徑，其中vp 稱為起點，vq稱為終點。 路徑的長度是該路徑上邊的個數(shù)。如果一條路徑上除了起點和終點可以相同外，再不能有相同的頂點，則稱此路徑為簡單路徑。如果一條簡單路徑的起點和終點相同，且路徑長度大于等于2，則稱之為簡單回路。圖(a)中，v1到v3之間存在一條路徑v1, v2, v5, v4, v3，同時這也是一條簡單路徑；v1, v2, v5, v

8、4, v3, v1是一條簡單回路。 (a) (b) (c)V5V4V2V1V3V1V2V3V4路徑：v1 v3 v4 v3 v5簡單路徑：v1 v3 v5簡單回路：v1 v2 v3 v1路徑：v1 v3 v2 v4 v3 v2簡單路徑：v1 v3 v2簡單回路：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、在一條從頂點vi到頂點vj的路徑，則稱vi與vj可及(連通)。若G為無向圖，且V(G)中任意兩頂點都可及，則稱G為連通圖。若G為有向圖，且對于V(G)中任意兩個頂點vi和vj ， vi與vj可及， vj與vi也可及，則稱G為強連通圖。也可以定義“弱連通圖”的概念，即在任何頂點u和v之間，至少存在一條從u到v的路徑或者存在一條從v到u的路徑。V5V4V2V1V3V1V2V3V4定義5.9 設(shè)圖G = (V，E)是無向（或有向）圖，若G的子圖GK是一個（強）連通圖，則稱GK 為G的（強）連通子圖。定義5.10 對于G的一個連通子圖GK，如果不存在G的另一個連通子圖G，使得V(GK)V(G)，則稱G

10、K為G的連通分量。 (a) (b) (c) (d) (e) 一個圖的連通子圖e是a的連通分量連通分量V4V3V1V2V4V3V2V1連通分量BAEJKGLMDIFCHALJCFBMDEKIHG有時候，圖不僅要表示出元素之間是否存在某種關(guān)系，同時還需要表示與這一關(guān)系相關(guān)的某些信息。例如在計算機網(wǎng)絡(luò)對應(yīng)的圖中，頂點表示計算機，頂點之間的邊表示計算機之間的通訊鏈路。實際中，為了管理計算機網(wǎng)絡(luò)，我們需要這個圖包含更多的信息，例如每條通訊鏈路的物理長度、成本和帶寬等信息。為此，我們?yōu)閭鹘y(tǒng)圖中的每條邊添加相應(yīng)的數(shù)據(jù)域以記錄所需要的信息。定義5.11 設(shè)G = (V, E)是圖，若對圖中的任意一條邊l，都有

11、實數(shù)w(l)與其對應(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)路徑 的長度或權(quán)重。權(quán)通常用來表示從一個頂點到另一個頂點的距離或費用。V1V2V3V42357 無向圖 有向圖 端點 弧 弧頭 弧尾 相鄰的 鄰接到 鄰接自 度 出度 入度 連通圖 強連通圖 第五章 圖5.1 基本概念5.2 圖的存儲結(jié)構(gòu)5.3 圖的遍歷5.4 拓撲排序5.5 關(guān)鍵路徑 5.6 最短路徑5.7 最小支撐樹5

12、.8 圖的應(yīng)用鄰接矩陣 鄰接表(逆鄰接表)1、 圖的存儲結(jié)構(gòu)用順序方式或鏈接方式存儲圖的頂點表v0,v1,vn-1 ,圖的邊用nn階矩陣A =(aij)表示，A的定義如下：（a）若圖為權(quán)圖，aij對應(yīng)邊的權(quán)值；（b）若圖為非權(quán)圖，則（1） aii=0；（2） aij=1，當ij且或(vi,vj)存在時； （3）aij=0，當ij且或(vi,vj)不存在時。稱矩陣A為圖的鄰接矩陣。1、鄰接矩陣例1無向圖的鄰接矩陣無向圖的鄰接矩陣是對稱陣。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特點：無向圖的鄰接矩陣對稱，可壓縮存儲，有n個頂點的無向圖需存儲空間為n(n+1)/2有向圖鄰接矩陣不一定對稱，有n個頂點的有向圖需存儲空間為n 借助鄰接矩陣，可以很容易地求出圖中頂點的度。無向圖 鄰接矩陣的第i行（或第i列）的非零元素的個數(shù)是頂點Vi的度。有向圖 鄰接矩陣第i行的非零元素的個數(shù)為頂點Vi的出度；第i列的非零元素的個數(shù)為頂點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、鄰接表鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。對圖的每個頂點建立一個單鏈表（n個頂點建立n個單鏈表），第i個單鏈表中的結(jié)點包含頂點Vi的所有鄰接頂點。由順序存儲的頂點表和鏈接存儲的邊鏈表構(gòu)成的圖的存儲結(jié)構(gòu)被稱為鄰接表。 V0V3V2V1V0V1V2V302311230120303頂點的結(jié)構(gòu) 非權(quán)圖中邊結(jié)點結(jié)構(gòu)為（VerAdj,link）權(quán)圖中邊結(jié)點結(jié)構(gòu)為（VerAdj,cost,link）

15、VerName adjacentVerAdj cost linkVerAdj link 例1無向圖的鄰接表V0V3V2V1V0V1V2V302311230120303例2有向圖的鄰接表V0V1V2V3V4024311300413V0V3V4V1V2對于用鄰接表存儲的有向圖，每條邊只對應(yīng)一個邊結(jié)點；而對于用鄰接表存儲的無向圖，每條邊則對應(yīng)兩個邊結(jié)點。根據(jù)鄰接表，可以統(tǒng)計出有向圖中每個頂點的出度。但是，如果要統(tǒng)計頂點的入度，每統(tǒng)計一個頂點，就要遍歷所有的邊結(jié)點，其時間復(fù)雜度為O(e)(e為圖中邊的個數(shù))，從而統(tǒng)計所有頂點入度的時間復(fù)雜度為O(ne)(n為圖的頂點個數(shù))。建立逆鄰接表(頂點的指向關(guān)系

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

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

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

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

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

21、) ; / 求無權(quán)圖中頂點v到其他頂點的最短路徑 void DShortestPath(const int v ) ; / 求正權(quán)圖中頂點v到其他頂點的最短路徑 void AllLength( ) ; / 求正權(quán)圖中每對頂點間的最短路徑 void Prim( ) ; / 構(gòu)造圖的最小支撐樹的普里姆算法 ;/ 構(gòu)造函數(shù), 創(chuàng)建一個圖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/ 取得序號為v的頂點的第一個鄰接頂點的序號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沒有鄰接頂點，則返回-10123 0 3 5 8 3 0 4 5 0 2 8 4 2 00 1 2 3ADCB35284/取得頂點v1相對于v2的下一個鄰接頂點的序號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之后沒有與v1鄰接的頂點，則返回-10123 0 3 5 8 3 0 4 5 0 2 8 4 2 00 1 2 3ADCB35284刪除頂點Vertex算法思想：不僅要從頂點表中刪除該頂點，還需要刪除該頂點所發(fā)出的邊以及所有的入邊，即在鄰接矩陣中刪除相應(yīng)的行和列。2. 用鄰接表存儲的圖類Graph_List

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

25、List private:Vertex *Head; / 頂點表頭指針int graphsize; / 圖中當前頂點的個數(shù) public:/ I. 圖的構(gòu)造函數(shù)和析構(gòu)函數(shù)Graph_List ( ); Graph_List ( );/ II. 圖的維護函數(shù)與Graph_Matrix類中的維護函數(shù)相同。/ III. 圖的基本算法與Graph_Matrix類中的基本算法相同。 ;/ 求序號為v的頂點的第一個鄰接頂點的序號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/ 求序號為v1的頂點相對于序號為v2的頂點的下一個鄰接頂點的序號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é)點 p = plink ; if (p =

27、= NULL) return -1; p = p link ; /找v2的下一個邊結(jié)點 if (p = = NULL) return -1; return p VerAdj ; return -1 ;ADCBABCD02311230120303 第五章 圖5.1 基本概念5.2 圖的存儲結(jié)構(gòu)5.3 圖的遍歷5.4 拓撲排序5.5 關(guān)鍵路徑 5.6 最短路徑5.7 最小支撐樹5.8 圖的應(yīng)用從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷 ( Graph Traversal )。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂

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

29、過的頂點 u 為止。接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。深度優(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ù)組申請空間 for( int k = 0 ; k graphsize ; k + + )visitedk = 0 ; / 數(shù)組初始化 / 從序號為0的頂點出發(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 可以利用堆棧實現(xiàn)深度優(yōu)先遍歷的非遞歸算法。 堆棧中存放已

32、訪問結(jié)點的未被訪問的鄰接頂點，每次彈出棧頂元素時，如其未被訪問，則訪問該頂點，并檢查當前頂點的邊鏈表，將其未被訪問的鄰接頂點入棧，循環(huán)進行。2. 迭代算法 首先將所有頂點的visited值置為0, 初始頂點壓入堆棧； 檢測堆棧是否為空。若堆棧為空，則迭代結(jié) 束；否則，從棧頂彈出一個頂點v； 如果v未被訪問過，則訪問v，將visitedv值更新為1，然后根據(jù)v的鄰接頂點表，將v的未被訪問的鄰接頂點壓入棧，執(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 /* 當S不空時 */( 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 個頂點，e 條邊。如

34、果用鄰接表表示圖，沿頂點的adjacent可以找到某個頂點v 的所有鄰接頂點w。由于總共有2e 個邊結(jié)點，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為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、先訪問初始點頂點v0，之后依次訪問與v0鄰接的全部頂點w1，w2，.，wk。然后，再順次訪問與w1，w2，.，wk鄰接的尚未訪問的全部頂點，再從這些被訪問過的頂點出發(fā)，逐個訪問與它們鄰接的尚未訪問過的全部頂點。依此類推，直到連通圖中的所有頂點全部訪問完為止。廣度優(yōu)先搜索BFS ( Breadth First Search )廣度優(yōu)先搜索的示例 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先搜索類似于樹的層次遍歷，是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。為了實現(xiàn)逐層訪問，算法中使用一個隊列，以便于向

36、下一層訪問。與深度優(yōu)先搜索過程一樣，為避免重復(fù)訪問，需要一個輔助數(shù)組visited 。算法BFS (Head, v, visited. visited) /*廣度優(yōu)先遍歷算法 */BFS1初始化 CREATQ(Q). /*創(chuàng)建隊列 Q */ FOR i = 1 TO n DO visitedi 0. PRINT(v) . visitedv 1. Qv. /* 入隊 */BFS2廣度優(yōu)先遍歷 WHILE NOT(ISEMTQ(Q) DO /* 當隊列不空時 */ ( v Q. /* 出隊 */ 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 /* 當隊列不空時 */ ( v Q. /* 出隊 */ 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)的總時間代價為 d0 + d1 + + dn-1 = O(e)，其中的 di 是頂點 i 的度?？偟臅r間復(fù)雜度為O(n+e)。如果使用鄰接矩陣，則對于每一個被訪問的頂點，循環(huán)要檢測矩陣中的 n 個元素，總的時間代價為O(n2)。定理5.1 設(shè)圖G = (V, E), V = 1, 2, , n, 頂點s V. 令 (這里假定 ) , 則算法DFS(或BFS) 運行結(jié)束后有：圖的深度優(yōu)先樹的先根遍歷回溯法（試探法）圖的廣度優(yōu)先樹的層次遍歷分支限界法 進行問題搜索時，哪種方法更好？ 深度優(yōu)先 優(yōu)點：存儲空間少； 缺點：會面臨“鉆牛角

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

40、 THEN /*能放置*/ ( queenInRowki. IF k= n THEN PRINT(queenInRow). /*找到一個解，打印*/ ELSE NQUEENS(k+1). /*考慮下一個皇后*/ ) ) 第五章 圖5.1 基本概念5.2 圖的存儲結(jié)構(gòu)5.3 圖的遍歷5.4 拓撲排序5.5 關(guān)鍵路徑 5.6 最短路徑5.7 最小支撐樹5.8 圖的應(yīng)用 5.4 拓撲排序 計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。AOV網(wǎng):在有向圖中，用頂點表示活動，用有向邊表示活動之間的先后

41、關(guān)系，稱這樣的有向圖為AOV網(wǎng)(Activity On Vertex Network)。例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學習。 例按拓撲次序安排計算機專業(yè)必修課程計算機專業(yè)必修課程課程代號 課程名稱 先修課程 C0 高等數(shù)學 無 C1 程序設(shè)計基礎(chǔ) 無 C2 離散數(shù)學 C0,C1 C3 數(shù)據(jù)結(jié)構(gòu) C2,C4 C4 程序設(shè)計語言 C1 C5 編譯技術(shù) C3,C4 C6 操作系統(tǒng) C3,C8 C7 普通物理 C0 C8 計算機原理 C7 C0C2C3C5C4C1C

42、7C6C8在AOV網(wǎng)絡(luò)中，如果活動Vi 必須在活動Vj 之前進行，則存在有向邊， AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)絡(luò)中如果出現(xiàn)了有向環(huán)，則意味著某項活動應(yīng)以自己作為先決條件。因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。拓撲序列：把AOV網(wǎng)中的所有頂點排成一個線性序列，使每個活動的所有前驅(qū)活動都排在該活動的前邊。拓撲排序：構(gòu)造AOV網(wǎng)的拓撲序列的過程被稱為拓撲排序。拓撲序列：C0 , C1 , C2 , C4 , C3 , C5 , C7 , C8 , C6C0C2C3C5C4C1C7C6C8 拓撲排序基本步驟： 從網(wǎng)中選擇一個入度為0的頂點且輸出之。 從網(wǎng)中刪除該頂

43、點及其所有出邊。執(zhí)行 ，直至所有頂點已輸出，或網(wǎng)中剩余頂點入度均不為0 (說明網(wǎng)中存在回路，無法繼續(xù)拓撲排序)C0C2C3C5C4C1C7C6C8 回路與拓撲排序任何無回路的AOV網(wǎng)，其頂點均可排成拓撲序列(其拓撲序列不一定唯一)；如果能將AOV網(wǎng)的所有頂點都排入一個拓撲序列，則該AOV網(wǎng)中必定無有向環(huán)；如果得不到所有頂點的拓撲序列，則說明AOV網(wǎng)中存在有向環(huán)(AOV網(wǎng)所代表的工程是不可行的)。存在回路的AOV網(wǎng)，找不到所有頂點的拓撲序列。因此，可以用拓撲排序判斷有向圖中是否有回路假定AOV網(wǎng)用鄰接表的形式存儲。為實現(xiàn)拓撲排序算法，事先需做好兩項準備工作：建立一個數(shù)組count ，counti

44、的元素值取對應(yīng)頂點i的入度；建立一個堆棧，棧中存放入度為0的頂點，每當一個頂點的入度為0，就將其壓入棧。拓撲排序算法325140002123013425count02431524235355用一個堆棧存放入度為 0 的頂點。虛擬的堆棧利用變量top和count數(shù)組元素的值來模擬堆棧的壓入和彈出。 top:“棧頂”位置，初始為-1counttop：次棧頂元素入棧：counti = top; top = i;出棧：j = top; top = counttop;算法TopoOrder(n) /* 圖的拓撲排序算法 */TOrder1初始化 /* 計算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拓撲排序算法： top -1./棧頂指針top FOR i = 0 TO n-1 DO/將入度為0的頂點入棧IF counti = 0 THEN ( counti top. top i. )top102123013425count325140102123013425counttop1拓撲排序算法： top -1

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