數(shù)據(jù)結(jié)構(gòu)_第四部分ppt課件

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

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

3、 E = A，B， A，C， B，D， B, E) , D，E， C，E 無向圖無向圖 1 243 56 6 1 6 5 55 6 3 4 2 1 243 56 6 1 6 5 55 6 3 4 2 加權(quán)圖中邊的表示：加權(quán)圖中邊的表示：或或(Vi, Vj, W) 加權(quán)圖加權(quán)圖 第第12章章 圖的根本概念圖的根本概念 圖的定義圖的定義 圖的術(shù)語圖的術(shù)語 圖的運(yùn)算圖的運(yùn)算 圖的存儲圖的存儲 圖的遍歷圖的遍歷 圖遍歷的運(yùn)用圖遍歷的運(yùn)用 圖的根本術(shù)語圖的根本術(shù)語 鄰接：如鄰接：如ViVi，VjVj是圖中的一條邊，那么稱是圖中的一條邊，那么稱 ViVi和和VjVj是鄰接的。如是鄰接的。如ViVj是圖中的

4、一條邊，是圖中的一條邊， 那么稱那么稱ViVi鄰接到鄰接到VjVj，或，或VjVj和和ViVi鄰接。鄰接。 度：無向圖中鄰接于某一結(jié)點(diǎn)的邊的總數(shù)。度：無向圖中鄰接于某一結(jié)點(diǎn)的邊的總數(shù)。 入度：有向圖中進(jìn)入某一結(jié)點(diǎn)的邊數(shù)，稱為該入度：有向圖中進(jìn)入某一結(jié)點(diǎn)的邊數(shù)，稱為該 結(jié)點(diǎn)的入度結(jié)點(diǎn)的入度 出度：有向圖中分開某一結(jié)點(diǎn)的邊數(shù)，稱為該出度：有向圖中分開某一結(jié)點(diǎn)的邊數(shù)，稱為該 結(jié)點(diǎn)的出度結(jié)點(diǎn)的出度 子圖子圖 AB CD A C AB CD 有向圖有向圖G1的子圖的子圖 AB CD 有向圖有向圖 G1 設(shè)有兩個圖設(shè)有兩個圖G=G=V V，E E和和G G= =V V，E E，假設(shè)，假設(shè) EEVV,那么稱

5、那么稱G G是是G G的子圖的子圖 無向圖無向圖 G2 AB CD E AB D E A AB CD AB CD E 無向圖無向圖G2的子圖的子圖 途徑和途徑長度途徑和途徑長度 對對1iN1iN，結(jié)點(diǎn)序列，結(jié)點(diǎn)序列w1,w2,wN w1,w2,wN 中的結(jié)點(diǎn)對中的結(jié)點(diǎn)對wi, wi, wi+1wi+1都有都有wi, wi+1wi, wi+1 E E或或 E E， 那么，那么，w1,w2,wNw1,w2,wN是圖中的一條途徑。是圖中的一條途徑。 非加權(quán)的途徑長度就是組成途徑的邊數(shù)，對于途徑非加權(quán)的途徑長度就是組成途徑的邊數(shù)，對于途徑 w1,w2,wNw1,w2,wN，非加權(quán)途徑長度為，非加權(quán)途徑

6、長度為N-1N-1。 加權(quán)途徑長度是指途徑上一切邊的權(quán)值之和。加權(quán)途徑長度是指途徑上一切邊的權(quán)值之和。 簡單途徑和環(huán)：假設(shè)一條途徑上的一切結(jié)點(diǎn)，除了簡單途徑和環(huán)：假設(shè)一條途徑上的一切結(jié)點(diǎn)，除了 起始結(jié)點(diǎn)和終止結(jié)點(diǎn)能夠一樣外，其他的結(jié)點(diǎn)都不起始結(jié)點(diǎn)和終止結(jié)點(diǎn)能夠一樣外，其他的結(jié)點(diǎn)都不 一樣，那么稱其為簡單途徑。一個回路或環(huán)是一條一樣，那么稱其為簡單途徑。一個回路或環(huán)是一條 簡單途徑，其起始結(jié)點(diǎn)和終止結(jié)點(diǎn)一樣，且途徑長簡單途徑，其起始結(jié)點(diǎn)和終止結(jié)點(diǎn)一樣，且途徑長 度至少為度至少為1 1。 無向圖的連通性無向圖的連通性 連通：頂點(diǎn)連通：頂點(diǎn)v v至至v v 之間有途徑存在之間有途徑存在 連通圖：無向

7、圖連通圖：無向圖 G G 的恣意兩點(diǎn)之間都是的恣意兩點(diǎn)之間都是 連通的，那么稱連通的，那么稱 G G 是連通圖。是連通圖。 連通分量：非連通圖中的極大連通子圖連通分量：非連通圖中的極大連通子圖 AB CD EFG IJ L H M K AB CD E H M FG JI LK 無向圖無向圖G 無向圖無向圖G的三個連通分量的三個連通分量 有向圖的連通性有向圖的連通性 強(qiáng)連通圖：有向圖強(qiáng)連通圖：有向圖 G G 的恣意兩點(diǎn)之間都是的恣意兩點(diǎn)之間都是 連通的，那么稱連通的，那么稱 G G 是強(qiáng)連通圖。是強(qiáng)連通圖。 強(qiáng)連通分量：極大連通子圖強(qiáng)連通分量：極大連通子圖 弱連通圖：如有向圖弱連通圖：如有向圖G

8、 G不是強(qiáng)連通的，但假不是強(qiáng)連通的，但假 設(shè)把它看成是無向圖時是連通的，那么稱設(shè)把它看成是無向圖時是連通的，那么稱 該圖是弱連通的該圖是弱連通的 有向圖有向圖G 有向圖有向圖G G的兩個強(qiáng)連通分量的兩個強(qiáng)連通分量 AB CD AB CD 不是強(qiáng)連通圖。由于不是強(qiáng)連通圖。由于B B 到其他結(jié)點(diǎn)都沒有途到其他結(jié)點(diǎn)都沒有途 徑。但此圖是弱連通徑。但此圖是弱連通 的。的。 完全圖完全圖 完全圖：每兩個節(jié)點(diǎn)之間都有邊的無完全圖：每兩個節(jié)點(diǎn)之間都有邊的無 向圖稱為完全圖。完全圖有向圖稱為完全圖。完全圖有 n(n-1)/2 n(n-1)/2 條邊的無向圖。其中條邊的無向圖。其中 n n 是結(jié)點(diǎn)個數(shù)。是結(jié)點(diǎn)個

