數(shù)據(jù)結(jié)構(gòu)課件：第5章 圖1

1、第五章 圖圖（Graph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，對結(jié)點(diǎn)（圖中常稱為頂點(diǎn)）的前趨和后繼個數(shù)不加限制，即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個結(jié)點(diǎn)之間都可能相關(guān)。圖狀結(jié)構(gòu)可以描述各種復(fù)雜的數(shù)據(jù)對象。圖的應(yīng)用極為廣泛，特別是近年來的迅速發(fā)展，已經(jīng)滲透到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。 圖狀結(jié)構(gòu)的實(shí)際背景 在城市之間建立通訊網(wǎng)絡(luò)，使得其中的任意兩個城市之間有直接或間接的通訊線路，假設(shè)已知每對城市之間通訊線路的造價，要求找出一個造價最低的通訊網(wǎng)絡(luò)。 城市航線網(wǎng)天津北京上海廣州深圳計(jì)算機(jī)網(wǎng)絡(luò)computerconnection 第五章

2、圖5.1 基本概念5.2 圖的存儲結(jié)構(gòu)5.3 圖的遍歷5.4 拓?fù)渑判?.5 關(guān)鍵路徑 5.6 最短路徑5.7 最小支撐樹定義5.1：圖G由兩個集合V和E組成，記為G=(V, E)；其中 V 是頂點(diǎn)的有限集合，E 是連接 V 中兩個不同頂點(diǎn)的邊的有限集合。通常，也將圖G的頂點(diǎn)集和邊集分別記為V(G)和E(G)。 如果E中的頂點(diǎn)對是有序的，即E中的每條邊都是有方向的，則稱G為有向圖。如果頂點(diǎn)對是無序?qū)?，則稱G是無向圖。 5.1 圖的基本概念定義5.2 若G = (V, E)是有向圖，則它的一條有向邊是由V中兩個頂點(diǎn)構(gòu)成的有序?qū)?，亦稱為弧，記為，其中w是邊的始點(diǎn)，又稱弧尾；v是邊的終點(diǎn)，又稱弧頭。

3、有向圖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 在無向圖中，若兩個頂點(diǎn)w和v之間存在一條邊(w, v)，則稱w, v是相鄰的，二者互為鄰接頂點(diǎn)。在有向圖中，若存在一條邊，則稱頂點(diǎn)w鄰接到頂點(diǎn)v，頂點(diǎn)v鄰接自頂點(diǎn)w.v3v4v1v2oooov1v2v3v4定義5.4 由于E是邊的集合，故一個圖中不會多次出現(xiàn)一條邊。若去掉此限制，則由此產(chǎn)生的結(jié)構(gòu)稱為多重圖

4、。圖 (c)就是一個多重圖。 (a) (b) (c)定義5.5 設(shè)G是無向圖，vV(G)，E(G)中以v為端點(diǎn)的邊的個數(shù)，稱為頂點(diǎn)的度。若G是有向圖，則v的出度是以v為始點(diǎn)的邊的個數(shù)，v的入度是以v為終點(diǎn)的邊的個數(shù)。有向圖中，以某頂點(diǎn)為弧頭的弧的數(shù)目稱為該頂點(diǎn)的入度。以某頂點(diǎn)為弧尾的弧的數(shù)目稱為該頂點(diǎn)的出度。 頂點(diǎn)的度=入度+出度。設(shè)圖G(可以為有向或無向圖)共有n個頂點(diǎn)， e條邊，若頂點(diǎn)vi的度數(shù)為D(vi)，則因?yàn)橐粭l邊關(guān)聯(lián)兩個頂點(diǎn)，而且使得這兩個頂點(diǎn)的度數(shù)分別增加1。因此頂點(diǎn)的度數(shù)之和就是邊的兩倍。定義5.6 設(shè)G是圖，若存在一個頂點(diǎn)序列 使得 或 屬于E(G)，則稱vp到vq存在一條路

