1、第第12章章 圖的根本概念圖的根本概念 圖的定義圖的定義 圖的術語圖的術語 圖的運算圖的運算 圖的存儲圖的存儲 圖的遍歷圖的遍歷 圖遍歷的運用圖遍歷的運用圖的定義圖的定義 圖可以用圖可以用G=(V, E)G=(V, E)表示。其中，表示。其中，V V是頂點的集合，是頂點的集合，E E是銜接頂是銜接頂點的邊弧的集合。點的邊弧的集合。 假設邊是有方向的，稱為有向圖。有向圖的邊用假設邊是有方向的，稱為有向圖。有向圖的邊用表示。表示。表示從表示從A A出發到出發到B B的一條邊。在有向圖中，的一條邊。在有向圖中，和和是不一樣的。是不一樣的。 假設邊是無方向的，稱為無向圖。無向圖的邊通常用圓括號假設邊是

2、無方向的，稱為無向圖。無向圖的邊通常用圓括號表示。表示。A A，B B表示頂點表示頂點A A和和B B之間有一條邊。無向圖也稱為之間有一條邊。無向圖也稱為雙向圖。雙向圖。 加權圖：邊被賦予一個權值的圖稱為加權圖。假設圖是有向加權圖：邊被賦予一個權值的圖稱為加權圖。假設圖是有向的，稱為加權有向圖，假設是無向的，稱為加權無向圖。的，稱為加權有向圖，假設是無向的，稱為加權無向圖。 如如G1G1：V = AV = A，B B，C C，DD， E = , , , , E = , , , , , , 表示的圖如下所示表示的圖如下所示ABCDABCDEV = A，B，C，D，E ，E = A，B， A，C，

3、 B，D， B, E) , D，E， C，E無向圖無向圖12435661655563421243566165556342加權圖中邊的表示：加權圖中邊的表示：或或(Vi, Vj, W)加權圖加權圖第第12章章 圖的根本概念圖的根本概念 圖的定義圖的定義 圖的術語圖的術語 圖的運算圖的運算 圖的存儲圖的存儲 圖的遍歷圖的遍歷 圖遍歷的運用圖遍歷的運用圖的根本術語圖的根本術語 鄰接：如鄰接：如ViVi，VjVj是圖中的一條邊，那么稱是圖中的一條邊，那么稱ViVi和和VjVj是鄰接的。如是鄰接的。如ViVj是圖中的一條邊，是圖中的一條邊，那么稱那么稱ViVi鄰接到鄰接到VjVj，或，或VjVj和和Vi

4、Vi鄰接。鄰接。 度：無向圖中鄰接于某一結點的邊的總數。度：無向圖中鄰接于某一結點的邊的總數。 入度：有向圖中進入某一結點的邊數，稱為該入度：有向圖中進入某一結點的邊數，稱為該結點的入度結點的入度 出度：有向圖中分開某一結點的邊數，稱為該出度：有向圖中分開某一結點的邊數，稱為該結點的出度結點的出度子圖子圖ABCDACABCD有向圖有向圖G1的子圖的子圖ABCD有向圖有向圖 G1設有兩個圖設有兩個圖G=G=V V，E E和和G G= =V V，E E，假設，假設EEVV,那么稱那么稱G G是是G G的子圖的子圖無向圖無向圖 G2ABCDEABDEAABCDABCDE無向圖無向圖G2的子圖的子圖途

5、徑和途徑長度途徑和途徑長度 對對1iN1iN，結點序列，結點序列w1,w2,wN w1,w2,wN 中的結點對中的結點對wi, wi, wi+1wi+1都有都有wi, wi+1wi, wi+1 E E或或 E E，那么，那么，w1,w2,wNw1,w2,wN是圖中的一條途徑。是圖中的一條途徑。 非加權的途徑長度就是組成途徑的邊數，對于途徑非加權的途徑長度就是組成途徑的邊數，對于途徑w1,w2,wNw1,w2,wN，非加權途徑長度為，非加權途徑長度為N-1N-1。 加權途徑長度是指途徑上一切邊的權值之和。加權途徑長度是指途徑上一切邊的權值之和。 簡單途徑和環：假設一條途徑上的一切結點，除了簡單途

6、徑和環：假設一條途徑上的一切結點，除了起始結點和終止結點能夠一樣外，其他的結點都不起始結點和終止結點能夠一樣外，其他的結點都不一樣，那么稱其為簡單途徑。一個回路或環是一條一樣，那么稱其為簡單途徑。一個回路或環是一條簡單途徑，其起始結點和終止結點一樣，且途徑長簡單途徑，其起始結點和終止結點一樣，且途徑長度至少為度至少為1 1。無向圖的連通性無向圖的連通性 連通：頂點連通：頂點v v至至v v 之間有途徑存在之間有途徑存在 連通圖：無向圖連通圖：無向圖 G G 的恣意兩點之間都是的恣意兩點之間都是連通的，那么稱連通的，那么稱 G G 是連通圖。是連通圖。 連通分量：非連通圖中的極大連通子圖連通分量