9、數(shù)。 即即 有向完全圖：每兩個節(jié)點(diǎn)之間都有兩有向完全圖：每兩個節(jié)點(diǎn)之間都有兩 條弧的有向圖稱為有向完全圖。有向條弧的有向圖稱為有向完全圖。有向 完全圖有完全圖有 n(n-1) n(n-1) 條邊。其中條邊。其中 n n 是結(jié)是結(jié) 點(diǎn)個數(shù)。即點(diǎn)個數(shù)。即 假設(shè)一個有向圖中沒有環(huán)，那么稱為假設(shè)一個有向圖中沒有環(huán)，那么稱為 有向無環(huán)圖，簡寫為有向無環(huán)圖，簡寫為DAGDAG 2 n C 2 2 n C AB CD 無向完全圖無向完全圖 生成樹生成樹 AB CD E H M AB CD E H M 無向圖無向圖G 無向圖無向圖G的生成樹的生成樹 生成樹是連通圖的極小連通子圖。包含圖的一生成樹是連通圖的極小

10、連通子圖。包含圖的一 切切 n n 個結(jié)點(diǎn)，但只含圖的個結(jié)點(diǎn)，但只含圖的 n-1 n-1 條邊。在生成條邊。在生成 樹中添加一條邊之后，必定會構(gòu)成回路或環(huán)。樹中添加一條邊之后，必定會構(gòu)成回路或環(huán)。 第第12章章 圖的根本概念圖的根本概念 圖的定義圖的定義 圖的術(shù)語圖的術(shù)語 圖的運(yùn)算圖的運(yùn)算 圖的存儲圖的存儲 圖的遍歷圖的遍歷 圖遍歷的運(yùn)用圖遍歷的運(yùn)用 圖的運(yùn)算圖的運(yùn)算 常規(guī)操作：常規(guī)操作： 構(gòu)造一個由假設(shè)干個結(jié)點(diǎn)、假設(shè)干條邊組構(gòu)造一個由假設(shè)干個結(jié)點(diǎn)、假設(shè)干條邊組 成的圖；成的圖； 判別兩個結(jié)點(diǎn)之間能否有邊存在；判別兩個結(jié)點(diǎn)之間能否有邊存在； 在圖中添加或刪除一條邊；在圖中添加或刪除一條邊； 前

11、往圖中的結(jié)點(diǎn)數(shù)或邊數(shù)；前往圖中的結(jié)點(diǎn)數(shù)或邊數(shù)； 按某種規(guī)那么遍歷圖中的一切結(jié)點(diǎn)。按某種規(guī)那么遍歷圖中的一切結(jié)點(diǎn)。 和運(yùn)用嚴(yán)密結(jié)合的運(yùn)算：和運(yùn)用嚴(yán)密結(jié)合的運(yùn)算： 拓?fù)渑判蛲負(fù)渑判?找最小生成樹找最小生成樹 找最短途徑等。找最短途徑等。 圖的籠統(tǒng)類圖的籠統(tǒng)類 template class graph public: 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

12、 numOfVer() const return Vers; virtual numOfEdge() const return Edges; protected: int Vers, Edges; ; 第第12章章 圖的根本概念圖的根本概念 圖的定義圖的定義 圖的術(shù)語圖的術(shù)語 圖的運(yùn)算圖的運(yùn)算 圖的存儲圖的存儲 圖的遍歷圖的遍歷 圖遍歷的運(yùn)用圖遍歷的運(yùn)用 圖的存儲圖的存儲 鄰接矩陣和加權(quán)鄰接矩陣鄰接矩陣和加權(quán)鄰接矩陣 鄰接表鄰接表 鄰接矩陣鄰接矩陣有向圖有向圖 設(shè)有向圖具有設(shè)有向圖具有 n n 個結(jié)點(diǎn)，那么用個結(jié)點(diǎn)，那么用 n n 行行 n n 列的布爾矩列的布爾矩 陣陣 A A 表示該有向圖

13、假設(shè)表示該有向圖假設(shè)i i 至至 j j 有一條有向邊有一條有向邊, , Ai,j = 1 ,Ai,j = 1 ,假設(shè)假設(shè) i i 至至 j j 沒有一條有向邊沒有一條有向邊,Ai,j ,Ai,j = 0 = 0 AB CD 表示成右圖矩陣表示成右圖矩陣 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 留意：留意： 出度出度: i: i行之和。入度行之和。入度: j: j列之和。列之和。 鄰接矩陣鄰接矩陣有向圖有向圖 AB CD 表示成右圖矩陣表示成右圖矩陣 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 在物理實(shí)現(xiàn)時的思索：分別用在物理實(shí)現(xiàn)時的思索：分別用 0

14、 0、1 1、2 2、3 3 分別標(biāo)識結(jié)分別標(biāo)識結(jié) 點(diǎn)點(diǎn)A A、B B、C C、D D。而將真正的數(shù)據(jù)字段之值放入一個一維數(shù)。而將真正的數(shù)據(jù)字段之值放入一個一維數(shù) 組之中。組之中。 0 1 2 3 0 1 2 3 DABC 0 1 2 3 鄰接矩陣鄰接矩陣無向圖無向圖 設(shè)無向圖具有設(shè)無向圖具有 n n 個結(jié)點(diǎn)，那么用個結(jié)點(diǎn)，那么用 n n 行行 n n 列的布爾矩陣列的布爾矩陣 A A 表示該無向圖；并且表示該無向圖；并且 Ai,j = 1 , Ai,j = 1 , 假設(shè)假設(shè)i i 至至 j j 有一條無有一條無 向邊；向邊；Ai,j = 0Ai,j = 0假設(shè)假設(shè) i i 至至 j j 沒有

15、一條無向邊沒有一條無向邊 表示成右圖矩陣表示成右圖矩陣 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 1 0 AB CD E 在物理實(shí)現(xiàn)時的思索，和前一頁的無向圖類似。在物理實(shí)現(xiàn)時的思索，和前一頁的無向圖類似。 留意：留意： 無向圖的鄰接矩陣是一個對稱矩陣無向圖的鄰接矩陣是一個對稱矩陣 i i 結(jié)點(diǎn)的度結(jié)點(diǎn)的度: i : i 行或行或 i i 列之和。列之和。 加權(quán)的鄰接矩陣加權(quán)的鄰接矩陣有向圖有向圖 設(shè)有向圖具有設(shè)有向圖具有 n n 個結(jié)點(diǎn)，那么用個結(jié)點(diǎn)，那么用 n n 行行 n n 列的矩陣列的矩陣 A A 表表 示該有向圖；示該有向圖； 假設(shè)