5、徑，其中vp 稱為起點(diǎn)，vq稱為終點(diǎn)。 路徑的長度是該路徑上邊的個數(shù)。如果一條路徑上除了起點(diǎn)和終點(diǎn)可以相同外，再不能有相同的頂點(diǎn)，則稱此路徑為簡單路徑。如果一條簡單路徑的起點(diǎn)和終點(diǎn)相同，且路徑長度大于等于2，則稱之為簡單回路。圖(a)中，v1到v3之間存在一條路徑v1, v2, v5, v4, v3，同時這也是一條簡單路徑；v1, v2, v5, v4, 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

6、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完全圖 ：有向完全圖(邊數(shù)n*(n-1) 無向完全圖(邊數(shù)1/2*n*(n-1) 定義5.8 設(shè)G是圖，若存在一條從頂點(diǎn)vi到頂點(diǎn)vj的路徑，則稱vi與vj可及(連通)。若G為無向圖，且V(G)中任意兩頂點(diǎn)都可及，則稱G為連通圖。若G為有向圖，且對于V(G)中任意兩個不同的

7、頂點(diǎn)vi和vj ， vi與vj可及， vj與vi也可及，則稱G為強(qiáng)連通圖。也可以定義“弱連通圖”的概念，即在任何頂點(diǎn)u和v之間，至少存在一條從u到v的路徑或者存在一條從v到u的路徑。V5V4V2V1V3V1V2V3V4定義5.10 對于G的一個連通子圖GK，如果不存在G的另一個連通子圖G，使得V(GK)V(G)，則稱GK為G的連通分量。無向圖G的極大連通子圖稱為G的連通分量。 (a) (b) (c) (d) (e) 一個圖的連通子圖e是a的連通分量連通分量V4V3V1V2V4V3V2V1連通分量BAEJKGLMDIFCHALJCFBMDEKIHG有時候，圖不僅要表示出元素之間是否存在某種關(guān)系，

8、同時還需要表示與這一關(guān)系相關(guān)的某些信息。例如在計(jì)算機(jī)網(wǎng)絡(luò)對應(yīng)的圖中，頂點(diǎn)表示計(jì)算機(jī)，頂點(diǎn)之間的邊表示計(jì)算機(jī)之間的通訊鏈路。實(shí)際中，為了管理計(jì)算機(jī)網(wǎng)絡(luò)，我們需要這個圖包含更多的信息，例如每條通訊鏈路的物理長度、成本和帶寬等信息。為此，我們?yōu)閭鹘y(tǒng)圖中的每條邊添加相應(yīng)的數(shù)據(jù)域以記錄所需要的信息。定義5.11 設(shè)G = (V, E)是圖，若對圖中的任意一條邊l，都有實(shí)數(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()=V1V2V3V4

9、2357定義5.12 若 是權(quán)圖G中的一條路徑，則 稱為加權(quán)路徑 的長度或權(quán)重。權(quán)通常用來表示從一個頂點(diǎn)到另一個頂點(diǎn)的距離或費(fèi)用。 無向圖 有向圖 邊 端點(diǎn) 弧 弧頭 弧尾 相鄰的 鄰接到 鄰接自 度 出度 入度 連通圖 強(qiáng)連通圖 第五章 圖5.1 基本概念5.2 圖的存儲結(jié)構(gòu)5.3 圖的遍歷5.4 拓?fù)渑判?.5 關(guān)鍵路徑 5.6 最短路徑5.7 最小支撐樹鄰接矩陣 鄰接表(逆鄰接表)1、 圖的存儲結(jié)構(gòu)用順序方式或鏈接方式存儲圖的頂點(diǎn)表v0,v1,vn-1 ,圖的邊用nn階矩陣A =(aij)表示，A的定義如下：（a）若圖為權(quán)圖，aij對應(yīng)邊的權(quán)值；（b）若圖為非權(quán)圖，則（1） aii=0；

10、（2） aij=1，當(dāng)ij且或(vi,vj)存在時； （3）aij=0，當(dāng)ij且或(vi,vj)不存在時。稱矩陣A為圖的鄰接矩陣。1、鄰接矩陣?yán)?無向圖的鄰接矩陣無向圖的鄰接矩陣是對稱陣。0123 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 00 1 2 3V0V3V2V1 例2有向圖的鄰接矩陣V0V3V4V1V201234 0 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 借助鄰接矩陣，