7、：非連通圖中的極大連通子圖ABCDEFGIJLHMKABCDEHMFGJILK無向圖無向圖G無向圖無向圖G的三個連通分量的三個連通分量有向圖的連通性有向圖的連通性 強連通圖：有向圖強連通圖：有向圖 G G 的恣意兩點之間都是的恣意兩點之間都是連通的，那么稱連通的，那么稱 G G 是強連通圖。是強連通圖。 強連通分量：極大連通子圖強連通分量：極大連通子圖 弱連通圖：如有向圖弱連通圖：如有向圖G G不是強連通的，但假不是強連通的，但假設把它看成是無向圖時是連通的，那么稱設把它看成是無向圖時是連通的，那么稱該圖是弱連通的該圖是弱連通的有向圖有向圖G有向圖有向圖G G的兩個強連通分量的兩個強連通分量A

8、BCDABCD不是強連通圖。由于不是強連通圖。由于B B到其他結點都沒有途到其他結點都沒有途徑。但此圖是弱連通徑。但此圖是弱連通的。的。完全圖完全圖 完全圖：每兩個節點之間都有邊的無完全圖：每兩個節點之間都有邊的無向圖稱為完全圖。完全圖有向圖稱為完全圖。完全圖有 n(n-1)/2 n(n-1)/2 條邊的無向圖。其中條邊的無向圖。其中 n n 是結點個數。是結點個數。即即 有向完全圖：每兩個節點之間都有兩有向完全圖：每兩個節點之間都有兩條弧的有向圖稱為有向完全圖。有向條弧的有向圖稱為有向完全圖。有向完全圖有完全圖有 n(n-1) n(n-1) 條邊。其中條邊。其中 n n 是結是結點個數。即點

9、個數。即 假設一個有向圖中沒有環，那么稱為假設一個有向圖中沒有環，那么稱為有向無環圖，簡寫為有向無環圖，簡寫為DAGDAG2nC22nCABCD無向完全圖無向完全圖生成樹生成樹ABCDEHMABCDEHM無向圖無向圖G 無向圖無向圖G的生成樹的生成樹 生成樹是連通圖的極小連通子圖。包含圖的一生成樹是連通圖的極小連通子圖。包含圖的一切切 n n 個結點，但只含圖的個結點，但只含圖的 n-1 n-1 條邊。在生成條邊。在生成樹中添加一條邊之后，必定會構成回路或環。樹中添加一條邊之后，必定會構成回路或環。第第12章章 圖的根本概念圖的根本概念 圖的定義圖的定義 圖的術語圖的術語 圖的運算圖的運算 圖

10、的存儲圖的存儲 圖的遍歷圖的遍歷 圖遍歷的運用圖遍歷的運用圖的運算圖的運算 常規操作：常規操作： 構造一個由假設干個結點、假設干條邊組構造一個由假設干個結點、假設干條邊組成的圖；成的圖； 判別兩個結點之間能否有邊存在；判別兩個結點之間能否有邊存在； 在圖中添加或刪除一條邊；在圖中添加或刪除一條邊； 前往圖中的結點數或邊數；前往圖中的結點數或邊數； 按某種規那么遍歷圖中的一切結點。按某種規那么遍歷圖中的一切結點。 和運用嚴密結合的運算：和運用嚴密結合的運算： 拓撲排序拓撲排序 找最小生成樹找最小生成樹 找最短途徑等。找最短途徑等。圖的籠統類圖的籠統類 template class graph p

11、ublic:virtual bool insert(int u, int v, TypeOfEdge w) = 0;virtual bool remove(int u, int v) = 0;virtual bool exist(int u, int v) const = 0;virtual numOfVer() const return Vers;virtual numOfEdge() const return Edges;protected:int Vers, Edges; 第第12章章 圖的根本概念圖的根本概念 圖的定義圖的定義 圖的術語圖的術語 圖的運算圖的運算 圖的存儲圖的存儲 圖的

12、遍歷圖的遍歷 圖遍歷的運用圖遍歷的運用圖的存儲圖的存儲 鄰接矩陣和加權鄰接矩陣鄰接矩陣和加權鄰接矩陣 鄰接表鄰接表鄰接矩陣鄰接矩陣有向圖有向圖設有向圖具有設有向圖具有 n n 個結點，那么用個結點，那么用 n n 行行 n n 列的布爾矩列的布爾矩陣陣 A A 表示該有向圖假設表示該有向圖假設i i 至至 j j 有一條有向邊有一條有向邊, , Ai,j = 1 ,Ai,j = 1 ,假設假設 i i 至至 j j 沒有一條有向邊沒有一條有向邊,Ai,j ,Ai,j = 0 = 0 ABCD表示成右圖矩陣表示成右圖矩陣0 1 1 00 0 0 00 0 0 11 0 0 0留意：留意： 出度出

13、度: i: i行之和。入度行之和。入度: j: j列之和。列之和。鄰接矩陣鄰接矩陣有向圖有向圖ABCD表示成右圖矩陣表示成右圖矩陣0 1 1 00 0 0 00 0 0 11 0 0 0在物理實現時的思索：分別用在物理實現時的思索：分別用 0 0、1 1、2 2、3 3 分別標識結分別標識結點點A A、B B、C C、D D。而將真正的數據字段之值放入一個一維數。而將真正的數據字段之值放入一個一維數組之中。組之中。 0 1 2 30123DABC 0 1 2 3鄰接矩陣鄰接矩陣無向圖無向圖設無向圖具有設無向圖具有 n n 個結點，那么用個結點，那么用 n n 行行 n n 列的布爾矩陣列的布爾