16、假設(shè)i i 至至 j j 有一條有向邊且它的權(quán)值為有一條有向邊且它的權(quán)值為a a ，那么，那么Ai,j = a Ai,j = a 。假設(shè)。假設(shè) i i 至至 j j 沒有一條有向邊。沒有一條有向邊。 那么那么Ai,j = Ai,j = 空空 或其它標(biāo)志或其它標(biāo)志 表示成右圖矩陣表示成右圖矩陣 a b b b a a AB CD a a ab b b 鄰接矩陣的特點(diǎn)鄰接矩陣的特點(diǎn) 優(yōu)點(diǎn)：判別恣意兩點(diǎn)之間能否有邊方便，優(yōu)點(diǎn)：判別恣意兩點(diǎn)之間能否有邊方便， 僅耗費(fèi)僅耗費(fèi) O(1) O(1) 時間。時間。 缺陷：即使缺陷：即使 n2 n2 條邊，也需內(nèi)存條邊，也需內(nèi)存 n2 n2 單元，太多單元，太多

17、; ; 僅讀入數(shù)據(jù)耗費(fèi)僅讀入數(shù)據(jù)耗費(fèi) O( n2 ) O( n2 ) 時間，太長。而大多數(shù)的圖的邊數(shù)遠(yuǎn)遠(yuǎn)時間，太長。而大多數(shù)的圖的邊數(shù)遠(yuǎn)遠(yuǎn) 小于小于n2n2。 鄰接矩陣類的定義鄰接矩陣類的定義 template class adjMatrixGraph:public graph public: adjMatrixGraph(int vSize, const TypeOfVer d, TypeOfEdge noEdgeFlag); bool insert(int u, int v, TypeOfEdge w); bool remove(int u, int v); bool exist(int

18、u, int v) const; adjMatrixGraph() ； private: TypeOfEdge *edge; /存放鄰接矩陣存放鄰接矩陣 TypeOfVer *ver; /存放結(jié)點(diǎn)值存放結(jié)點(diǎn)值 TypeOfEdge noEdge; /鄰接矩陣中的鄰接矩陣中的的表示值的表示值 ; 構(gòu)造函數(shù)構(gòu)造函數(shù) template adjMatrixGraph:adjMatrixGraph (int vSize, const TypeOfVer d, TypeOfEdge noEdgeFlag) int i, j; Vers = vSize; Edges = 0; noEdge = noEdge

19、Flag; /存放結(jié)點(diǎn)的數(shù)組的初始化存放結(jié)點(diǎn)的數(shù)組的初始化 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; edgeii = 0; 析構(gòu)函數(shù)析構(gòu)函數(shù) template adjMatrixGraph: adjMatrixGraph() delete ver

20、; for (int i=0; iVers; +i) delete edgei delete edge; Insert函數(shù)函數(shù) 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 true; Remove函數(shù)函數(shù) template bool adjMatrixGraph: remove(int u, int v

21、) if (u Vers -1 | v Vers -1) return false; if (edgeuv = noEdge) return false; edgeuv = noEdge; -Edges; return true; Exist函數(shù)函數(shù) template bool adjMatrixGraph: exist(int u, int v) const if (u Vers -1 | v Vers -1) return false; if (edgeuv = noEdge) return false; else return true; 圖的存儲圖的存儲 鄰接矩陣和加權(quán)鄰接矩陣鄰接矩陣

22、和加權(quán)鄰接矩陣 鄰接表鄰接表 鄰接表鄰接表 設(shè)有向圖或無向圖具有設(shè)有向圖或無向圖具有 n n 個結(jié)點(diǎn)，那么用結(jié)點(diǎn)表、個結(jié)點(diǎn)，那么用結(jié)點(diǎn)表、 邊表表示該有向圖或無向圖。邊表表示該有向圖或無向圖。 結(jié)點(diǎn)表：用數(shù)組或單鏈表的方式存放一切的結(jié)點(diǎn)值。結(jié)點(diǎn)表：用數(shù)組或單鏈表的方式存放一切的結(jié)點(diǎn)值。 假設(shè)結(jié)點(diǎn)數(shù)假設(shè)結(jié)點(diǎn)數(shù)n n知，那么采用數(shù)組方式，否那么應(yīng)采知，那么采用數(shù)組方式，否那么應(yīng)采 用單鏈表的方式。用單鏈表的方式。 邊表邊結(jié)點(diǎn)表：每條邊用一個結(jié)點(diǎn)進(jìn)展表示。邊表邊結(jié)點(diǎn)表：每條邊用一個結(jié)點(diǎn)進(jìn)展表示。 同一個結(jié)點(diǎn)出發(fā)的一切的邊構(gòu)成它的邊結(jié)點(diǎn)單鏈表。同一個結(jié)點(diǎn)出發(fā)的一切的邊構(gòu)成它的邊結(jié)點(diǎn)單鏈表。 AB CD