11、可以很容易地求出圖中頂點(diǎn)的度。無向圖 鄰接矩陣的第i行（或第i列）的非零元素的個數(shù)是頂點(diǎn)Vi的度。有向圖 鄰接矩陣第i行的非零元素的個數(shù)為頂點(diǎn)Vi的出度；第i列的非零元素的個數(shù)為頂點(diǎn)Vi的入度。Graph1V4V3V2V1Graph2V5V1V2V3V4 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)酱鎯Y(jié)構(gòu)。對圖的每個頂點(diǎn)建立一個單鏈表（n個頂點(diǎn)建立n個單鏈表），第i個單鏈表中的結(jié)點(diǎn)包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。由順序存儲的頂點(diǎn)表和鏈接存儲的邊鏈表構(gòu)

12、成的圖的存儲結(jié)構(gòu)被稱為鄰接表。 V0V3V2V1V0V1V2V302311230120303 例1無向圖的鄰接表 頂點(diǎn)的結(jié)構(gòu) 非權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu)對于用鄰接表存儲的無向圖，每條邊對應(yīng)兩個邊結(jié)點(diǎn)；根據(jù)鄰接表，可以統(tǒng)計(jì)出無向圖中每個頂點(diǎn)的度。V0V3V2V1V0V1V2V302311230120303VerName adjacentVerAdj link例2有向圖的鄰接表對于用鄰接表存儲的有向圖，每條邊只對應(yīng)一個邊結(jié)點(diǎn)；根據(jù)鄰接表，可以統(tǒng)計(jì)出有向圖中每個頂點(diǎn)的出度。但是，如果要統(tǒng)計(jì)頂點(diǎn)的入度，每統(tǒng)計(jì)一個頂點(diǎn)，就要遍歷所有的邊結(jié)點(diǎn)，其時間復(fù)雜度為O(e)(e為圖中邊的個數(shù))，從而統(tǒng)計(jì)所有頂點(diǎn)入度的時間

13、復(fù)雜度為O(ne)(n為圖的頂點(diǎn)個數(shù))。V0V1V2V3V4024311300413V0V3V4V1V2例3有向圖的逆鄰接表建立逆鄰接表(頂點(diǎn)的指向關(guān)系與鄰接表恰好相反)，根據(jù)逆鄰接表，很容易統(tǒng)計(jì)出圖中每個頂點(diǎn)的入度。V0V3V4V1V2V0V1V2V3V4024311022413例4 權(quán)圖的鄰接表V0V3V2V135284V0V1V2V3023113382508221405320334權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu)VerAdj cost link采用鄰接矩陣還是用鄰接表來存儲圖，要視對給定圖實(shí)施的具體操作而定。對于邊很多的圖(也稱稠密圖)，適于用鄰接矩陣存儲，因?yàn)檎加玫目臻g少。而對于頂點(diǎn)多而邊少的圖(也稱

14、稀疏圖)，若用鄰接矩陣存儲，對應(yīng)的鄰接矩陣將是一個稀疏矩陣，存儲利用率很低。因此，頂點(diǎn)多而邊少的圖適于用鄰接表存儲。鄰接矩陣存儲的圖類Graph_Matrix鄰接表存儲的圖類Graph_List2、 圖的實(shí)現(xiàn)1. 用鄰接矩陣存儲的圖類 Graph_Matrix類聲明const int MaxGraphSize = 256 ; / 圖的最大頂點(diǎn)個數(shù)const int MaxWeight = 1000 ; /邊的最大權(quán)值template class Graph_Matrix private: SLList VertexList ; /頂點(diǎn)表int edge MaxGraphSize MaxGrap