14、矩陣 A A 表示該無向圖；并且表示該無向圖；并且 Ai,j = 1 , Ai,j = 1 , 假設假設i i 至至 j j 有一條無有一條無向邊；向邊；Ai,j = 0Ai,j = 0假設假設 i i 至至 j j 沒有一條無向邊沒有一條無向邊 表示成右圖矩陣表示成右圖矩陣0 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 10 1 1 1 0ABCDE在物理實現時的思索，和前一頁的無向圖類似。在物理實現時的思索，和前一頁的無向圖類似。留意：留意： 無向圖的鄰接矩陣是一個對稱矩陣無向圖的鄰接矩陣是一個對稱矩陣 i i 結點的度結點的度: i : i 行或行或 i i 列之和

15、。列之和。加權的鄰接矩陣加權的鄰接矩陣有向圖有向圖設有向圖具有設有向圖具有 n n 個結點，那么用個結點，那么用 n n 行行 n n 列的矩陣列的矩陣 A A 表表示該有向圖；示該有向圖； 假設假設i i 至至 j j 有一條有向邊且它的權值為有一條有向邊且它的權值為a a ，那么，那么Ai,j = a Ai,j = a 。假設。假設 i i 至至 j j 沒有一條有向邊。沒有一條有向邊。那么那么Ai,j = Ai,j = 空空 或其它標志或其它標志表示成右圖矩陣表示成右圖矩陣 a b b ba a ABCDaaabbb鄰接矩陣的特點鄰接矩陣的特點 優點：判別恣意兩點之間能否有邊方便，優點：

16、判別恣意兩點之間能否有邊方便，僅耗費僅耗費 O(1) O(1) 時間。時間。 缺陷：即使缺陷：即使 n2 n2 條邊，也需內存條邊，也需內存 n2 n2 單元，太多單元，太多; ; 僅讀入數據耗費僅讀入數據耗費 O( n2 ) O( n2 ) 時間，太長。而大多數的圖的邊數遠遠時間，太長。而大多數的圖的邊數遠遠小于小于n2n2。鄰接矩陣類的定義鄰接矩陣類的定義template class adjMatrixGraph:public graph public: adjMatrixGraph(int vSize, const TypeOfVer d, TypeOfEdge noEdgeFlag);

17、bool insert(int u, int v, TypeOfEdge w);bool remove(int u, int v);bool exist(int u, int v) const;adjMatrixGraph() ；private:TypeOfEdge *edge; /存放鄰接矩陣存放鄰接矩陣TypeOfVer *ver; /存放結點值存放結點值TypeOfEdge noEdge; /鄰接矩陣中的鄰接矩陣中的的表示值的表示值;構造函數構造函數template adjMatrixGraph:adjMatrixGraph (int vSize, const TypeOfVer d,

18、TypeOfEdge noEdgeFlag) int i, j; Vers = vSize; Edges = 0; noEdge = noEdgeFlag; /存放結點的數組的初始化存放結點的數組的初始化 ver = new TypeOfVervSize; for (i=0; ivSize;+ i) veri = di; /鄰接矩陣的初始化鄰接矩陣的初始化 edge = new TypeOfEdge*vSize; for (i=0; ivSize; + i) edgei = new TypeOfEdgevSize; for (j=0; jvSize; +j) edgeij = noEdge;

19、edgeii = 0; 析構函數析構函數template adjMatrixGraph: adjMatrixGraph()delete ver;for (int i=0; iVers; +i) delete edgeidelete edge;Insert函數函數template bool adjMatrixGraph: insert(int u, int v, TypeOfEdge w) if (u Vers - 1 | v Vers -1) return false; if (edgeuv != noEdge) return false; edgeuv = w; +Edges; return

20、 true; Remove函數函數template bool adjMatrixGraph: remove(int u, int v) if (u Vers -1 | v Vers -1) return false; if (edgeuv = noEdge) return false; edgeuv = noEdge; -Edges; return true; Exist函數函數template bool adjMatrixGraph: exist(int u, int v) const if (u Vers -1 | v Vers -1) return false; if (edgeuv =

21、 noEdge) return false; else return true; 圖的存儲圖的存儲 鄰接矩陣和加權鄰接矩陣鄰接矩陣和加權鄰接矩陣 鄰接表鄰接表鄰接表鄰接表 設有向圖或無向圖具有設有向圖或無向圖具有 n n 個結點，那么用結點表、個結點，那么用結點表、邊表表示該有向圖或無向圖。邊表表示該有向圖或無向圖。 結點表：用數組或單鏈表的方式存放一切的結點值。結點表：用數組或單鏈表的方式存放一切的結點值。假設結點數假設結點數n n知，那么采用數組方式，否那么應采知，那么采用數組方式，否那么應采用單鏈表的方式。用單鏈表的方式。 邊表邊結點表：每條邊用一個結點進展表示。邊表邊結點表：每條邊用一