23、 無向圖無向圖 G2 AB CD E 有向圖有向圖 G1 0 1 2 3 dest link A B C D 12 0 3 data adj 1 2 data adj 0 3 0 4 1 4 2 3 A B 0 1 2 3 4 C D E 4 1 dest link 鄰接表的特點(diǎn)鄰接表的特點(diǎn) 鄰接表是圖的規(guī)范存儲方式鄰接表是圖的規(guī)范存儲方式 優(yōu)點(diǎn)：內(nèi)存優(yōu)點(diǎn)：內(nèi)存 結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù) 邊數(shù)，處置時間也是邊數(shù)，處置時間也是 結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù) 邊數(shù)，即為邊數(shù)，即為O(|V|+|E|)O(|V|+|E|)。 當(dāng)我們談及圖的線性算法時，普通指的是當(dāng)我們談及圖的線性算法時，普通指的是 O(|V|+|E|)O(|V|

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

25、ool remove(int u, int v); bool exist(int u, int v) const; adjListGraph() ; private: struct edgeNode /鄰接表中存儲邊的結(jié)點(diǎn)類鄰接表中存儲邊的結(jié)點(diǎn)類 int end; /終點(diǎn)編號終點(diǎn)編號 TypeOfEdge weight; /邊的權(quán)值邊的權(quán)值 edgeNode *next; edgeNode(int e, TypeOfEdge w, edgeNode *n = NULL) end = e; weight = w; next = n; ; struct verNode /保管頂點(diǎn)的數(shù)據(jù)元素類型保管

26、頂點(diǎn)的數(shù)據(jù)元素類型 TypeOfVer ver; /頂點(diǎn)值頂點(diǎn)值 edgeNode *head; /對應(yīng)的單鏈表的頭指針對應(yīng)的單鏈表的頭指針 verNode( edgeNode *h = NULL) head = h ; ; verNode *verList; ; 構(gòu)造函數(shù)構(gòu)造函數(shù) template adjListGraph: adjListGraph(int vSize, const TypeOfVer d) Vers = vSize; Edges = 0; verList = new verNodevSize; for (int i = 0; i Vers; +i) verListi.ve

27、r = di; 析構(gòu)函數(shù)析構(gòu)函數(shù) template adjListGraph:adjListGraph() int i; edgeNode *p; for (i = 0; i next; delete p; delete verList; Insert函數(shù)函數(shù) template bool adjListGraph: insert(int u, int v, TypeOfEdge w) verListu.head = new edgeNode(v, w, verListu.head ); +Edges; return true; Remove函數(shù)函數(shù) template bool adjListG

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

29、return true; Exist函數(shù)函數(shù) template bool adjListGraph: exist(int u, int v) const edgeNode *p = verListu.head; while (p !=NULL if (p = NULL) return false; else return true; 第第12章章 圖的根本概念圖的根本概念 圖的定義圖的定義 圖的術(shù)語圖的術(shù)語 圖的運(yùn)算圖的運(yùn)算 圖的存儲圖的存儲 圖的遍歷圖的遍歷 圖遍歷的運(yùn)用圖遍歷的運(yùn)用 圖的遍歷圖的遍歷 深度優(yōu)先搜索深度優(yōu)先搜索 廣度優(yōu)先搜索廣度優(yōu)先搜索 對有向圖和無向圖進(jìn)展遍歷是按照某種次序

30、系統(tǒng)地對有向圖和無向圖進(jìn)展遍歷是按照某種次序系統(tǒng)地 訪問圖中的一切頂點(diǎn)，并且使得每個頂點(diǎn)只能被訪訪問圖中的一切頂點(diǎn)，并且使得每個頂點(diǎn)只能被訪 問一次。在圖中某個頂點(diǎn)能夠和圖中的多個頂點(diǎn)鄰問一次。在圖中某個頂點(diǎn)能夠和圖中的多個頂點(diǎn)鄰 接并且存在回路，因此在圖中訪問一個頂點(diǎn)接并且存在回路，因此在圖中訪問一個頂點(diǎn)u u之后，之后， 在以后的訪問過程中，又能夠再次前往到頂點(diǎn)在以后的訪問過程中，又能夠再次前往到頂點(diǎn)u u，所，所 以圖的遍歷要比樹的遍歷更復(fù)雜以圖的遍歷要比樹的遍歷更復(fù)雜 深度優(yōu)先搜索深度優(yōu)先搜索 1 1、選中第一個被訪問的頂點(diǎn)；、選中第一個被訪問的頂點(diǎn)； 2 2、對頂點(diǎn)作已訪問過的標(biāo)志；

31、、對頂點(diǎn)作已訪問過的標(biāo)志； 3 3、依次從頂點(diǎn)的未被訪問過的第一個、第、依次從頂點(diǎn)的未被訪問過的第一個、第 二個、第三個二個、第三個 鄰接頂點(diǎn)出發(fā)，進(jìn)展深鄰接頂點(diǎn)出發(fā)，進(jìn)展深 度優(yōu)先搜索；度優(yōu)先搜索； 4 4、假設(shè)還有頂點(diǎn)未被訪問，那么選中一個、假設(shè)還有頂點(diǎn)未被訪問，那么選中一個 起始頂點(diǎn)，轉(zhuǎn)向起始頂點(diǎn)，轉(zhuǎn)向2 2； 5 5、一切的頂點(diǎn)都被訪問到，那么終了。、一切的頂點(diǎn)都被訪問到，那么終了。 5 6 7 2 4 1 3 從結(jié)點(diǎn)從結(jié)點(diǎn)5開場進(jìn)展深度優(yōu)先的開場進(jìn)展深度優(yōu)先的 搜索，那么遍歷序列可以為：搜索，那么遍歷序列可以為： 5，7，6，2，4，3，1， 也可以為：也可以為： 5，6，2，3，1

32、，4，7。 深度優(yōu)先生成樹深度優(yōu)先生成樹 5 6 7 2 3 1 4 5 67 2 3 1 4 深度優(yōu)先生成森林深度優(yōu)先生成森林 在進(jìn)展深度優(yōu)先搜索在進(jìn)展深度優(yōu)先搜索 DFS DFS 時，有時并不一時，有時并不一 定可以保證從某一個結(jié)點(diǎn)出發(fā)能訪問到一切定可以保證從某一個結(jié)點(diǎn)出發(fā)能訪問到一切 的頂點(diǎn)的頂點(diǎn) 在這種情況下，必需再選中一個未訪問過的在這種情況下，必需再選中一個未訪問過的 頂點(diǎn)，繼續(xù)進(jìn)展深度優(yōu)先搜索。直至一切的頂點(diǎn)，繼續(xù)進(jìn)展深度優(yōu)先搜索。直至一切的 頂點(diǎn)都被訪問到為止。頂點(diǎn)都被訪問到為止。 這時，得到的是一組樹而不是一棵樹，這一這時，得到的是一組樹而不是一棵樹，這一 組樹被稱為深度優(yōu)先

33、生成森林。組樹被稱為深度優(yōu)先生成森林。 5 6 7 2 4 1 3 從結(jié)點(diǎn)從結(jié)點(diǎn)1開場深度開場深度 優(yōu)先搜索優(yōu)先搜索 1 2 4 3 5 67 深度優(yōu)先搜索的實(shí)現(xiàn)深度優(yōu)先搜索的實(shí)現(xiàn) 深度優(yōu)先搜索深度優(yōu)先搜索DFSDFS的實(shí)現(xiàn)方法和樹的前序的實(shí)現(xiàn)方法和樹的前序 遍歷算法類似，但必需對訪問過的頂點(diǎn)加遍歷算法類似，但必需對訪問過的頂點(diǎn)加 以標(biāo)志以標(biāo)志 dfsdfs函數(shù)不需求參數(shù)，也沒有前往值。它函數(shù)不需求參數(shù)，也沒有前往值。它 從編號最小的結(jié)點(diǎn)出發(fā)開場搜索，并將對從編號最小的結(jié)點(diǎn)出發(fā)開場搜索，并將對 當(dāng)前對象的深度優(yōu)先搜索的序列顯示在顯當(dāng)前對象的深度優(yōu)先搜索的序列顯示在顯 示器上。示器上。 深度優(yōu)先

34、搜索的實(shí)現(xiàn)深度優(yōu)先搜索的實(shí)現(xiàn) 以鄰接表為例以鄰接表為例 設(shè)置一個數(shù)組設(shè)置一個數(shù)組visitedvisited，記錄節(jié)點(diǎn)能否被訪問過，記錄節(jié)點(diǎn)能否被訪問過 設(shè)計一個私有的深度優(yōu)先搜索的函數(shù)，從某一節(jié)設(shè)計一個私有的深度優(yōu)先搜索的函數(shù)，從某一節(jié) 點(diǎn)出發(fā)訪問一切可達(dá)節(jié)點(diǎn)點(diǎn)出發(fā)訪問一切可達(dá)節(jié)點(diǎn) 假設(shè)是無向非連通圖的或有向非強(qiáng)連通，那么對假設(shè)是無向非連通圖的或有向非強(qiáng)連通，那么對 圖中尚未訪問的節(jié)點(diǎn)反復(fù)調(diào)用深度優(yōu)先搜索，構(gòu)圖中尚未訪問的節(jié)點(diǎn)反復(fù)調(diào)用深度優(yōu)先搜索，構(gòu) 成深度優(yōu)先搜索的森林。成深度優(yōu)先搜索的森林。 公有的公有的dfs函數(shù)函數(shù) void dfs( ) 對每個節(jié)點(diǎn)對每個節(jié)點(diǎn) v visited v

35、 = false; while (v = 尚未訪問的節(jié)點(diǎn)尚未訪問的節(jié)點(diǎn) dfs(v，visited); template void adjListGraph:dfs() const bool *visited = new boolVers; for (int i=0; i Vers; +i) visitedi = false; cout 當(dāng)前圖的深度優(yōu)先遍歷序列為：當(dāng)前圖的深度優(yōu)先遍歷序列為： endl; for (i = 0; i Vers; +i) if (visitedi = true) continue; dfs(i, visited); cout endl; 私有的私有的dfs vo

36、id dfs( v，visited ) visitedv = true; for 每個每個 v的鄰接點(diǎn)的鄰接點(diǎn)w if( ! Visitedw ) dfs( w,visited ); 訪問從結(jié)點(diǎn)訪問從結(jié)點(diǎn)v出發(fā)可以訪問到的一切結(jié)點(diǎn)出發(fā)可以訪問到的一切結(jié)點(diǎn) 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 6 7 2

37、4 1 3 對圖調(diào)用對圖調(diào)用dfs 結(jié)果為：結(jié)果為： 當(dāng)前圖的深度優(yōu)先搜索序列為：當(dāng)前圖的深度優(yōu)先搜索序列為： 1 2 4 3 6 7 即對應(yīng)于左圖的即對應(yīng)于左圖的 深度優(yōu)先生成森林深度優(yōu)先生成森林 1 2 4 3 5 67 時間性能分析時間性能分析 dfsdfs函數(shù)將對一切的頂點(diǎn)和邊進(jìn)展訪問，函數(shù)將對一切的頂點(diǎn)和邊進(jìn)展訪問， 因此它的時間代價和頂點(diǎn)數(shù)因此它的時間代價和頂點(diǎn)數(shù) |V| |V| 及邊數(shù)及邊數(shù) |E| |E| 是相關(guān)的，即是是相關(guān)的，即是O(|V|+|E|)O(|V|+|E|)。 假設(shè)圖是用鄰接矩陣來表示，那么所需假設(shè)圖是用鄰接矩陣來表示，那么所需 求的時間是求的時間是O O|V|

38、2|V|2。 圖的遍歷圖的遍歷 深度優(yōu)先搜索深度優(yōu)先搜索 廣度優(yōu)先搜索廣度優(yōu)先搜索 對有向圖和無向圖進(jìn)展遍歷是按照某種次序系統(tǒng)地對有向圖和無向圖進(jìn)展遍歷是按照某種次序系統(tǒng)地 訪問圖中的一切頂點(diǎn)，并且使得每個頂點(diǎn)只能被訪訪問圖中的一切頂點(diǎn)，并且使得每個頂點(diǎn)只能被訪 問一次。在圖中某個頂點(diǎn)能夠和圖中的多個頂點(diǎn)鄰問一次。在圖中某個頂點(diǎn)能夠和圖中的多個頂點(diǎn)鄰 接并且存在回路，因此在圖中訪問一個頂點(diǎn)接并且存在回路，因此在圖中訪問一個頂點(diǎn)u u之后，之后， 在以后的訪問過程中，又能夠再次前往到頂點(diǎn)在以后的訪問過程中，又能夠再次前往到頂點(diǎn)u u，所，所 以圖的遍歷要比樹的遍歷更復(fù)雜以圖的遍歷要比樹的遍歷更復(fù)

39、雜 廣度優(yōu)先搜索廣度優(yōu)先搜索 BFS 1 1、選中第一個被訪問的頂點(diǎn)；、選中第一個被訪問的頂點(diǎn)； 2 2、對頂點(diǎn)作已訪問過的標(biāo)志；、對頂點(diǎn)作已訪問過的標(biāo)志； 3 3、依次訪問已訪問頂點(diǎn)的未被訪問過的第一個、第、依次訪問已訪問頂點(diǎn)的未被訪問過的第一個、第 二個、第三個二個、第三個第第 m m 個鄰接頂點(diǎn)個鄰接頂點(diǎn) W1 W1 、W2W2、 W3 Wm W3 Wm ，進(jìn)展訪問且進(jìn)展標(biāo)志，轉(zhuǎn)向，進(jìn)展訪問且進(jìn)展標(biāo)志，轉(zhuǎn)向3 3； 4 4、假設(shè)還有頂點(diǎn)未被訪問，那么選中一個起始頂點(diǎn)，、假設(shè)還有頂點(diǎn)未被訪問，那么選中一個起始頂點(diǎn)， 轉(zhuǎn)向轉(zhuǎn)向2 2； 5 5、一切的頂點(diǎn)都被訪問到，那么終了。、一切的頂點(diǎn)都被

40、訪問到，那么終了。 廣度優(yōu)先搜索類似于樹的從樹根出發(fā)的按照層次的遍廣度優(yōu)先搜索類似于樹的從樹根出發(fā)的按照層次的遍 歷。它的訪問方式如下：歷。它的訪問方式如下： 5 6 7 2 4 1 3 按照頂點(diǎn)序號小的先按照頂點(diǎn)序號小的先 訪問，序號大的后訪訪問，序號大的后訪 問的原那么，那么它問的原那么，那么它 的廣度優(yōu)先訪問序列的廣度優(yōu)先訪問序列 為：為：1，2，4，3，5， 6，7 。對應(yīng)的廣度優(yōu)。對應(yīng)的廣度優(yōu) 先生成森林為先生成森林為 1 2 4 3 5 67 從不同的結(jié)點(diǎn)開場可以得到不同的搜索序列。例如，從不同的結(jié)點(diǎn)開場可以得到不同的搜索序列。例如， 從從5開場廣度優(yōu)先搜索這個圖，得到的遍歷序列為

41、：開場廣度優(yōu)先搜索這個圖，得到的遍歷序列為：5， 6，7，2，4，3，1。 5 6 7 2 4 1 3 1 24 3 5 67 廣度優(yōu)先搜索的實(shí)現(xiàn)廣度優(yōu)先搜索的實(shí)現(xiàn) 需求記錄每個結(jié)點(diǎn)能否已被訪問需求記錄每個結(jié)點(diǎn)能否已被訪問 需求記住每個已被訪問的結(jié)點(diǎn)的后繼結(jié)點(diǎn)，然后依需求記住每個已被訪問的結(jié)點(diǎn)的后繼結(jié)點(diǎn)，然后依 次訪問這些后繼結(jié)點(diǎn)。這可以用一個隊(duì)列來實(shí)現(xiàn)次訪問這些后繼結(jié)點(diǎn)。這可以用一個隊(duì)列來實(shí)現(xiàn) 過程：過程： 將序號最小的頂點(diǎn)放入隊(duì)列將序號最小的頂點(diǎn)放入隊(duì)列 反復(fù)取隊(duì)列的隊(duì)頭元素進(jìn)展處置，直到隊(duì)列為空。反復(fù)取隊(duì)列的隊(duì)頭元素進(jìn)展處置，直到隊(duì)列為空。 對出隊(duì)的每個元素，首先檢查該元素能否已被訪問。

42、對出隊(duì)的每個元素，首先檢查該元素能否已被訪問。 假設(shè)沒有被訪問過，那么訪問該元素，并將它的一假設(shè)沒有被訪問過，那么訪問該元素，并將它的一 切的沒有被訪問過的后繼入隊(duì)切的沒有被訪問過的后繼入隊(duì) 檢查能否還有結(jié)點(diǎn)未被訪問。假設(shè)有，反復(fù)上述兩檢查能否還有結(jié)點(diǎn)未被訪問。假設(shè)有，反復(fù)上述兩 個步驟個步驟 template void adjListGraph:bfs() const bool *visited = new boolVers; int currentNode; linkQueue q; edgeNode *p; for (int i=0; i Vers; +i) visitedi = fal

43、se; cout 當(dāng)前圖的廣度優(yōu)先遍歷序列為：當(dāng)前圖的廣度優(yōu)先遍歷序列為： endl; for (i = 0; i Vers; +i) if (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，那么此，那么此 時，就無法訪問其他

44、結(jié)點(diǎn)了時，就無法訪問其他結(jié)點(diǎn)了,由于由于5沒有其他的沒有其他的 尚未被訪問的邊了。尚未被訪問的邊了。 處理方法處理方法 找出途徑上的另外一個尚有未訪問的邊找出途徑上的另外一個尚有未訪問的邊 的頂點(diǎn)，開場另一次深度優(yōu)先的搜索，的頂點(diǎn)，開場另一次深度優(yōu)先的搜索， 將得到的遍歷序列拼接到原來的序列中，將得到的遍歷序列拼接到原來的序列中， 直到一切的邊都已被訪問。直到一切的邊都已被訪問。 0 12 3 4 5 先找到先找到 5-4-3-5 在途徑上找一個尚有邊未在途徑上找一個尚有邊未 被訪問的結(jié)點(diǎn)，如：被訪問的結(jié)點(diǎn)，如：4， 開場另一次深度優(yōu)先遍歷。開場另一次深度優(yōu)先遍歷。 得到途徑得到途徑4-2-1

45、-4 將第二條途徑拼接到第一條途徑上，得到：將第二條途徑拼接到第一條途徑上，得到： 5-4-2-1-4-3-5 3號結(jié)點(diǎn)還有未訪問的邊，從號結(jié)點(diǎn)還有未訪問的邊，從3號結(jié)點(diǎn)再開場一次深號結(jié)點(diǎn)再開場一次深 度優(yōu)先遍歷，得到途徑度優(yōu)先遍歷，得到途徑3-1-0-2-3 將第三條途徑拼接到第一條途徑上，得到：將第三條途徑拼接到第一條途徑上，得到： 5-4-2-1-4-3-1-0-2-3-5 尋覓歐拉回路尋覓歐拉回路 檢查存在性檢查存在性 找出回路：找出回路： 執(zhí)行一次深度優(yōu)先的搜索。從起始結(jié)點(diǎn)開執(zhí)行一次深度優(yōu)先的搜索。從起始結(jié)點(diǎn)開 場，沿著這條路不斷往下走，直到無路可場，沿著這條路不斷往下走，直到無路可

46、 走。而且在此過程中不允許回溯。走。而且在此過程中不允許回溯。 途徑上能否有一個尚有未訪問的邊的頂點(diǎn)。途徑上能否有一個尚有未訪問的邊的頂點(diǎn)。 假設(shè)有，開場另一次深度優(yōu)先的搜索，將假設(shè)有，開場另一次深度優(yōu)先的搜索，將 得到的遍歷序列拼接到原來的序列中，直得到的遍歷序列拼接到原來的序列中，直 到一切的邊都已被訪問。到一切的邊都已被訪問。 歐拉回路的實(shí)現(xiàn)歐拉回路的實(shí)現(xiàn) 歐拉回路是由一段一段的途徑拼接起來的。為此，歐拉回路是由一段一段的途徑拼接起來的。為此， 設(shè)計了一個私有的成員函數(shù)設(shè)計了一個私有的成員函數(shù)EulerCircuitEulerCircuit來獲得一來獲得一 段途徑。公有的段途徑。公有的E

47、ulerCircuitEulerCircuit函數(shù)調(diào)用私有的函數(shù)調(diào)用私有的 EulerCircuitEulerCircuit函數(shù)獲得一段段的途徑，并將它們拼函數(shù)獲得一段段的途徑，并將它們拼 接起來，構(gòu)成一條完好的歐拉回路。接起來，構(gòu)成一條完好的歐拉回路。 為了拼接方便起見，找到的歐拉回路被保管在一個為了拼接方便起見，找到的歐拉回路被保管在一個 單鏈表中，單鏈表的結(jié)點(diǎn)類型為單鏈表中，單鏈表的結(jié)點(diǎn)類型為EulerNodeEulerNode。 EulerNodeEulerNode保管兩個內(nèi)容：結(jié)點(diǎn)的編號和下一結(jié)點(diǎn)保管兩個內(nèi)容：結(jié)點(diǎn)的編號和下一結(jié)點(diǎn) 的指針。它被定義為鄰接表類的私有的內(nèi)嵌類。的指針。它

48、被定義為鄰接表類的私有的內(nèi)嵌類。 歐拉回路的實(shí)現(xiàn)歐拉回路的實(shí)現(xiàn) 續(xù)續(xù) 歐拉回路中，一條邊不能走兩遍。為此，歐拉回路中，一條邊不能走兩遍。為此， 當(dāng)一條邊被訪問以后，就將這條邊刪除當(dāng)一條邊被訪問以后，就將這條邊刪除 CloneClone函數(shù)創(chuàng)建一份鄰接表的拷貝，以便函數(shù)創(chuàng)建一份鄰接表的拷貝，以便 在找完途徑后能恢復(fù)這個圖的鄰接表在找完途徑后能恢復(fù)這個圖的鄰接表 公有的公有的EulerCircuitEulerCircuit函數(shù)函數(shù) template void adjListGraph:EulerCircuit (TypeOfVer start) EulerNode *beg, *end, *p,

49、*q, *tb, *te; int numOfDegree; edgeNode *r; verNode *tmp; /檢查能否存在歐拉回路檢查能否存在歐拉回路 for (int i=0; inext; if (numOfDegree =0 | numOfDegree % 2) cout 不存在歐拉回路不存在歐拉回路 endl; return; /尋覓起始結(jié)點(diǎn)的編號尋覓起始結(jié)點(diǎn)的編號 for (i = 0; iVers; +i) if (verListi.ver = start) break; if (i = Vers) cout 起始結(jié)點(diǎn)不存在起始結(jié)點(diǎn)不存在 next != NULL) if

50、(verListp-next-NodeNum.head != NULL) break; else p = p-next; if (p-next = NULL) break; q = p-next; tb = EulerCircuit(q-NodeNum, te); te-next =q-next; p-next = tb; delete q; /恢復(fù)原圖恢復(fù)原圖 delete verList; verList = tmp; /顯示得到的歐拉回路顯示得到的歐拉回路 cout 歐拉回路是：歐拉回路是： endl; while (beg !=NULL) cout NodeNum.ver next;

51、delete p; cout endl; 歐拉途徑中的結(jié)點(diǎn)類歐拉途徑中的結(jié)點(diǎn)類 struct EulerNode int NodeNum; EulerNode *next; EulerNode(int ver) NodeNum = ver; next =NULL; ; clone函數(shù)的實(shí)現(xiàn)函數(shù)的實(shí)現(xiàn) template adjListGraph:verNode * adjListGraph:clone( ) const verNode *tmp = new verNodeVers; edgeNode *p; for (int i = 0; i end, p-weight, tmpi.head);

52、 p = p-next; return tmp; 私有的私有的EulerCircuitEulerCircuit函數(shù)函數(shù) template adjListGraph:EulerNode *adjListGraph :EulerCircuit(int start, EulerNode * int nextNode; beg = end = new EulerNode(start); while(verListstart.head != NULL) nextNode = verListstart.head-end; remove( start, nextNode); remove(nextNode,

53、 start); start = nextNode; end-next = new EulerNode(start); end = end-next; return beg; 哈密爾頓回路問題哈密爾頓回路問題 該回路經(jīng)過圖的每一個結(jié)點(diǎn)一次，且僅該回路經(jīng)過圖的每一個結(jié)點(diǎn)一次，且僅 經(jīng)過一次。經(jīng)過一次。 一個圖能否存在哈密爾頓回路至今仍未一個圖能否存在哈密爾頓回路至今仍未 找到滿足該問題的充要條件。找到滿足該問題的充要條件。 圖遍歷的運(yùn)用圖遍歷的運(yùn)用 無向圖的連通性無向圖的連通性 歐拉回路歐拉回路 有向圖的連通性有向圖的連通性 拓?fù)渑判蛲負(fù)渑判?對有向圖，深度優(yōu)先搜索可以測試能否強(qiáng)連通，并對有向圖

54、，深度優(yōu)先搜索可以測試能否強(qiáng)連通，并 找出一切強(qiáng)連通分量找出一切強(qiáng)連通分量 找強(qiáng)連通分量的方法找強(qiáng)連通分量的方法 從恣意節(jié)點(diǎn)開場深度優(yōu)先遍歷從恣意節(jié)點(diǎn)開場深度優(yōu)先遍歷G G。對森林中的每棵樹。對森林中的每棵樹 進(jìn)展深度優(yōu)先遍歷，并按遍歷的順序給每個節(jié)點(diǎn)編進(jìn)展深度優(yōu)先遍歷，并按遍歷的順序給每個節(jié)點(diǎn)編 號號 將將G G的每條邊逆向，構(gòu)成的每條邊逆向，構(gòu)成GrGr。從編號最大的節(jié)點(diǎn)開場。從編號最大的節(jié)點(diǎn)開場 深度優(yōu)先遍歷深度優(yōu)先遍歷GrGr。得到的深度優(yōu)先遍歷森林的每棵。得到的深度優(yōu)先遍歷森林的每棵 樹就是樹就是G G的強(qiáng)連通分量。的強(qiáng)連通分量。 有向圖的連通性有向圖的連通性 AB D G H C

55、J E I F 從從B開場深度優(yōu)先搜索開場深度優(yōu)先搜索 B E D A F C I HG 10 J 9 7 8 6 54 3 2 1 AB D G H C J E I F Gr G I H J B A C F DE 因此，圖因此，圖G有有5個個 強(qiáng)連通分量強(qiáng)連通分量 圖遍歷的運(yùn)用圖遍歷的運(yùn)用 無向圖的連通性無向圖的連通性 歐拉回路歐拉回路 有向圖的連通性有向圖的連通性 拓?fù)渑判蛲負(fù)渑判?拓?fù)渑判蛲負(fù)渑判?設(shè)設(shè)G=G=V V，E E是一個具有是一個具有n n個頂點(diǎn)的有向無個頂點(diǎn)的有向無 環(huán)圖。環(huán)圖。V V中的頂點(diǎn)序列中的頂點(diǎn)序列V1V1，V2V2，VnVn稱為稱為 一個拓?fù)湫蛄?，?dāng)且僅當(dāng)該序列滿

56、足以下一個拓?fù)湫蛄?，?dāng)且僅當(dāng)該序列滿足以下 條件：假設(shè)在條件：假設(shè)在G G中，從中，從ViVi到到VjVj有一條途徑，有一條途徑， 那么序列中那么序列中ViVi必需排在必需排在VjVj的前面。的前面。 下述集合下述集合 M M 代表課程的集合代表課程的集合 1 1 代表數(shù)學(xué)，代表數(shù)學(xué)， 2 2 代表程序設(shè)計，代表程序設(shè)計， 3 3 代表離散數(shù)學(xué)，代表離散數(shù)學(xué)， 4 4 代表匯編程序設(shè)計，代表匯編程序設(shè)計， 5 5 代表數(shù)據(jù)構(gòu)造，代表數(shù)據(jù)構(gòu)造， 6 6 代表構(gòu)造化程序設(shè)計代表構(gòu)造化程序設(shè)計, , 7 7 代表編譯原理代表編譯原理 關(guān)系關(guān)系R R表示課程學(xué)習(xí)的先后關(guān)系，如數(shù)學(xué)必需在離表示課程學(xué)習(xí)的