15、hSize ; /鄰接矩陣int graphsize ; /當(dāng)前頂點(diǎn)數(shù)public: /I. 構(gòu)造函數(shù)與析構(gòu)函數(shù)Graph_Matrix( ) ;Graph_Matrix( ) ; /II. 圖的維護(hù)函數(shù)int GraphEmpty(void) const /檢測圖是否為空int GraphFull(void) const ; /檢測圖是否已滿，即頂點(diǎn)個數(shù)是否越界int NumberOfVertices( void ) const ;/返回圖的頂點(diǎn)個數(shù)int NumberOfEdges( void ) const ; /返回圖的邊個數(shù) int GetWeight( const int v1,

16、const int v2 ) ; / 返回指定邊的權(quán)值int* & GetNeighbors( const int v ) ;/ 返回頂點(diǎn)v的鄰接頂點(diǎn)表 int GetFirstNeighbor( const int v ) ; / 返回序號為v的頂點(diǎn)的第一個鄰接頂點(diǎn)的序號 int GetNextNeighbor( const int v1, const int v2 ) ; /返回序號為v1的頂點(diǎn)相對于序號為v2的頂點(diǎn)的下一個鄰接頂點(diǎn)的序號void InsertVertex( const int & v) ; / 向圖中插入一個頂點(diǎn)void InsertEdge( const int & v

17、1, const int & v2, int weight ); /向圖中插入一條邊void DeleteVertex( const int & v ) ; /從圖中刪除一個頂點(diǎn)void DeleteEdge( const int & v1, const int & v2 ) ; /從圖中刪除一條邊 / III. 圖的基本算法 void DepthFirstSearch( ) ;/圖的深度優(yōu)先搜索(遞歸) void DFS(const int v) ; /從頂點(diǎn)v開始進(jìn)行圖的深度優(yōu)先搜索(迭代方法) void BFS( const int v ) ; /從頂點(diǎn)v開始進(jìn)行圖的廣度優(yōu)先搜索 voi

18、d TopoOrder( ) ; / 圖的拓?fù)渑判?void CriticalPath( ) ; / 輸出圖的關(guān)鍵路徑 void ShortestPath(const int v ) ; / 求無權(quán)圖中頂點(diǎn)v到其他頂點(diǎn)的最短路徑 void DShortestPath(const int v ) ; / 求正權(quán)圖中頂點(diǎn)v到其他頂點(diǎn)的最短路徑 void AllLength( ) ; / 求正權(quán)圖中每對頂點(diǎn)間的最短路徑 void Prim( ) ; / 構(gòu)造圖的最小支撐樹的普里姆算法 ;/ 構(gòu)造函數(shù), 創(chuàng)建一個圖Graph_Matrix : Graph_Matrix () cin graphsize

19、;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 4 2 00 1 2 3ADCB35284/ 取得序號為v的頂點(diǎn)的第一個鄰接頂點(diǎn)的序號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沒有鄰接頂點(diǎn)，則返回-10123 0 3 5

20、8 3 0 4 5 0 2 8 4 2 00 1 2 3ADCB35284/取得頂點(diǎn)v1相對于v2的下一個鄰接頂點(diǎn)的序號int Graph_Matrix :GetNextNeighbor( 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鄰接的頂點(diǎn)，則返回-10123 0 3 5 8 3 0 4 5 0 2 8 4 2 00 1 2 3ADCB352

21、84刪除頂點(diǎn)Vertex算法思想：不僅要從頂點(diǎn)表中刪除該頂點(diǎn)，還需要刪除該頂點(diǎn)所發(fā)出的邊以及所有的入邊，即在鄰接矩陣中刪除相應(yīng)的行和列。2. 用鄰接表存儲的圖類Graph_ListV0V3V2V1V0V1V2V3023112301203032. 用鄰接表存儲的圖類Graph_List/ 邊結(jié)點(diǎn)的結(jié)構(gòu)體struct Edge friend class Graph_List ; int VerAdj ; / 鄰接頂點(diǎn)序號，從0開始編號 int cost ; / 邊的權(quán)值 Edge *link ; / 指向下一個邊結(jié)點(diǎn)的指針 ;權(quán)圖中邊結(jié)點(diǎn)結(jié)構(gòu)VerAdj cost link/ 頂點(diǎn)表中結(jié)點(diǎn)的結(jié)構(gòu)體

22、struct Vertexfriend class Graph_List;int VerName;/ 頂點(diǎn)的名稱Edge *adjacent;/ 邊鏈表的頭指針VerName adjacent頂點(diǎn)的結(jié)構(gòu)/采用鄰接表存儲的Graph_List類定義class Graph_List private:Vertex *Head; / 頂點(diǎn)表頭指針int graphsize; / 圖中當(dāng)前頂點(diǎn)的個數(shù) public:/ I. 圖的構(gòu)造函數(shù)和析構(gòu)函數(shù)Graph_List ( ); Graph_List ( );/ II. 圖的維護(hù)函數(shù)與Graph_Matrix類中的維護(hù)函數(shù)相同。/ III. 圖的基本算法與

23、Graph_Matrix類中的基本算法相同。 ;/ 求序號為v的頂點(diǎn)的第一個鄰接頂點(diǎn)的序號int Graph_List: GetFirstNeighbor( const int v ) if ( v = = -1 ) return -1; Edge *p = Headv.adjacent ; if (p != NULL) return pVerAdj ; else return -1;ADCBABCD02311230120303Head/ 求序號為v1的頂點(diǎn)相對于序號為v2的頂點(diǎn)的下一個鄰接頂點(diǎn)的序號int Graph_List : GetNextNeighbor( const int v1

24、, 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 = = NULL) return -1; p = p link ; /找v2的下一個邊結(jié)點(diǎn) if (p = = NULL) return -1; return p VerAdj ; return -1 ;ADCBABCD02311230120303 第五章 圖5.1 基本概念5.2 圖的存儲結(jié)構(gòu)5.3 圖的遍歷5.4 拓?fù)渑?/p>