22、個結點進展表示。同一個結點出發的一切的邊構成它的邊結點單鏈表。同一個結點出發的一切的邊構成它的邊結點單鏈表。ABCD無向圖無向圖 G2ABCDE有向圖有向圖 G10123 dest linkABCD1203 data adj12 data adj03041423AB01234CDE41 dest link鄰接表的特點鄰接表的特點 鄰接表是圖的規范存儲方式鄰接表是圖的規范存儲方式 優點：內存優點：內存 結點數結點數 邊數，處置時間也是邊數，處置時間也是結點數結點數 邊數，即為邊數，即為O(|V|+|E|)O(|V|+|E|)。 當我們談及圖的線性算法時，普通指的是當我們談及圖的線性算法時，普通指

23、的是O(|V|+|E|)O(|V|+|E|) 缺陷：缺陷： 確定確定 i - j i - j 能否有邊，最壞需耗費能否有邊，最壞需耗費 O(n) O(n) 時間。時間。 無向圖同一條邊表示兩次。邊表空間浪費一倍。無向圖同一條邊表示兩次。邊表空間浪費一倍。 有向圖中尋覓進入某結點的邊，非常困難。有向圖中尋覓進入某結點的邊，非常困難。鄰接表類的定義鄰接表類的定義template class adjListGraph:public graph public: adjListGraph(int vSize, const TypeOfVer d);bool insert(int u, int v, Ty

24、peOfEdge w);bool remove(int u, int v);bool exist(int u, int v) const;adjListGraph() ;private: struct edgeNode /鄰接表中存儲邊的結點類鄰接表中存儲邊的結點類int end; /終點編號終點編號TypeOfEdge weight; /邊的權值邊的權值edgeNode *next;edgeNode(int e, TypeOfEdge w, edgeNode *n = NULL) end = e; weight = w; next = n;struct verNode /保管頂點的數據元素類

25、型保管頂點的數據元素類型TypeOfVer ver; /頂點值頂點值edgeNode *head; /對應的單鏈表的頭指針對應的單鏈表的頭指針verNode( edgeNode *h = NULL) head = h ;verNode *verList; 構造函數構造函數template adjListGraph: adjListGraph(int vSize, const TypeOfVer d) Vers = vSize; Edges = 0; verList = new verNodevSize; for (int i = 0; i Vers; +i) verListi.ver = di