57、先后關(guān)系，如數(shù)學(xué)必需在離 散數(shù)學(xué)之前學(xué)習(xí)。要求排一張學(xué)習(xí)的先后次序表。散數(shù)學(xué)之前學(xué)習(xí)。要求排一張學(xué)習(xí)的先后次序表。 拓?fù)渑判虻倪\(yùn)用拓?fù)渑判虻倪\(yùn)用 1 32 7 5 6 4 數(shù)學(xué)數(shù)學(xué) 程序設(shè)計程序設(shè)計 離散數(shù)學(xué)離散數(shù)學(xué) 匯編程匯編程 序設(shè)計序設(shè)計 數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造 構(gòu)造化程序設(shè)計構(gòu)造化程序設(shè)計 編譯原理編譯原理 用有向圖表示關(guān)系用有向圖表示關(guān)系 R R。節(jié)點(diǎn)集為課程。節(jié)點(diǎn)集為課程 集合。假設(shè)課程集合。假設(shè)課程i i 和和j j有關(guān)系有關(guān)系R R，那么，那么 有一條邊。有一條邊。 可行的排課：可行的排課： 方案方案1： 1，2，3，4，5，6，7 方案方案2： 1，2，3，5，6，4，7 方案方案

58、3： 1，2，3，5，6，7，4 。 1 32 7 5 6 4 數(shù)學(xué)數(shù)學(xué) 程序設(shè)計程序設(shè)計 離散數(shù)學(xué)離散數(shù)學(xué) 匯編程序匯編程序 設(shè)計設(shè)計 數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造 構(gòu)造化程序設(shè)計構(gòu)造化程序設(shè)計 編譯原理編譯原理 找出拓?fù)渑判虻倪^程找出拓?fù)渑判虻倪^程 第一個輸出的結(jié)點(diǎn)序列中的第一個元素：第一個輸出的結(jié)點(diǎn)序列中的第一個元素： 必需無前驅(qū)，即入度為必需無前驅(qū)，即入度為0 0 后驅(qū)：必需等到它的前驅(qū)輸出之后才輸出。后驅(qū)：必需等到它的前驅(qū)輸出之后才輸出。 無前驅(qū)及后件的結(jié)點(diǎn)：任何時候都可輸出。無前驅(qū)及后件的結(jié)點(diǎn)：任何時候都可輸出。 邏輯刪除法：當(dāng)某個節(jié)點(diǎn)被輸出后，就作為邏輯刪除法：當(dāng)某個節(jié)點(diǎn)被輸出后，就作為 該