25、序5.5 關(guān)鍵路徑 5.6 最短路徑5.7 最小支撐樹從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪遍圖中所有頂點(diǎn)，且使每個頂點(diǎn)僅被訪問一次，就叫做圖的遍歷 ( Graph Traversal )。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個頂點(diǎn)之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，可設(shè)置一個標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組 visited ，它的初始狀態(tài)為 0，在圖的遍歷過程中，一旦某一個頂點(diǎn) i 被訪問，就立即讓 visitedi 為 1，防止它被多次訪問。5.3.1 深度優(yōu)先遍歷 深度優(yōu)先遍歷又被稱為深度優(yōu)先搜索 DFS ( Depth Firs

26、t Search ) 基本思想: DFS 在訪問圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問它的任一鄰接頂點(diǎn) w1；再從 w1 出發(fā)，訪問與 w1鄰接但還沒有訪問過的頂點(diǎn) w2；然后再從 w2 出發(fā)，進(jìn)行類似的訪問， 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。深度優(yōu)先搜索DFS ( Depth First Search )深度優(yōu)先搜索的示例1. 遞歸算

27、法/P140算法DepthFirstSearch (v, visited)/* 圖的深度優(yōu)先遍歷的遞歸算法*/DFSearch1初始化 PRINT(v).visitedv 1. p adjacent(Headv) .DFSearch2深度優(yōu)先遍歷圖WHILE pDO( IF visitedVerAdj(p)1 THEN DepthFirstSearch (VerAdj(p), visited) . p link(p) . )算法 DFS_Main( ) visited = new intgraphsize ;/ 為輔助數(shù)組申請空間 for( int k = 0 ; k graphsize ;

28、k + + )visitedk = 0 ; / 數(shù)組初始化 / 從序號為0的頂點(diǎn)出發(fā)，深度優(yōu)先遍歷圖 DepthFirstSearch( 0 , visited ) ; delete visited ; / 釋放輔助數(shù)組空間01234567002431567123457612043065172727364517DFSearch1初始化 PRINT(v). visitedv 1. p adjacent(Headv) .DFSearch2深度優(yōu)先遍歷圖 WHILE p DO ( IF visitedVerAdj(p)1 THEN DepthFirstSearch (VerAdj(p), visit

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

30、遍歷的非遞歸算法*/DFS1初始化 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不空時 */( 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). ) ) )DF