26、;析構函數析構函數template adjListGraph:adjListGraph() int i; edgeNode *p; for (i = 0; i next; delete p; delete verList; Insert函數函數template bool adjListGraph: insert(int u, int v, TypeOfEdge w) verListu.head = new edgeNode(v, w, verListu.head ); +Edges; return true;Remove函數函數template bool adjListGraph:remove

27、(int u, int v)edgeNode *p = verListu.head, *q; if (p = NULL) return false; /結點結點u沒有相連的邊沒有相連的邊 if (p-end = v) /單鏈表中的第一個結點就是被刪除的邊單鏈表中的第一個結點就是被刪除的邊 verListu.head = p-next; delete p; -Edges; return true; while (p-next !=NULL & p-next-end != v) p = p-next if (p-next = NULL) return false; /沒有找到被刪除的邊沒有

28、找到被刪除的邊 q = p-next; p-next = q-next; delete q; -Edges; return true;Exist函數函數template bool adjListGraph: exist(int u, int v) const edgeNode *p = verListu.head; while (p !=NULL & p-end != v) p = p-next; if (p = NULL) return false; else return true; 第第12章章 圖的根本概念圖的根本概念 圖的定義圖的定義 圖的術語圖的術語 圖的運算圖的運算 圖的

29、存儲圖的存儲 圖的遍歷圖的遍歷 圖遍歷的運用圖遍歷的運用圖的遍歷圖的遍歷 深度優先搜索深度優先搜索 廣度優先搜索廣度優先搜索對有向圖和無向圖進展遍歷是按照某種次序系統地對有向圖和無向圖進展遍歷是按照某種次序系統地訪問圖中的一切頂點，并且使得每個頂點只能被訪訪問圖中的一切頂點，并且使得每個頂點只能被訪問一次。在圖中某個頂點能夠和圖中的多個頂點鄰問一次。在圖中某個頂點能夠和圖中的多個頂點鄰接并且存在回路，因此在圖中訪問一個頂點接并且存在回路，因此在圖中訪問一個頂點u u之后，之后，在以后的訪問過程中，又能夠再次前往到頂點在以后的訪問過程中，又能夠再次前往到頂點u u，所，所以圖的遍歷要比樹的遍歷更

30、復雜以圖的遍歷要比樹的遍歷更復雜深度優先搜索深度優先搜索1 1、選中第一個被訪問的頂點；、選中第一個被訪問的頂點；2 2、對頂點作已訪問過的標志；、對頂點作已訪問過的標志；3 3、依次從頂點的未被訪問過的第一個、第、依次從頂點的未被訪問過的第一個、第二個、第三個二個、第三個 鄰接頂點出發，進展深鄰接頂點出發，進展深度優先搜索；度優先搜索；4 4、假設還有頂點未被訪問，那么選中一個、假設還有頂點未被訪問，那么選中一個起始頂點，轉向起始頂點，轉向2 2；5 5、一切的頂點都被訪問到，那么終了。、一切的頂點都被訪問到，那么終了。5672413從結點從結點5開場進展深度優先的開場進展深度優先的搜索，那

31、么遍歷序列可以為：搜索，那么遍歷序列可以為：5，7，6，2，4，3，1，也可以為：也可以為：5，6，2，3，1，4，7。 深度優先生成樹深度優先生成樹56723145672314深度優先生成森林深度優先生成森林 在進展深度優先搜索在進展深度優先搜索 DFS DFS 時，有時并不一時，有時并不一定可以保證從某一個結點出發能訪問到一切定可以保證從某一個結點出發能訪問到一切的頂點的頂點 在這種情況下，必需再選中一個未訪問過的在這種情況下，必需再選中一個未訪問過的頂點，繼續進展深度優先搜索。直至一切的頂點，繼續進展深度優先搜索。直至一切的頂點都被訪問到為止。頂點都被訪問到為止。 這時，得到的是一組樹而

32、不是一棵樹，這一這時，得到的是一組樹而不是一棵樹，這一組樹被稱為深度優先生成森林。組樹被稱為深度優先生成森林。5672413從結點從結點1開場深度開場深度優先搜索優先搜索 1243567深度優先搜索的實現深度優先搜索的實現 深度優先搜索深度優先搜索DFSDFS的實現方法和樹的前序的實現方法和樹的前序遍歷算法類似，但必需對訪問過的頂點加遍歷算法類似，但必需對訪問過的頂點加以標志以標志 dfsdfs函數不需求參數，也沒有前往值。它函數不需求參數，也沒有前往值。它從編號最小的結點出發開場搜索，并將對從編號最小的結點出發開場搜索，并將對當前對象的深度優先搜索的序列顯示在顯當前對象的深度優先搜索的序列顯

33、示在顯示器上。示器上。深度優先搜索的實現深度優先搜索的實現 以鄰接表為例以鄰接表為例 設置一個數組設置一個數組visitedvisited，記錄節點能否被訪問過，記錄節點能否被訪問過 設計一個私有的深度優先搜索的函數，從某一節設計一個私有的深度優先搜索的函數，從某一節點出發訪問一切可達節點點出發訪問一切可達節點 假設是無向非連通圖的或有向非強連通，那么對假設是無向非連通圖的或有向非強連通，那么對圖中尚未訪問的節點反復調用深度優先搜索，構圖中尚未訪問的節點反復調用深度優先搜索，構成深度優先搜索的森林。成深度優先搜索的森林。公有的公有的dfs函數函數void dfs( ) 對每個節點對每個節點 v

34、 visited v = false; while (v = 尚未訪問的節點尚未訪問的節點 dfs(v，visited); template void adjListGraph:dfs() constbool *visited = new boolVers; for (int i=0; i Vers; +i) visitedi = false; cout 當前圖的深度優先遍歷序列為：當前圖的深度優先遍歷序列為： endl; for (i = 0; i Vers; +i) if (visitedi = true) continue; dfs(i, visited); cout endl; 私有的

35、私有的dfsvoid dfs( v，visited ) visitedv = true; for 每個每個 v的鄰接點的鄰接點w if( ! Visitedw ) dfs( w,visited );訪問從結點訪問從結點v出發可以訪問到的一切結點出發可以訪問到的一切結點 template void adjListGraph:dfs (int start, bool visited) const edgeNode *p = verListstart.head; cout verListstart.ver end = false) dfs(p-end, visited); p = p-next; 5

36、672413對圖調用對圖調用dfs結果為：結果為：當前圖的深度優先搜索序列為：當前圖的深度優先搜索序列為：1 2 4 36 7即對應于左圖的即對應于左圖的深度優先生成森林深度優先生成森林1243567時間性能分析時間性能分析 dfsdfs函數將對一切的頂點和邊進展訪問，函數將對一切的頂點和邊進展訪問，因此它的時間代價和頂點數因此它的時間代價和頂點數 |V| |V| 及邊數及邊數 |E| |E| 是相關的，即是是相關的，即是O(|V|+|E|)O(|V|+|E|)。 假設圖是用鄰接矩陣來表示，那么所需假設圖是用鄰接矩陣來表示，那么所需求的時間是求的時間是O O|V|2|V|2。圖的遍歷圖的遍歷

37、深度優先搜索深度優先搜索 廣度優先搜索廣度優先搜索對有向圖和無向圖進展遍歷是按照某種次序系統地對有向圖和無向圖進展遍歷是按照某種次序系統地訪問圖中的一切頂點，并且使得每個頂點只能被訪訪問圖中的一切頂點，并且使得每個頂點只能被訪問一次。在圖中某個頂點能夠和圖中的多個頂點鄰問一次。在圖中某個頂點能夠和圖中的多個頂點鄰接并且存在回路，因此在圖中訪問一個頂點接并且存在回路，因此在圖中訪問一個頂點u u之后，之后，在以后的訪問過程中，又能夠再次前往到頂點在以后的訪問過程中，又能夠再次前往到頂點u u，所，所以圖的遍歷要比樹的遍歷更復雜以圖的遍歷要比樹的遍歷更復雜廣度優先搜索廣度優先搜索 BFS 1 1、

38、選中第一個被訪問的頂點；、選中第一個被訪問的頂點；2 2、對頂點作已訪問過的標志；、對頂點作已訪問過的標志；3 3、依次訪問已訪問頂點的未被訪問過的第一個、第、依次訪問已訪問頂點的未被訪問過的第一個、第二個、第三個二個、第三個第第 m m 個鄰接頂點個鄰接頂點 W1 W1 、W2W2、W3 Wm W3 Wm ，進展訪問且進展標志，轉向，進展訪問且進展標志，轉向3 3；4 4、假設還有頂點未被訪問，那么選中一個起始頂點，、假設還有頂點未被訪問，那么選中一個起始頂點，轉向轉向2 2；5 5、一切的頂點都被訪問到，那么終了。、一切的頂點都被訪問到，那么終了。 廣度優先搜索類似于樹的從樹根出發的按照層

39、次的遍廣度優先搜索類似于樹的從樹根出發的按照層次的遍歷。它的訪問方式如下：歷。它的訪問方式如下：5672413按照頂點序號小的先按照頂點序號小的先訪問，序號大的后訪訪問，序號大的后訪問的原那么，那么它問的原那么，那么它的廣度優先訪問序列的廣度優先訪問序列為：為：1，2，4，3，5，6，7 。對應的廣度優。對應的廣度優先生成森林為先生成森林為1243567從不同的結點開場可以得到不同的搜索序列。例如，從不同的結點開場可以得到不同的搜索序列。例如，從從5開場廣度優先搜索這個圖，得到的遍歷序列為：開場廣度優先搜索這個圖，得到的遍歷序列為：5，6，7，2，4，3，1。 56724131243567廣度

40、優先搜索的實現廣度優先搜索的實現 需求記錄每個結點能否已被訪問需求記錄每個結點能否已被訪問 需求記住每個已被訪問的結點的后繼結點，然后依需求記住每個已被訪問的結點的后繼結點，然后依次訪問這些后繼結點。這可以用一個隊列來實現次訪問這些后繼結點。這可以用一個隊列來實現 過程：過程： 將序號最小的頂點放入隊列將序號最小的頂點放入隊列 反復取隊列的隊頭元素進展處置，直到隊列為空。反復取隊列的隊頭元素進展處置，直到隊列為空。對出隊的每個元素，首先檢查該元素能否已被訪問。對出隊的每個元素，首先檢查該元素能否已被訪問。假設沒有被訪問過，那么訪問該元素，并將它的一假設沒有被訪問過，那么訪問該元素，并將它的一切

41、的沒有被訪問過的后繼入隊切的沒有被訪問過的后繼入隊 檢查能否還有結點未被訪問。假設有，反復上述兩檢查能否還有結點未被訪問。假設有，反復上述兩個步驟個步驟template void adjListGraph:bfs() const bool *visited = new boolVers; int currentNode; linkQueue q; edgeNode *p; for (int i=0; i Vers; +i) visitedi = false; cout 當前圖的廣度優先遍歷序列為：當前圖的廣度優先遍歷序列為： endl; for (i = 0; i Vers; +i) if (

42、visitedi = true) continue; q.enQueue(i); while (!q.isEmpty() currentNode = q.deQueue(); if (visitedcurrentNode = true) continue; cout verListcurrentNode.ver end = false) q.enQueue(p-end); p = p-next; cout 4-3-5，那么此，那么此時，就無法訪問其他結點了時，就無法訪問其他結點了,由于由于5沒有其他的沒有其他的尚未被訪問的邊了。尚未被訪問的邊了。處理方法處理方法 找出途徑上的另外一個尚有未訪問

43、的邊找出途徑上的另外一個尚有未訪問的邊的頂點，開場另一次深度優先的搜索，的頂點，開場另一次深度優先的搜索，將得到的遍歷序列拼接到原來的序列中，將得到的遍歷序列拼接到原來的序列中，直到一切的邊都已被訪問。直到一切的邊都已被訪問。012345先找到先找到 5-4-3-5在途徑上找一個尚有邊未在途徑上找一個尚有邊未被訪問的結點，如：被訪問的結點，如：4，開場另一次深度優先遍歷。開場另一次深度優先遍歷。得到途徑得到途徑4-2-1-4將第二條途徑拼接到第一條途徑上，得到：將第二條途徑拼接到第一條途徑上，得到：5-4-2-1-4-3-53號結點還有未訪問的邊，從號結點還有未訪問的邊，從3號結點再開場一次深

44、號結點再開場一次深度優先遍歷，得到途徑度優先遍歷，得到途徑3-1-0-2-3將第三條途徑拼接到第一條途徑上，得到：將第三條途徑拼接到第一條途徑上，得到：5-4-2-1-4-3-1-0-2-3-5尋覓歐拉回路尋覓歐拉回路 檢查存在性檢查存在性 找出回路：找出回路： 執行一次深度優先的搜索。從起始結點開執行一次深度優先的搜索。從起始結點開場，沿著這條路不斷往下走，直到無路可場，沿著這條路不斷往下走，直到無路可走。而且在此過程中不允許回溯。走。而且在此過程中不允許回溯。 途徑上能否有一個尚有未訪問的邊的頂點。途徑上能否有一個尚有未訪問的邊的頂點。假設有，開場另一次深度優先的搜索，將假設有，開場另一次

45、深度優先的搜索，將得到的遍歷序列拼接到原來的序列中，直得到的遍歷序列拼接到原來的序列中，直到一切的邊都已被訪問。到一切的邊都已被訪問。歐拉回路的實現歐拉回路的實現 歐拉回路是由一段一段的途徑拼接起來的。為此，歐拉回路是由一段一段的途徑拼接起來的。為此，設計了一個私有的成員函數設計了一個私有的成員函數EulerCircuitEulerCircuit來獲得一來獲得一段途徑。公有的段途徑。公有的EulerCircuitEulerCircuit函數調用私有的函數調用私有的EulerCircuitEulerCircuit函數獲得一段段的途徑，并將它們拼函數獲得一段段的途徑，并將它們拼接起來，構成一條完好

46、的歐拉回路。接起來，構成一條完好的歐拉回路。 為了拼接方便起見，找到的歐拉回路被保管在一個為了拼接方便起見，找到的歐拉回路被保管在一個單鏈表中，單鏈表的結點類型為單鏈表中，單鏈表的結點類型為EulerNodeEulerNode。 EulerNodeEulerNode保管兩個內容：結點的編號和下一結點保管兩個內容：結點的編號和下一結點的指針。它被定義為鄰接表類的私有的內嵌類。的指針。它被定義為鄰接表類的私有的內嵌類。歐拉回路的實現歐拉回路的實現 續續 歐拉回路中，一條邊不能走兩遍。為此，歐拉回路中，一條邊不能走兩遍。為此，當一條邊被訪問以后，就將這條邊刪除當一條邊被訪問以后，就將這條邊刪除 Cl

47、oneClone函數創建一份鄰接表的拷貝，以便函數創建一份鄰接表的拷貝，以便在找完途徑后能恢復這個圖的鄰接表在找完途徑后能恢復這個圖的鄰接表公有的公有的EulerCircuitEulerCircuit函數函數template void adjListGraph:EulerCircuit (TypeOfVer start) EulerNode *beg, *end, *p, *q, *tb, *te; int numOfDegree; edgeNode *r; verNode *tmp; /檢查能否存在歐拉回路檢查能否存在歐拉回路 for (int i=0; inext; if (numOfDe

48、gree =0 | numOfDegree % 2) cout 不存在歐拉回路不存在歐拉回路 endl; return; /尋覓起始結點的編號尋覓起始結點的編號for (i = 0; iVers; +i) if (verListi.ver = start) break;if (i = Vers) cout 起始結點不存在起始結點不存在 next != NULL) if (verListp-next-NodeNum.head != NULL) break; else p = p-next; if (p-next = NULL) break; q = p-next; tb = EulerCircu

49、it(q-NodeNum, te); te-next =q-next; p-next = tb; delete q;/恢復原圖恢復原圖 delete verList; verList = tmp; /顯示得到的歐拉回路顯示得到的歐拉回路 cout 歐拉回路是：歐拉回路是： endl; while (beg !=NULL) cout NodeNum.ver next;delete p; cout endl;歐拉途徑中的結點類歐拉途徑中的結點類 struct EulerNodeint NodeNum;EulerNode *next;EulerNode(int ver) NodeNum = ver;

50、 next =NULL; clone函數的實現函數的實現 template adjListGraph:verNode * adjListGraph:clone( ) const verNode *tmp = new verNodeVers; edgeNode *p; for (int i = 0; i end, p-weight, tmpi.head);p = p-next; return tmp; 私有的私有的EulerCircuitEulerCircuit函數函數template adjListGraph:EulerNode *adjListGraph :EulerCircuit(int

51、start, EulerNode *&end)EulerNode *beg; int nextNode; beg = end = new EulerNode(start); while(verListstart.head != NULL) nextNode = verListstart.head-end; remove( start, nextNode); remove(nextNode, start); start = nextNode; end-next = new EulerNode(start); end = end-next; return beg;哈密爾頓回路問題哈密爾頓回

52、路問題 該回路經過圖的每一個結點一次，且僅該回路經過圖的每一個結點一次，且僅經過一次。經過一次。 一個圖能否存在哈密爾頓回路至今仍未一個圖能否存在哈密爾頓回路至今仍未找到滿足該問題的充要條件。找到滿足該問題的充要條件。 圖遍歷的運用圖遍歷的運用 無向圖的連通性無向圖的連通性 歐拉回路歐拉回路 有向圖的連通性有向圖的連通性 拓撲排序拓撲排序 對有向圖，深度優先搜索可以測試能否強連通，并對有向圖，深度優先搜索可以測試能否強連通，并找出一切強連通分量找出一切強連通分量 找強連通分量的方法找強連通分量的方法 從恣意節點開場深度優先遍歷從恣意節點開場深度優先遍歷G G。對森林中的每棵樹。對森林中的每棵樹

53、進展深度優先遍歷，并按遍歷的順序給每個節點編進展深度優先遍歷，并按遍歷的順序給每個節點編號號 將將G G的每條邊逆向，構成的每條邊逆向，構成GrGr。從編號最大的節點開場。從編號最大的節點開場深度優先遍歷深度優先遍歷GrGr。得到的深度優先遍歷森林的每棵。得到的深度優先遍歷森林的每棵樹就是樹就是G G的強連通分量。的強連通分量。有向圖的連通性有向圖的連通性ABDGHCJEIF從從B開場深度優先搜索開場深度優先搜索BEDAFCIHG10J978654321ABDGHCJEIFGrGIHJBACFDE因此，圖因此，圖G有有5個個強連通分量強連通分量圖遍歷的運用圖遍歷的運用 無向圖的連通性無向圖的連

54、通性 歐拉回路歐拉回路 有向圖的連通性有向圖的連通性 拓撲排序拓撲排序拓撲排序拓撲排序設設G=G=V V，E E是一個具有是一個具有n n個頂點的有向無個頂點的有向無環圖。環圖。V V中的頂點序列中的頂點序列V1V1，V2V2，VnVn稱為稱為一個拓撲序列，當且僅當該序列滿足以下一個拓撲序列，當且僅當該序列滿足以下條件：假設在條件：假設在G G中，從中，從ViVi到到VjVj有一條途徑，有一條途徑，那么序列中那么序列中ViVi必需排在必需排在VjVj的前面。的前面。下述集合下述集合 M M 代表課程的集合代表課程的集合1 1 代表數學，代表數學， 2 2 代表程序設計，代表程序設計，3 3 代

55、表離散數學，代表離散數學，4 4 代表匯編程序設計，代表匯編程序設計，5 5 代表數據構造，代表數據構造，6 6 代表構造化程序設計代表構造化程序設計, ,7 7 代表編譯原理代表編譯原理關系關系R R表示課程學習的先后關系，如數學必需在離表示課程學習的先后關系，如數學必需在離散數學之前學習。要求排一張學習的先后次序表。散數學之前學習。要求排一張學習的先后次序表。拓撲排序的運用拓撲排序的運用1327564數學數學程序設計程序設計離散數學離散數學匯編程匯編程序設計序設計數據構造數據構造構造化程序設計構造化程序設計編譯原理編譯原理用有向圖表示關系用有向圖表示關系R R。節點集為課程。節點集為課程集

56、合。假設課程集合。假設課程i i和和j j有關系有關系R R，那么，那么有一條邊。有一條邊。可行的排課：可行的排課：方案方案1： 1，2，3，4，5，6，7方案方案2： 1，2，3，5，6，4，7方案方案3： 1，2，3，5，6，7，4。1327564數學數學程序設計程序設計離散數學離散數學匯編程序匯編程序設計設計數據構造數據構造構造化程序設計構造化程序設計編譯原理編譯原理找出拓撲排序的過程找出拓撲排序的過程 第一個輸出的結點序列中的第一個元素：第一個輸出的結點序列中的第一個元素： 必需無前驅，即入度為必需無前驅，即入度為0 0 后驅：必需等到它的前驅輸出之后才輸出。后驅：必需等到它的前驅輸出

57、之后才輸出。 無前驅及后件的結點：任何時候都可輸出。無前驅及后件的結點：任何時候都可輸出。 邏輯刪除法：當某個節點被輸出后，就作為邏輯刪除法：當某個節點被輸出后，就作為該節點被刪除。一切以該節點作為前驅的一該節點被刪除。一切以該節點作為前驅的一切節點的入度減切節點的入度減1 1。1327564數學數學0程序設計程序設計1離散數學離散數學1匯編程序匯編程序設計設計1數據構造數據構造2構造化程序設計構造化程序設計1編譯原理編譯原理30 00 00 01 11 11 1匯編程序匯編程序設計設計0 00 01 11 11 1構造化程構造化程序設計序設計0 01 12 22 2數據構造數據構造0 01

58、12 22 23 33 3編譯原理編譯原理0 00 01 1程序設計程序設計0 01 1離散數學離散數學0 0數學數學輸出：輸出：數學，數學， 離散數學，離散數學，程序設計，程序設計，數據構造，數據構造，構造化程序設計，構造化程序設計，編譯原理，編譯原理，匯編程序設計匯編程序設計拓撲排序的實現拓撲排序的實現 計算每個結點的入度，保管在數組計算每個結點的入度，保管在數組inDegreeinDegree中；中； 檢查檢查inDegreeinDegree中的每個元素，將入度為中的每個元素，將入度為0 0的結的結點入隊；點入隊； 不斷從隊列中將入度為不斷從隊列中將入度為0 0的結點出隊，輸出此的結點出

59、隊，輸出此結點，并將該結點的后繼結點的入度減結點，并將該結點的后繼結點的入度減1 1；假；假設某個鄰接點的入度為設某個鄰接點的入度為0 0，那么將其入隊。，那么將其入隊。 template void adjListGraph:topSort( ) const linkQueue q; edgeNode *p; int current, *inDegree = new intVers; for (int i = 0; i Vers; +i) inDegreei = 0; for ( i = 0; i next) +inDegreep-end; for (i = 0; i Vers; +i) if

60、 (inDegreei = 0) q.enQueue(i); cout 拓撲排序為：拓撲排序為： endl; while( !q.isEmpty( ) ) current = q.deQueue( ); cout verListcurrent.ver next) if( -inDegreep-end = 0 ) q.enQueue( p-end ); cout endl; 時間復雜度時間復雜度 假設圖以鄰接表表示假設圖以鄰接表表示 計算入度需求計算入度需求O|V|+|E|的時間，搜索入度的時間，搜索入度為為0的結點需求的結點需求O|V|的時間。每個結點入的時間。每個結點入一次隊、出一次隊。每出一次隊，需求檢查它一次隊、出一