59、節(jié)點(diǎn)被刪除。一切以該節(jié)點(diǎn)作為前驅(qū)的一該節(jié)點(diǎn)被刪除。一切以該節(jié)點(diǎn)作為前驅(qū)的一 切節(jié)點(diǎn)的入度減切節(jié)點(diǎn)的入度減1 1。 1 32 7 5 6 4 數(shù)學(xué)數(shù)學(xué)0 程序設(shè)計程序設(shè)計1 離散數(shù)學(xué)離散數(shù)學(xué)1 匯編程序匯編程序 設(shè)計設(shè)計1 數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造2 構(gòu)造化程序設(shè)計構(gòu)造化程序設(shè)計1 編譯原理編譯原理3 0 00 00 01 11 11 1匯編程序匯編程序 設(shè)計設(shè)計 0 00 01 11 11 1構(gòu)造化程構(gòu)造化程 序設(shè)計序設(shè)計 0 01 12 22 2數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造 0 01 12 22 23 33 3編譯原理編譯原理 0 00 01 1程序設(shè)計程序設(shè)計 0 01 1離散數(shù)學(xué)離散數(shù)學(xué) 0 0數(shù)學(xué)數(shù)學(xué) 輸

60、出：輸出： 數(shù)學(xué)，數(shù)學(xué)， 離散數(shù)學(xué)，離散數(shù)學(xué)，程序設(shè)計，程序設(shè)計， 數(shù)據(jù)構(gòu)造，數(shù)據(jù)構(gòu)造，構(gòu)造化程序設(shè)計，構(gòu)造化程序設(shè)計， 編譯原理，編譯原理，匯編程序設(shè)計匯編程序設(shè)計 拓?fù)渑判虻膶?shí)現(xiàn)拓?fù)渑判虻膶?shí)現(xiàn) 計算每個結(jié)點(diǎn)的入度，保管在數(shù)組計算每個結(jié)點(diǎn)的入度，保管在數(shù)組inDegreeinDegree 中；中； 檢查檢查inDegreeinDegree中的每個元素，將入度為中的每個元素，將入度為0 0的結(jié)的結(jié) 點(diǎn)入隊(duì)；點(diǎn)入隊(duì)； 不斷從隊(duì)列中將入度為不斷從隊(duì)列中將入度為0 0的結(jié)點(diǎn)出隊(duì)，輸出此的結(jié)點(diǎn)出隊(duì)，輸出此 結(jié)點(diǎn)，并將該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的入度減結(jié)點(diǎn)，并將該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的入度減1 1；假；假 設(shè)某個鄰接點(diǎn)