31、S2利用堆棧S深度優(yōu)先遍歷圖 WHILE NOT(ISEMTS(S) DO /* 當(dāng)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). ) ) )A0243156BCDEFG162345054ACGBFED算法分析圖中有 n 個頂點(diǎn)，e 條邊。如果用鄰接表表示圖，沿頂點(diǎn)的adjacent可以找到某個頂點(diǎn)v 的所有鄰接頂點(diǎn)w。由于總共有2e 個邊結(jié)點(diǎn)，所以

32、掃描邊的時間為O(e)。而且對所有頂點(diǎn)遞歸訪問1次，所以遍歷圖的時間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個頂點(diǎn)的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時間為O(n2)。非連通圖需要多次調(diào)用深度優(yōu)先遍歷算法For i=0 to n-1 DOvisitedi 0.For j=0 to n-1 DOIF visitedj=0 THENDepthFirstSearch (vj, visited)V1V2V3V4V55.3.2 廣度優(yōu)先遍歷 基本思想：首先訪問初始點(diǎn)頂點(diǎn)v0，之后依次訪問與v0鄰接的全部頂點(diǎn)w1，w2，.，wk。然后，再順次訪問與w1，w2，.，wk鄰

33、接的尚未訪問的全部頂點(diǎn)，再從這些被訪問過的頂點(diǎn)出發(fā)，逐個訪問與它們鄰接的尚未訪問過的全部頂點(diǎn)。依此類推，直到連通圖中的所有頂點(diǎn)全部訪問完為止。廣度優(yōu)先搜索BFS ( Breadth First Search )廣度優(yōu)先搜索的示例 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先搜索類似于樹的層次遍歷，是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。為了實(shí)現(xiàn)逐層訪問，算法中使用一個隊(duì)列，以便于向下一層訪問。與深度優(yōu)先搜索過程一樣，為避免重復(fù)訪問，需要一個輔助數(shù)組visited 。算法BFS (Head, v,

34、 visited. visited) /*廣度優(yōu)先遍歷算法 */BFS1初始化 （P142改錯） 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ì)列不空時 */ ( v Q. /* 出隊(duì) */ p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN( Q VerAdj(p) . PRINT(VerAdj(p) ) . vis

35、itedVerAdj(p) 1. ) . p link(p). ) ) WHILE NOT(ISEMTQ(Q) DO /* 當(dāng)隊(duì)列不空時 */ ( 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). ) ) 01234567024315670123457612043065172727364517算法分析如果使用鄰接表表示圖，則循環(huán)的總時間代價為 d0 + d1

36、+ + dn-1 = O(e)，其中的 di 是頂點(diǎn) i 的度?？偟臅r間復(fù)雜度為O(n+e)。如果使用鄰接矩陣，則對于每一個被訪問的頂點(diǎn)，循環(huán)要檢測矩陣中的 n 個元素，總的時間代價為O(n2)。 第五章 圖5.1 基本概念5.2 圖的存儲結(jié)構(gòu)5.3 圖的遍歷5.4 拓?fù)渑判?.5 關(guān)鍵路徑 5.6 最短路徑5.7 最小支撐樹 5.4 拓?fù)渑判?計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。AOV網(wǎng):在有向圖中，用頂點(diǎn)表示活動，用有向邊表示活動之間的先后關(guān)系，稱這樣的有向圖為AOV網(wǎng)(Act

37、ivity On Vertex Network)。例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。 例按拓?fù)浯涡虬才庞?jì)算機(jī)專業(yè)必修課程計(jì)算機(jī)專業(yè)必修課程課程代號 課程名稱 先修課程 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 C0C2C3C5C4C1C7C6C8在AOV網(wǎng)絡(luò)中，如果活動Vi

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

39、輸出，或網(wǎng)中剩余頂點(diǎn)入度均不為0 (說明網(wǎng)中存在回路，無法繼續(xù)拓?fù)渑判? 拓?fù)湫蛄校?C0 ,C1 ,C2 ,C4 ,C3 ,C5 ,C7 ,C8 ,C6 C0 ,C7 ,C8 ,C1 ,C4 ,C2 ,C3 ,C6 ,C5C2C3C5C4C7C6C8C2C3C5C4C1C7C6C8C3C5C4C7C6C8C3C5C7C6C8C5C7C6C8C7C6C8C6C8C6C0C2C3C5C4C1C7C6C8 回路與拓?fù)渑判蛉魏螣o回路的AOV網(wǎng)，其頂點(diǎn)均可排成拓?fù)湫蛄?其拓?fù)湫蛄胁灰欢ㄎㄒ?；如果能將AOV網(wǎng)的所有頂點(diǎn)都排入一個拓?fù)湫蛄校瑒t該AOV網(wǎng)中必定無有向環(huán)；若在有回路的AOV網(wǎng)中，找不到所有頂

40、點(diǎn)的拓?fù)湫蛄?AOV網(wǎng)所代表的工程是不可行的)。 。因此，可以用拓?fù)渑判蚺袛嘤邢驁D中是否有回路假定AOV網(wǎng)用鄰接表的形式存儲。為實(shí)現(xiàn)拓?fù)渑判蛩惴?，事先需好兩?xiàng)準(zhǔn)備工作：建立一個數(shù)組count ，counti的元素值取對應(yīng)頂點(diǎn)i的入度；建立一個堆棧，棧中存放入度為0的頂點(diǎn)，每當(dāng)一個頂點(diǎn)的入度為0，就將其壓入棧。拓?fù)渑判蛩惴?25140002123013425count02431524235355用一個堆棧存放入度為 0 的頂點(diǎn)。虛擬的堆棧利用變量top和count數(shù)組元素的值來模擬堆棧的壓入和彈出。 top:“棧頂”位置，初始為-1counttop：次棧頂元素入棧：counti = top; t

41、op = i;出棧：j = top; top = counttop;算法TopoOrder(n) /* 圖的拓?fù)渑判蛩惴?*/TOrder1初始化 /* 計(jì)算count數(shù)組 */ FOR i = 0 TO 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). ) )/統(tǒng)計(jì)每個頂點(diǎn)的入度325140002123013425count02431524235355拓?fù)渑判蛩惴ǎ?算法TOrder1初始化第二部分 top

42、-1./棧頂指針top FOR i = 0 TO n-1 DO/將入度為0的頂點(diǎn)入棧IF counti = 0 THEN ( counti top. top i. )top102123013425count325140102123013425counttop1拓?fù)渑判蛩惴ǎ?/算法TOrder1初始化第二部分 top -1./棧頂指針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 / 若

43、循環(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. / 頂點(diǎn)k的入度減1 IF countk = 0 THEN /若入度為0，則k入棧 (countk top. top k.) p link (p). ) ) FOR i = 1 TO n DO(j top. top cou

44、nttop . /* 彈出堆棧頂點(diǎn)j */PRINT ( j ) .p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). )top1 2123013425count102123013425counttop325140 1 1013013425counttop3254002431524235355pppFOR i = 1 TO n DO(

45、j top. top counttop . /* 彈出堆棧頂點(diǎn)j */PRINT ( j ) .p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0， 則k 入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ) 32501 1 12013425counttopFOR i = 1 TO n DO(j top. top counttop . /* 彈出堆棧頂點(diǎn)j */PRINT ( j ) .

46、p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). ) 1 1 2013425counttop325FOR i = 1 TO n DO(j top. top counttop . /* 彈出堆棧頂點(diǎn)j */PRINT ( j ) .p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k Ver

47、Adj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). )1 1013425counttop35FOR i = 1 TO n DO(j top. top counttop . /* 彈出堆棧頂點(diǎn)j */PRINT ( j ) .p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF cou

48、ntk = 0 THEN (countk top. top k.) /入棧 p link (p). ) 1 013425counttop5FOR i = 1 TO n DO(j top. top counttop . /* 彈出堆棧頂點(diǎn)j */PRINT ( j ) .p adjacent( Headj ) . WHILE p DO/* 掃描j的邊鏈表 */ (k VerAdj(p) . /* k的入度減1，若入度為0，則k入棧 */ countk countk-1. IF countk = 0 THEN (countk top. top k.) /入棧 p link (p). )引理5.1

49、設(shè)圖G = (V, E)是非循環(huán)圖, V(G), 則G中一定存在入度為零的頂點(diǎn)定理5.2 設(shè)G=(V, E)是非循環(huán)圖，V(G)=1, 2 , n, e=|E(G)|. 則算法TopoOrder是正確的且算法的時間復(fù)雜性為 O(n+e). 第五章 圖5.1 基本概念5.2 圖的存儲結(jié)構(gòu)5.3 圖的遍歷5.4 拓?fù)渑判?.5 關(guān)鍵路徑 5.6 最短路徑5.7 最小支撐樹5.5 關(guān)鍵路徑 5.5.1 基本概念 邊表示活動(Activity) 邊的權(quán)值表示活動的持續(xù)時間(Duration) 頂點(diǎn)表示入邊的活動已完成，出邊的活動可以開始的狀態(tài)，也稱為事件(Event) 這樣的有向無環(huán)的帶權(quán)圖叫做AOE

50、 (Activity On Edges Network)網(wǎng)。例 某工程源點(diǎn)：表示整個工程的開始（入度為零）。匯點(diǎn)：表示整個工程的結(jié)束（出度為零）。完成整個工程至少需要多少時間？為縮短工程的時間，應(yīng)當(dāng)加快哪些活動？325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn)從源點(diǎn)到各頂點(diǎn)的路徑可能不止一條，路徑長度也可能不同。只有各條路徑上所有活動都完成了，整個工程才算完成。關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)具有最大長度的路徑稱為關(guān)鍵路徑。路徑長度：指路徑上的各邊權(quán)值之和。關(guān)鍵活動：關(guān)鍵路徑上的活動。325140867a1=6a8=7a7=9a6=2

51、a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn) 關(guān)鍵活動有關(guān)的量： 事件vi的最早發(fā)生時間ve(i): 從源點(diǎn)v0到vi的最長路徑長度。 事件vi的最遲發(fā)生時間vl(i): 保證匯點(diǎn)的最早發(fā)生時間不推遲的前提下，事件vi允許的最遲開始時間，等于ve(n-1)減去從vi到vn-1最長路徑長度。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn)325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn) 關(guān)鍵活動有關(guān)的量： 活動ak的最早開始時間e(k

52、): 設(shè)活動ak在有向邊上, e(k)是從源 點(diǎn)v0到vi的最長路徑長度。因此e(k)=ve(i)。 關(guān)鍵活動有關(guān)的量： 活動ak的最遲開始時間l(k): l(k)是在不會引起時間延誤的前提下，該活動允許的最遲開始時間。 設(shè)活動ak在有向邊上,則 l(k)= vl(j)-dur()。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn) 關(guān)鍵活動： l(k) e(k)325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn)5.5.2 關(guān)鍵活動算法求關(guān)鍵活動的基本步驟：

53、對AOE網(wǎng)進(jìn)行拓?fù)渑判颍赐負(fù)浯涡蚯蟪龈黜旤c(diǎn)事件的最早發(fā)生時間ve，若網(wǎng)中有回路，則終止算法； 按拓?fù)湫蛄械哪嫘蚯蟪龈黜旤c(diǎn)事件的最遲發(fā)生時間vl 根據(jù)ve和vl的值，求出各活動的最早開始時間e(k)與最遲開始時間l(k)，若e(k)= l(k)，則是關(guān)鍵活動。 例 求關(guān)鍵活動第1步ve(i)ve(0)0ve(i)maxve(j)+ dur()E(G),i=1,2,n-1325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn)按拓?fù)湔蜻f推:注：此時j為前驅(qū)結(jié)點(diǎn)，i為后繼結(jié)點(diǎn) ve(0)=0ve(1)= ve(0)+weight()=

54、0+6=6ve(2)= ve(0)+weight()=0+4=4ve(3)= ve(0)+weight()=0+5=5ve(4)= maxve(1)+ weight()， ve(2)+ weight() =max6+1,4+1=7325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn) ve(5)= ve(3)+weight()=5+2=7ve(6)= ve(4)+weight()=7+9=16ve(7)= maxve(4)+ weight()， ve(5)+ weight()=max7+7,7+4=14ve(8)= maxve(6

55、)+ weight()， ve(7)+ weight()=max16+2,14+41=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn) 例 求關(guān)鍵活動第2步vl(i)vl(n-1) ve(n-1)vl(i)minvl(j)- dur()E(G),i= n-2, n-3,0325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn)按拓?fù)淠嫘蜻f推: vl(8)= ve(8)=18vl(7)= vl(8)-weight()=18-4=14vl(6)= vl(8)-weight()=18-2=16vl(5)= vl(7)-weight()=14-4=10vl(4)= minvl(7)- weight()， vl(6)- weight() =min14-7,16-9=7325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)源點(diǎn) vl(3)= vl(5)-weight()=10-2=8vl(2)= vl(4)-weight()=7-1=6vl(1)= vl(4)-weight()=7-1=6vl(0)= minvl(1)- weig