《《算法與數(shù)據(jù)結(jié)構(gòu)》第5章圖與網(wǎng)ppt.ppt》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第5章圖與網(wǎng)ppt.ppt（151頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、算法與數(shù)據(jù)結(jié)構(gòu),第5章 圖與網(wǎng),第5章 圖與網(wǎng),圖與網(wǎng)是更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間的關(guān)系既不是線性表中的一對一的鄰接關(guān)系，也不是樹型結(jié)構(gòu)中的一對多的層次關(guān)系，而是一種多對多的網(wǎng)狀關(guān)系，任意兩個數(shù)據(jù)元素之間都可能相關(guān)。 由于許多問題都可以用圖或網(wǎng)來表示，所以其應(yīng)用已滲透到語言學(xué)、邏輯學(xué)、物理、化學(xué)、電子、通訊、數(shù)學(xué)等諸多學(xué)科領(lǐng)域。,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念 5.2 圖與網(wǎng)的存儲結(jié)構(gòu) 5.3 圖的遍歷 5.4 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應(yīng)用,5.1 圖與網(wǎng)的基本概念,5.1.1 圖與網(wǎng)的定義 5.1.2 圖的相關(guān)術(shù)語,圖的定義,圖

2、（graph）是由非空的頂點集合V和描述頂點間關(guān)系的?。ɑ蜻叄┑募螮組成的二元組，即 G=(V，E) 其中： V=vi | vidataobject，E= | vi , vjV， dataobject是具有相同性質(zhì)的數(shù)據(jù)元素（即頂點）的集合； 表示從vi到vj有一條邊單向相連稱作弧，且稱vi為弧尾（起點），vj為弧頭（終點），此時稱圖為有向圖（digraph）。 若E，必有E，則可以用無序?qū)Γ╲i , vj）代替這兩個有序?qū)Γ磸膙i 到 vj有一條雙向邊（即無向邊，也可看作雙向邊）相連稱作邊，此時圖稱為無向圖（undigraph）。,圖的示例,G1=(V1，E1) 其中： V1=v1，v2

3、，v3，v4， E1=， ，；,G2=(V2，E2) 其中： V2=v1，v2，v3，v4，v5， E2=(v1，v2)，(v1，v4)， (v2，v3)，(v2，v5)， (v3，v4)，(v3，v5),圖的定義（續(xù)）,如果用n表示圖中頂點數(shù)目，用e表示邊或弧的數(shù)目，且不考慮頂點到自身的邊或弧，那么對于無向圖e的取值范圍是0到n(n-1)/2，而對于有向圖e的取值范圍為0到n(n-1)。 把具有n(n-1)/2條邊的無向圖稱為無向完全圖； 把具有n(n-1)條弧的有向圖稱為有向完全圖； 有向完全圖和無向完全圖統(tǒng)稱完全圖（completed graph）。 若圖中邊或弧的數(shù)目很少則稱為稀疏圖（

4、sparse graph），反之邊或弧的數(shù)目接近完全圖則稱為稠密圖（dense graph）。,子圖的定義,假設(shè)有兩個圖G=（V，E）和G=（V，E），如果V V且E E，則稱G是G的子圖（subgraph）。 子圖示例如下：,網(wǎng)的定義,把圖中與邊或弧相關(guān)的數(shù)稱之為權(quán)(weight)；權(quán)可以表示從一個頂點到另一個頂點的距離、時間、電流、電壓、耗費等， 通常把這種帶權(quán)圖稱作網(wǎng)（network）； 當(dāng)然也可以依據(jù)邊或弧有無向網(wǎng)和有向網(wǎng)的概念。 網(wǎng)的示例如下圖：,5.1 圖與網(wǎng)的基本概念,5.1.1 圖與網(wǎng)的定義 5.1.2 圖的相關(guān)術(shù)語,圖的相關(guān)術(shù)語,在無向圖中，某個頂點的度（degree）是指所

5、依附于該頂點的邊的數(shù)目，頂點v的度通常記作TD（V）。例如在無向圖G2中，TD（v1）=2，TD（v2）=3，TD（v3）=3，TD（v4）=2，TD（v5）=2。,在有向圖中要區(qū)別頂點的入度和出度的概念， 入度是指以頂點V為終點的弧的數(shù)目，通常記作ID(V)； 出度是指以頂點V為始點的弧的數(shù)目，通常記作OD(V)； 頂點的度定義為入度和出度的和，即: TD（V）=ID（V）+OD（V）。,圖的相關(guān)術(shù)語（續(xù)）,例如在有向圖G1中， ID（v1）=1，OD（v1）=2，TD（v1）=3； ID（v2）=1，OD（v2）=0，TD（v2）=1； ID（v3）=1，OD（v3）=1，TD（v3）=2

6、； ID（v4）=1，OD（v4）=1，TD（v4）=2。,一般地，對于具有n 個頂點e條邊或弧的圖，邊或弧的個數(shù)與各頂點的度TD（vi）之間滿足如下關(guān)系：,圖的相關(guān)術(shù)語（續(xù)）,在無向圖G=（V，E）中，若（vp，vi1），（vi1，vi2） （vin，vq）都是E中的邊，則稱結(jié)點序列vp，vi1，vi2 vin，vq為從vp到vq的一條路徑； 在有向圖中，則要求， 都是E中的弧。 路徑（path）長度定義為路徑上邊或弧的數(shù)目； 如有向圖G1中有，所以說從V3到V2存在一條長度為3的路徑； 如無向圖G2有(v1，v2)，(v2，v5)和(v1，v4)，(v4，v3)，(v3，v5)，所以說從V

7、1到V5存在一條長度各為2和3的路徑。,圖的相關(guān)術(shù)語（續(xù)）,如果頂點序列中不出現(xiàn)重復(fù)頂點，則稱頂點序列為簡單路徑，例如前面所舉三條路徑的頂點序列分別為v3、v4、v1、v2和v1、v2、v5與v1、v4、v3、v5，均無重復(fù)頂點出現(xiàn)都是簡單路徑。 第一個頂點和最后一個頂點相同（即vp =vq）的簡單路徑稱為簡單回路或環(huán)（cycle）， 例如在有向圖G1中的v1，v3，v4，v1和無向圖G2中的v1，v4，v3，v2，v1與v2，v3，v5，v2等都是簡單回路或環(huán)。,圖的相關(guān)術(shù)語（續(xù)）,在無向圖中，如果從一個頂點vi到另一個頂點vj 有路徑，則稱vi和vj是連通的；如果圖中任意兩個頂點vi和vj

8、都是連通的，則稱該無向圖是連通圖（connected graph）。例如無向圖G2是連通圖，,而如下無向圖G5是非連通圖。,圖的相關(guān)術(shù)語（續(xù)）,無向圖的極大連通子圖稱為圖的連通分量（connected component）。 例如下圖給出了無向圖G5的兩個連通分量。,圖的相關(guān)術(shù)語（續(xù)）,在有向圖中，如果對于任意兩個頂點vi和vj（vivj）從vi到vj和從vj到vi都存在路徑，則稱該有向圖為強(qiáng)連通圖（strong graph）。 有向圖的極大強(qiáng)連通子圖稱為圖的強(qiáng)連通分量（strongly connected component）。 例如有向圖G1不是強(qiáng)連通圖，它的兩個強(qiáng)連通分量如下圖所示。,圖

9、的相關(guān)術(shù)語（續(xù)）,一個連通圖的生成樹（spanning tree）是該圖的一個極小連通子圖，它包含圖中全部的n個頂點和連通這n個頂點的n-1條邊。 如果在生成樹上添加任意一條原圖中的其它邊必定會產(chǎn)生回路或環(huán)；換句話說，有n個頂點n條或n條以上邊的無向圖一定存在回路或環(huán)。如果n個頂點的圖其邊數(shù)少于n-1條，則一定是非連通圖。 例如無向圖G2的一棵生成樹如下圖所示。,圖的相關(guān)術(shù)語（續(xù)）,在非連通圖中，由每個連通分量都可以得到一個極小連通子圖，即一棵生成樹，這些連通分量的生成樹就構(gòu)成了該非連通圖的生成森林。 對于有向圖，其生成樹或生成森林必定是有向樹和有向森林。 例如無向圖G5的生成森林如下圖所示。

10、,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念 5.2 圖與網(wǎng)的存儲結(jié)構(gòu) 5.3 圖的遍歷 5.4 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應(yīng)用,圖和網(wǎng)的存儲結(jié)構(gòu),由于圖的結(jié)構(gòu)復(fù)雜，其數(shù)據(jù)元素間存在著多對多的網(wǎng)狀關(guān)系，所以無法用物理位置關(guān)系表示元素間的邏輯關(guān)系，即不存在順序存儲結(jié)構(gòu)； 但可借用數(shù)組來表示元素間的邏輯關(guān)系。由于圖中頂點的度差別一般較大，故也不宜采用多重鏈表存儲結(jié)構(gòu)； 但可根據(jù)圖的具體情況和需要進(jìn)行的操作，設(shè)計恰當(dāng)?shù)慕Y(jié)點結(jié)構(gòu)和表結(jié)構(gòu)來存儲頂點信息和頂點間的關(guān)系，,5.2 圖與網(wǎng)的存儲結(jié)構(gòu),5.2.1 鄰接矩陣 5.2.2 鄰接表與逆鄰接表 5.2.3 鄰

11、接多重表,鄰接矩陣,所謂鄰接矩陣（adjacency matrix）存儲結(jié)構(gòu)，就是用一維數(shù)組存儲圖或網(wǎng)的頂點信息，用二維數(shù)組表示頂點之間的鄰接關(guān)系（即鄰接矩陣）。 若G=（V，E）是具有n個頂點的圖或網(wǎng)，G的鄰接矩陣A是如下定義的n階方陣： 當(dāng)G是無向圖或有向圖時，矩陣A中元素定義為,鄰接矩陣（續(xù)）,當(dāng)G是無向網(wǎng)或有向網(wǎng)時，矩陣A中元素定義為 其中：Wij表示邊或弧上的權(quán)值，表示一個所用計算機(jī)上所允許的大于所有權(quán)值的數(shù)或者一個特殊的其它值。,鄰接矩陣存儲結(jié)構(gòu)舉例,鄰接矩陣存儲,鄰接矩陣存儲,鄰接矩陣存儲結(jié)構(gòu)舉例(續(xù)),鄰接矩陣存儲,鄰接矩陣存儲,鄰接矩陣存儲結(jié)構(gòu)的特點,從圖的鄰接矩陣存儲表示容

12、易看出該表示法具有如下特點： 無向圖或網(wǎng)的鄰接矩陣一定是一個對稱矩陣，因此在存儲鄰接矩陣時可以只存儲其上三角陣或下三角陣以節(jié)省存儲空間。 對于無向圖或網(wǎng)，其鄰接矩陣中第i行（或第i列）中非零元素（或非元素）的個數(shù)正好是第i個頂點的度。即,鄰接矩陣存儲結(jié)構(gòu)的特點(續(xù)),對于有向圖或網(wǎng)，其鄰接矩陣中第i行中非零元素（或非元素）的個數(shù)正好是第i個頂點的出度OD(vi)，而第i列中非零元素（或非元素）的個數(shù)正好是第i個頂點的入度ID(vi) 。即 很容易確定圖或網(wǎng)中任意兩個頂點之間是否有邊或弧相連；但要確定圖或網(wǎng)中有多少條邊或弧則需要逐行逐列掃描方陣，時間代價是O(n2)，這是該方法的局限性。,鄰接矩

13、陣存儲圖或網(wǎng)的類型定義,用一維數(shù)組存儲頂點信息，用鄰接矩陣存儲頂點間關(guān)系信息的圖或網(wǎng)的形式描述如下： #define maxvernum 100 #define infinity maxinteger typedef struct vertextype vexmaxvernum; int adjmatrixmaxvernummaxvernum; int n,e; /*定義頂點數(shù)和邊或弧數(shù)變量單元*/ mgraph;,5.2 圖與網(wǎng)的存儲結(jié)構(gòu),5.2.1 鄰接矩陣 5.2.2 鄰接表與逆鄰接表 5.2.3 鄰接多重表,鄰接表,鄰接表（adjacency list）是圖和網(wǎng)的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鄰

14、接表中，對圖或網(wǎng)中的每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點是與vi相關(guān)聯(lián)的邊所聯(lián)結(jié)的結(jié)點（對有向圖是以頂點vi為尾的弧所聯(lián)結(jié)的結(jié)點，即弧頭結(jié)點）。 每個結(jié)點由三個域組成，其中：鄰接點域adjvex指示與頂點vi鄰接的點在圖中的位置，鏈域next指示下一條邊或弧所聯(lián)結(jié)的結(jié)點，數(shù)據(jù)域info存儲和邊或弧相關(guān)的信息（如網(wǎng)中的權(quán)值等）。每個單鏈表都附設(shè)一個表頭結(jié)點，如下圖所示。,鄰接表（續(xù)）,除了設(shè)有鏈域next指向鏈表中的第一個結(jié)點外，還設(shè)有數(shù)據(jù)域data存放頂點vi的有關(guān)信息（如頂點名，頂點位置等）。 這些表頭結(jié)點也可以組織為一個鏈表，但通常以向量形式存儲于一維數(shù)組中，以方便隨機(jī)訪問任一頂點

15、的單鏈表。 例如有向網(wǎng)G3的鄰接表如下圖所示。,鄰接表舉例,無向網(wǎng)G4的鄰接表如下圖所示。,鄰接表中結(jié)點和表頭結(jié)點的形式描述,鄰接表中結(jié)點和表頭結(jié)點的形式描述定義如下： #define maxvernum 100 typedef struct node /*定義表結(jié)點結(jié)構(gòu)*/ int adjvex,info; struct node *next; nodetype; typedef struct frontnode /*定義表頭結(jié)點結(jié)構(gòu)*/ vertextype data; struct node *next; frontnodetype; typedef frontnodetype adjl

16、istmaxvernum;,鄰接表與逆鄰接表,若無向圖或網(wǎng)中有n個頂點e條邊，則它的鄰接表需n個表頭結(jié)點和2e個表結(jié)點。顯然在邊稀疏的情況下，用鄰接表比鄰接矩陣節(jié)省存儲空間，當(dāng)與邊相關(guān)的信息較多時更是如此。 在無向圖或網(wǎng)的鄰接表中，頂點vi的度恰為第i個鏈表中的結(jié)點數(shù)。在有向圖或網(wǎng)的鄰接表中，第i個鏈表中的結(jié)點數(shù)只是頂點vi的出度；為了求vi的入度，必須遍歷整個鄰接表，所有鄰接點域adjvex的值為i的結(jié)點個數(shù)是頂點vi的入度。 有時為了便于確定頂點的入度或以vi為頭的弧，可以建立逆鄰接表，即對vi建立一個鏈接以vi為頭的弧的表。 在鄰接表上，可以很方便地找到任一頂點的第一個鄰接點和下一個鄰接

17、點；但要判定任意兩個頂點vi和vj之間是否有邊或弧相連，則需要第i個或第j個單鏈表，在這一點上不及鄰接矩陣方便。,逆鄰接表舉例,有向網(wǎng)G3的逆鄰接表如下圖所示,5.2 圖與網(wǎng)的存儲結(jié)構(gòu),5.2.1 鄰接矩陣 5.2.2 鄰接表與逆鄰接表 5.2.3 鄰接多重表,鄰接多重表,鄰接多重表(adjacency multilist)是無向圖和網(wǎng)的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。 在鄰接表中，可以很方便地得到關(guān)于頂點和邊的有關(guān)信息；然而和一條邊(vi，vj)相關(guān)聯(lián)的兩個結(jié)點vi和vj分別存儲在第i和第j兩個單鏈表中，給無向圖或網(wǎng)的某些操作帶來不便。 例如，要對已搜索過的邊作記號或刪除一條邊等操作，需要找到表示同一條

18、邊的兩個結(jié)點。在對無向圖或網(wǎng)進(jìn)行這一類操作的問題中，宜采用下面將要介紹的鄰接多重表作存儲結(jié)構(gòu)。,鄰接多重表（續(xù)）,在鄰接多重表中，每一條邊用一個結(jié)點來表示，每個結(jié)點由五個或六個域組成，如下圖所示。 其中：mark為標(biāo)志域，可用來標(biāo)記該條邊是否已被搜索過；ivex和jvex為該邊所關(guān)聯(lián)的兩個頂點在圖中的位置或序號；ilink指向下一條依附于頂點ivex的邊，jlink指向下一條依附于頂點jvex的邊； 需要時還可增加一個存放和邊相關(guān)的各種信息的域info。,鄰接多重表（續(xù)）,無向圖或網(wǎng)中的每個頂點也用一個結(jié)點表示，它由存儲與該頂點相關(guān)的信息的域data和指示第一條依附于該頂點的邊的域firste

19、dge組成，如下圖所示。 在鄰接多重表中，所有依附于同一個頂點的邊都鏈接在同一個鏈表中；由于每一條邊都依附于兩個頂點，所以每一個邊結(jié)點都同時鏈接在兩個鏈表中。 由此可見，對于無向圖和無向網(wǎng)而言，其鄰接多重表和鄰接表的差別僅在于同一條邊在鄰接表中用兩個結(jié)點而在鄰接多重表中只用一個結(jié)點。 除了在邊結(jié)點中增加一個標(biāo)志域外，鄰接多重表所需的存儲量和鄰接表相同。在鄰接多重表中，各種基本操作的實現(xiàn)也和鄰接表相似。,鄰接多重表的邊結(jié)點和頂點結(jié)點的形式描述,鄰接多重表的邊結(jié)點和頂點結(jié)點的形式描述定義如下： typedef struct edgenode /*定義邊結(jié)點類型*/ int mark ,ivex ,

20、jvex; /*對于網(wǎng)可增加整型info域*/ struct edgenode *ilink,*jlink; edgenodetype ; typedef struct vexnode /*定義頂點結(jié)點類型*/ int data; struct edgenode *firstedge; vexnodetype; typedef vexnodetype adjmulistmaxvernum;,鄰接多重表舉例,鄰接多重表舉例（續(xù)）,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念 5.2 圖與網(wǎng)的存儲結(jié)構(gòu) 5.3 圖的遍歷 5.4 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應(yīng)

21、用,圖的遍歷,和樹的遍歷類似，圖的遍歷（traversing graph）是指從圖中的任一頂點出發(fā)訪問圖中所有頂點，且使每個頂點僅被訪問一次的過程。 然而由于圖結(jié)構(gòu)本身的復(fù)雜性，使得圖的遍歷比樹的遍歷復(fù)雜得多，主要表現(xiàn)在以下幾個方面： 圖中沒有一個惟一的開始結(jié)點，可以從任意一個頂點開始訪問； 從一個頂點出發(fā)只能訪問到它所在連通分量的各頂點，對于非連通圖還需考慮其它連通分量上頂點的訪問；,圖的遍歷（續(xù)）, 如果有回路存在，一個頂點被訪問之后又可能沿回路回到該頂點，為了避免對同一頂點的多次訪問，在遍歷過程中必須記下已訪問過的頂點，通常利用一維輔助數(shù)組記錄頂點被訪問的情況； 一個頂點可以和多個頂點相

22、鄰接，當(dāng)訪問過這個頂點之后如何選擇下一個要訪問的頂點。 圖的遍歷是圖的重要操作，對圖和網(wǎng)的許多操作都是建立在對圖的遍歷操作的基礎(chǔ)之上，如圖的連通性問題，拓?fù)渑判騿栴}等。通常有兩種遍歷圖的方法，即深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷，這兩種遍歷方法對無向圖和有向圖都適用。,5.3 圖的遍歷,5.3.1 深度優(yōu)先搜索遍歷 5.3.2 廣度優(yōu)先搜索遍歷 5.3.3 圖的遍歷應(yīng)用舉例 圖的連通性與生成樹,深度優(yōu)先搜索遍歷,圖的深度優(yōu)先搜索（depth-first search）遍歷類似于樹的先根次序遍歷，是樹的先根次序遍歷的推廣。 其遞歸定義如下： 從圖中某個頂點v0出發(fā)并訪問它； 依次從v0的未被訪問

23、的鄰接頂點出發(fā)深度優(yōu)先遍歷圖，直到圖中所有從v0出發(fā)有路徑可達(dá)的頂點都已被訪問到； 若圖中還有頂點未被訪問到，則另選一個未被訪問的頂點記作v0轉(zhuǎn)，否則圖的深度優(yōu)先遍歷結(jié)束。,深度優(yōu)先搜索遍歷（續(xù)）,在深度優(yōu)先搜索遍歷開始時，圖G的初始狀態(tài)是所有頂點都未曾被訪問： 首先從某一頂點v0出發(fā)并訪問它； 然后訪問與v0相鄰接的頂點vi，下一個要訪問的是與頂點vi相鄰接的尚未被訪問的頂點vj，再下一個是與vj相鄰接的尚未被訪問的頂點vk， 依此類推直到某個頂點所有的鄰接頂點都已被訪問過時達(dá)到最“深處”； 此時逐層回退到某個尚有鄰接頂點未被訪問的頂點vr，再從vr的一個未被訪問的鄰接頂點出發(fā)重復(fù)上述過程；

24、,深度優(yōu)先搜索遍歷（續(xù)）,直到圖中從v0出發(fā)有路徑可達(dá)的頂點都訪問到時，圖的一個連通分量深度優(yōu)先搜索遍歷結(jié)束， 對于非連通圖中的其它連通分量，還要繼續(xù)上述的深度優(yōu)先搜索遍歷過程，直到圖中所有頂點都被訪問過時止。,例如，對于右圖的無向圖G6的深度優(yōu)先搜索遍歷，若從v1出發(fā)結(jié)點的訪問順序為 v1v2v4v8v5v3v6v7,深度優(yōu)先搜索遍歷（續(xù)）,假設(shè)圖用鄰接表作存儲結(jié)構(gòu)，圖中n個頂點的表頭結(jié)點存入數(shù)組gn+1中，并用1到n作為標(biāo)識每一個頂點的序號，gi存放頂點vi的有關(guān)信息，v為給定的出發(fā)頂點序號。 為了在遍歷過程中區(qū)分頂點是否已被訪問過，設(shè)置標(biāo)志數(shù)組cn+1，初始值全為0，一旦頂點vi被訪問時

25、置ci為1。,深度優(yōu)先搜索遍歷（續(xù)）,從頂點v 出發(fā)按深度優(yōu)先搜索遍歷圖的遞歸算法dfs如下： void dfs(adjlist g,int v,int c) int i ; nodetype *p; cv=1; printf(“%dn”,v); /*訪問頂點v*/ for(p=gv.next;p!=NULL;p=p-next) i=p-adjvex; if(ci=0) dfs(g,i,c); ,深度優(yōu)先搜索遍歷（續(xù)）,對整個圖的遍歷算法travergraph如下： void travergraph(adjlist g ,int n ) int v; int cn+1; for(v=1;v=n

26、;v+) cv=0; /*標(biāo)志數(shù)組初始化*/ for(v=1;v=n;v+) if(cv=0) /*按深度優(yōu)先遍歷圖g*/ dfs(g,v,c); ,深度優(yōu)先搜索遍歷（續(xù)）,在遍歷時，對每個頂點至多調(diào)用一次dfs函數(shù)；因為一旦某個頂點被標(biāo)志為已被訪問，就不會再從它出發(fā)進(jìn)行搜索。 因此，遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程，其時間耗費取決于所采用的存儲結(jié)構(gòu)。 在上述以鄰接表作圖的存儲結(jié)構(gòu)時，找鄰接點所需時間為O(e)，e為無向圖的邊數(shù)或有向圖的弧數(shù)。由于在travergraph中需要O(n)的時間建立標(biāo)志數(shù)組，故深度優(yōu)先搜索遍歷圖的時間復(fù)雜度為O(n+e)。,5.3 圖的遍歷,5.3

27、.1 深度優(yōu)先搜索遍歷 5.3.2 廣度優(yōu)先搜索遍歷 5.3.3 圖的遍歷應(yīng)用舉例 圖的連通性與生成樹,廣度優(yōu)先搜索遍歷,廣度優(yōu)先搜索(broadth-first search)遍歷類似于樹的按層次遍歷，是樹的層次次序遍歷的推廣。 其定義如下： 從圖中某個頂點v0出發(fā)并訪問它； 依次訪問v0的各個未被訪問的鄰接頂點，然后分別從這些鄰接頂點出發(fā)依次訪問它們的鄰接頂點，并使先被訪問頂點的鄰接頂點先于后被訪問頂點的鄰接頂點，直到圖中已被訪問過的頂點的鄰接頂點都被訪問到； 若圖中還有頂點未被訪問到，則另選一個未被訪問的頂點記作v0轉(zhuǎn)，否則圖的廣度優(yōu)先遍歷結(jié)束。,廣度優(yōu)先搜索遍歷（續(xù)）,換句話說，圖的廣

28、度優(yōu)先搜索遍歷過程是：從v0出發(fā)由近及遠(yuǎn)依次訪問有路徑可達(dá)且路徑長度分別為1、2、3、的各頂點。,例如對右圖的無向圖G6進(jìn)行廣度優(yōu)先搜索遍歷； 從v1出發(fā)訪問v1，然后訪問v1的鄰接點v2和v3，緊接著訪問v2的鄰接點v4和v5，v3的鄰接點v6和v7，最后訪問v4的鄰接點v8。此時所有頂點均已被訪問過，圖G6的廣度優(yōu)先搜索遍歷完成，得到的廣度優(yōu)先搜索遍歷頂點序列為 v1v2v3v4v5v6v7v8,廣度優(yōu)先搜索遍歷（續(xù)）,由于先被訪問頂點的鄰接頂點先于后被訪問頂點的鄰接頂點被訪問，在廣度優(yōu)先搜索遍歷時應(yīng)設(shè)置隊列q存放已被訪問過的頂點以保證按層次依次訪問它們的鄰接頂點； 同時需要設(shè)置一個數(shù)組c

29、記錄頂點是否已被訪問的情況。 假定圖以鄰接表存儲，其它約定也和深度優(yōu)先搜索算法相同。,廣度優(yōu)先搜索遍歷（續(xù)）,圖的廣度優(yōu)先搜索算法bfs可描述如下： void bfs(adjlist g,int v,int c) int qN+1,r=0,f=0; nodetype *p; cv=1; printf(“%dn”,v); q0=v; while(fadjvex; if(cv=0) cv=1; printf(“%dn”,v); q+r=v; p=p-next; ,廣度優(yōu)先搜索遍歷（續(xù)）,在圖的廣度優(yōu)先搜索算法中，每個頂點至多進(jìn)一次隊列。 圖的遍歷過程實質(zhì)上是通過邊或弧找鄰接頂點的過程， 因此廣度優(yōu)

30、先搜索遍歷圖的時間復(fù)雜度和深度優(yōu)先搜索遍歷相同都為O(n+e)， 兩者的區(qū)別僅在于對頂點的訪問次序不同(即bfs和dfs的差別),5.3 圖的遍歷,5.3.1 深度優(yōu)先搜索遍歷 5.3.2 廣度優(yōu)先搜索遍歷 5.3.3 圖的遍歷應(yīng)用舉例 圖的連通性與生成樹,圖的連通性問題,對于無向圖G進(jìn)行遍歷時，若G是連通圖，僅需從圖中任一頂點v0出發(fā)進(jìn)行深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷訪問完圖中所有頂點； 若G是非連通圖，則需從多個頂點出發(fā)進(jìn)行搜索遍歷，每一次從一個未被訪問過的頂點出發(fā)，遍歷過程中訪問到它所在連通分量中的所有頂點。,例如對左圖的無向圖G2，從v1出發(fā)深度優(yōu)先搜索遍歷得到頂點序列v1v2v3

31、v4v5，訪問完所有頂點；,圖的連通性問題（續(xù)）,例如對右圖的無向圖G5，從A出發(fā)深度優(yōu)先搜索得到頂點序列ABDHGC只訪問完一個連通分量，還需再從E出發(fā)深度優(yōu)先搜索得到結(jié)點序列EF才訪問完所有結(jié)點。,圖的連通性問題（續(xù)）,由此，我們只要在算法travergraph中設(shè)置一個計數(shù)器變量count并賦初值為0，每調(diào)用一次dfs(或bfs)就給count加1，在算法執(zhí)行結(jié)束時就可依據(jù)count的值是否為1判定圖G 是否連通圖了； 同樣的道理，在travergraph算法中每次調(diào)用dfs(或bfs)之間設(shè)置輸出標(biāo)志，就可以區(qū)分非連通圖G的連通分量了。也就是說，利用圖的遍歷算法可以確定無向圖的連通性，

32、也可以求無向圖的連通分量。 同樣的道理，對于有向圖G進(jìn)行遍歷時，可利用travergraph算法判定有向圖G是否為強(qiáng)連通圖，也可以利用travergraph算法求有向圖G 的強(qiáng)連通分量。,生成樹,一個含有n個頂點的連通圖的生成樹，是圖的一個極小連通子圖，它包含圖中全部n個頂點和保證使任意兩個頂點連通所需的n-1條邊。 對于無向連通圖G=(V,E)，從任一頂點v0出發(fā)遍歷圖G時，必定將邊的集合E劃分為兩個集合E1和E2。 其中：E1為遍歷過程中所經(jīng)過的邊(不含回邊)的集合。E2為其余邊的集合。 由E1和頂點集合V一起構(gòu)成圖G的極小連通子圖，就是G的生成樹。 由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先

33、生成樹，由廣度優(yōu)先搜索遍歷得到的生成樹稱為廣度優(yōu)先生成樹。,生成樹舉例,由圖可見，連通圖的生成樹不惟一。從圖中的不同頂點出發(fā)，或者采用不同的遍歷方法，遍歷圖的過程中經(jīng)過的邊不同，得到的生成樹也就不同。,生成森林,對于非連通的無向圖，遍歷過程中得到幾棵生成樹；有幾個連通分量就有幾棵生成樹，即為生成森林。 和生成樹的道理一樣，生成森林也是不惟一的。 對于有向圖G進(jìn)行深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷，若有向圖G是強(qiáng)連通圖，則得到的是一棵深度優(yōu)先有向樹或一棵廣度優(yōu)先有向樹；若有向圖G是非強(qiáng)連通圖，則得到的是有向森林。,生成森林舉例,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念 5.2 圖與網(wǎng)的存儲結(jié)構(gòu)

34、5.3 圖的遍歷 5.4 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應(yīng)用,5.4 無向連通網(wǎng)的最小生成樹,5.4.1 最小生成樹的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,最小生成樹的概念,對于一個無向網(wǎng)（即帶權(quán)無向圖），生成樹上各邊權(quán)值之和稱為這棵生成樹的代價；最小代價生成樹是各邊權(quán)值總和最小的生成樹，簡稱最小生成樹(minimum spanning tree)。 例如下圖所示無向連通網(wǎng)G7和它的最小生成樹：,最小生成樹的應(yīng)用,最小生成樹有很多實際應(yīng)用。 例如要在n個城市之間建立通訊網(wǎng)，連通n個城市只需要n-1條線路；而每兩個城市之間都可以

35、設(shè)置一條線路，相應(yīng)地都要付出一定代價；n個城市之間最多可能設(shè)置n(n-1)/2條線路，如何在其中選擇n-1條以使總的耗費最少？即求通訊網(wǎng)的最小生成樹問題。 又如要在m個村莊之間修建公路，使這m個村莊村與村之間可達(dá)且總的修建費用最少；此問題是一個以村為頂點，以村與村直達(dá)公路為邊其修建費用為權(quán)的公路網(wǎng)求最小生成樹的問題。 一個無向連通網(wǎng)的最小生成樹也可能不是惟一的，但其總代價一定是最小的。,5.4 無向連通網(wǎng)的最小生成樹,5.4.1 最小生成樹的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,Prim算法,Prim算法是從連通網(wǎng)中的某一個頂點開始，以此作為生成樹的初始狀態(tài)，然后不斷

36、地將網(wǎng)中的其它頂點添加到生成樹上，直到最后一個頂點添加到生成樹上時得到最小生成樹。 其具體方法是： 從網(wǎng)中任一頂點開始，先把該頂點包含在生成樹中，此時生成樹只有一個頂點； 找出一個端點在生成樹中另一個端點在生成樹外的所有邊，并把權(quán)值最小的邊連同它所關(guān)聯(lián)的另一個頂點添加到生成樹中；當(dāng)有兩條及以上具有相同最小權(quán)值的邊可供選擇時，選擇其中任意一條都可以； 反復(fù)執(zhí)行，直到所有頂點都包含在生成樹中時止。,利用Prim算法構(gòu)造最小生成樹的過程,下圖給出了利用Prim算法從頂v1開始得到無向連通網(wǎng)G7的最小生成樹的過程：,Prim算法（續(xù)）,為了實現(xiàn)Prim算法，需設(shè)一個輔助數(shù)組closedge以記錄每次選

37、擇的權(quán)值最小的邊。 數(shù)組元素closedgei對應(yīng)于序號為i的頂點vi，它包含兩個域adjvex和lowcost。 若vi已在生成樹上，則置closedgei.lowcost=0； 若頂點vi不在生成樹上，用closedgei. lowcost存放vi與生成樹上的頂點構(gòu)成的最小代價邊的權(quán)值， 而用closedgei.adjvex存放該邊所關(guān)聯(lián)的生成樹上的另一頂點的序號。,Prim算法（續(xù)）,設(shè)有n個頂點的無向連通網(wǎng)以鄰接矩陣g存儲，從序號為k的頂點vk開始構(gòu)造最小生成樹，則輔助數(shù)組的初始情況為： closedgek.lowcost=0; closedgei.lowcost=g.adjmatri

38、xk,i (ik且1in) closedgei.adjvex=k; (ik且1in) 然后從數(shù)組中選出某一個j，它滿足closedgej.lowcost不等于0且是最小的值，將vj添加到生成樹上并修改closedge數(shù)組中的值。如此不斷進(jìn)行下去，直到全部的n個頂點都在生成樹上，就得到了要求的最小生成樹。,Prim算法的形式化描述,#define m 30 /*m為頂點的個數(shù)最大值*/ #define max 99 /*max為權(quán)的上限值*/ void prim(mgraph g,int k,int n) int i,j,min,p; struct int adjvex; int lowcost

39、; closedgem; for(i=1;i=n;i+) /*輔助數(shù)組初始化*/ if(i!=k) closedgei.adjvex=k; closedgei.lowcost=g.adjmatrixki; closedgek.lowcost=0;,Prim算法的形式化描述（續(xù)）,for(i=1;in;i+) p=1; min=max; for(j=1;j=n;j+) /*選最小權(quán)值及對應(yīng)頂點vp*/ if(closedgej.lowcost!=0 ,Prim算法的形式化描述（續(xù)）,for(j=1;j=n;j+) if(g.adjmatrixpjclosedgej.lowclst) closed

40、gej.lowcost=g.adjmatrixpj; closedgej.adjvex=p; /*選一條邊及對應(yīng)頂點結(jié)束*/ /*prim結(jié)束*/ 在該算法中有一個兩重循環(huán)，外層執(zhí)行n-1次，里層兩個并列循環(huán)各執(zhí)行n次。所以Prim算法與網(wǎng)中的邊數(shù)無關(guān)，其時間復(fù)雜度為O(n2)，適合于求邊稠密的網(wǎng)的最小生成樹。,在Prim算法中輔助數(shù)組中各分量值變化舉例,下表中給出了利用Prim算法求無向連通網(wǎng)G7從頂點v1出發(fā)生成樹的過程中輔助數(shù)組中各分量值的變化情況。,5.4 無向連通網(wǎng)的最小生成樹,5.4.1 最小生成樹的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,Kruskal算法

41、,Kruskal算法是求無向連通網(wǎng)的最小生成樹的另一種常用算法。它與Prim算法不同，時間復(fù)雜度主要與網(wǎng)中邊的條數(shù)e相關(guān)為O(eloge)，適合用于求邊稀疏的無向連通網(wǎng)的最小生成樹。 Kruskal算法的思想為： 將n個頂點看作是n個獨立的連通分量，將e條邊按權(quán)值大小由小到大排序； 從權(quán)值最小的邊開始依權(quán)值遞增順序查看每一條邊，如果該邊所依附的兩個頂點在不同的連通分量上，則選定此邊連接兩個連通分量為一個連通分量，否則舍棄此邊； 反復(fù)執(zhí)行，直到所有頂點都在同一個連通分量上為止，這個連通分量即為所求的最小生成樹。,利用Kruskal算法構(gòu)造最小生成樹的過程,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念

42、 5.2 圖與網(wǎng)的存儲結(jié)構(gòu) 5.3 圖的遍歷 5.4 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應(yīng)用,有向網(wǎng)的最短路徑,如果右圖中的G7表示一個已建成的公路交通網(wǎng)，頂點表示不同的村莊(或城鎮(zhèn))，邊表示村莊(或城鎮(zhèn))間的公路，邊上的權(quán)值表示公路的長度，從村莊(或城鎮(zhèn))v1到村莊(或城鎮(zhèn))v7走哪條路徑最短呢？,或者邊上的權(quán)值代表時間，走哪條路徑最快呢？或者邊上的權(quán)值代表乘車費用，走哪條路徑最省錢呢？如果在每個村莊(或城鎮(zhèn))都需要換乘車輛，走哪條路換乘次數(shù)最少呢？諸如此類問題，歸結(jié)起來就是一個求網(wǎng)中頂點之間最短路徑的問題，即要求路徑上邊的權(quán)值之和最小或邊的條數(shù)最少。,

43、有向網(wǎng)的最短路徑（續(xù)）,考慮到交通網(wǎng)的有向性，如公路的上坡和下坡、航運的順?biāo)湍嫠鋾r間等不一樣，這里討論有向網(wǎng)的最短路徑(shortest path)，并稱路徑上的第一個頂點為源點(sourse)，最后一個頂點為終點(destination)。 對于無向網(wǎng)的最短路徑問題，可以利用有向網(wǎng)求最短路徑的算法來求解，只不過把無向網(wǎng)中的一條邊看作兩條權(quán)值相等方向相反的弧罷了。,5.5 有向網(wǎng)的最短路徑,5.5.1 單源最短路徑 5.5.2 所有頂點對之間的最短路徑,單源最短路徑,所謂單源最短路徑，是指從一個頂點（源點）出發(fā)到其它各頂點的最短路徑，即給定有向網(wǎng)G和源點vk，求從vk到G 中其它各頂點vj

44、(j=1,2,n, jk)的最短路徑。 迪杰斯特拉(E.W.Dijkstra)提出了一種按路徑長度遞增的次序產(chǎn)生最短路徑的算法。 其基本思想是，把網(wǎng)中所有頂點分成兩組，第一組是已確定最短路徑的頂點集合S，第二組是尚未確定最短路徑的頂點集合V；把V中的頂點按最短路徑長度遞增的順序逐個添加到S中，添加過程中始終保持從vk到S中每個頂點的最短路徑長度都不大于從vk到V中任何頂點的最短路徑長度，直到從vk出發(fā)可以到達(dá)的頂點都在S中時止。,單源最短路徑（續(xù)）,一開始時，S中只有頂點vk，其余頂點在V中。 這里引入一維輔助數(shù)組dist，用disti表示在當(dāng)前時刻所找到的從源點vk到每個終點vi的最短路徑長

45、度；其初始值為：distk=0，若存在弧則disti為其弧上的權(quán)值，否則從vk到vi無弧時distk=。 然后每次從V中的頂點中選取一個dist值最小的頂點vj（distj=mindisti|viV）加入到S中；并對V中頂點的dist值進(jìn)行相應(yīng)修正，即若以加入S中的頂點vj做中間頂點使得V中某頂點的dist值更小時要相應(yīng)修改該頂點的dist值。這樣從V中選一個頂點加入S中，對V中頂點的dist值修改一遍，只需做n-1次就可求得從vk到其余各頂點的最短路徑。,單源最短路徑（續(xù)）,在求最短路徑的過程中，最短路徑長度已記在dist數(shù)組中，同時需要把路徑也記下來。 為此我們設(shè)一維數(shù)組pre，prei中

46、存放從vk到vi的路徑上vi前一個頂點的序號；若從vk到vi無路徑可達(dá)，則vi的前一個頂點序號用0表示（即prei=0）。 在算法結(jié)束時，沿著頂點vi對應(yīng)的prei向前追溯就能確定從vk到vi的最短路徑，其最短路徑長度為disti。 設(shè)有向網(wǎng)用鄰接矩陣a表示，ai,j表示弧上的權(quán)值，無弧時ai,j為max；ai,i=0，當(dāng)vi進(jìn)入S 中時用ai,i=1來標(biāo)識。,最短路徑的Dijkstra算法描述,求有向網(wǎng)中從頂點vk出發(fā)到其它各頂點的最短路徑的Dijkstra算法如下： void dijkstra(int a,int k,int pre,int dist,int n) int i,j,p,mi

47、n; for (i=1;i=n;i+) disti=aki; if (distimax) prei=k; else prei=0; prek=0; distk=0; akk=1;,最短路徑的Dijkstra算法描述(續(xù)),for (p=1;p=n-1;p+) min=max; j=-1; for(i=1;i=n;i+) /*在V中選dist最小的頂點*/ if (aii=0 /*dijkstra*/,最短路徑的Dijkstra算法舉例,最短路徑的Dijkstra算法舉例(續(xù)),使用Dijkstra算法對于前圖中所示的有向圖G8，求從頂點v1到其它各頂點的最短路徑及其算法執(zhí)行過程中dist數(shù)組和

48、pre數(shù)組的變化情況如下表所示。,最短路徑的Dijkstra算法舉例(續(xù)),各頂點進(jìn)入S中的順序為v1，v3，v5，v4，v6；最終v2仍留在V中未進(jìn)入S中，說明從v1沒有路徑到達(dá)v2。要求從v1到某個頂點vi的最短路徑，可由prei回溯得到。 例如求v1到v6的最短路徑，可由pre6=4，pre4=5，pre5=1得到最短路徑為v1v5v4v6，路徑長度為dist6=60。,5.5 有向網(wǎng)的最短路徑,5.5.1 單源最短路徑 5.5.2 所有頂點對之間的最短路徑,所有頂點對之間的最短路徑,求所有頂點對之間的最短路徑的顯而易見的方法是，每次以一個頂點為源點重復(fù)執(zhí)行Dijkstra算法n 次來求

49、得，總的執(zhí)行時間為O(n3)。 下面介紹的是由費洛伊德（E.W.Floyd）提出的另一個算法。該算法也是用鄰接矩陣a表示有向網(wǎng)，其時間復(fù)雜度也是O(n3)，但在形式上更簡單些。,Floyd算法的基本思想,Floyd算法的基本思想是： 從鄰接矩陣a開始進(jìn)行n次迭代，第一次迭代后ai,j的值是從vi到vj且中間不經(jīng)過編號大于1的頂點（即v2到vn）的最短路徑長度；第k次迭代后ai,j的值是從vi到vj且中間不經(jīng)過編號大于k的頂點（即vk+1到vn）的最短路徑長度；經(jīng)第n次迭代后ai,j的值就是從vi到vj的最短路徑長度。其迭代公式為： aki,j=minak-1i,j，ak-1i,k+ak-1k,

50、j 其中：1kn，迭代初值a0即為有向網(wǎng)的鄰接矩陣。 迭代公式的意義是，如果在第k次迭代時加入頂點vk后，存在從vi到vk和從vk到vj的兩條路徑，且長度之和小于迭代前從vi到vj的路徑長度，則更新為新路徑的值，否則保留原有的值。,迭代公式直觀地表示,迭代公式可以直觀地表示為下圖所示，圖中用波浪線表示一條路徑。,Floyd算法,為了實現(xiàn)Floyd算法，還需引入一個矩陣path。 pathi,j是從vi到vj的最短路徑上vj前一個頂點的序號，并約定從vi到vj無路徑時pathi,j=0。 在求得最短路徑后由pathi,j的值向前追溯，可以得到從vi到vj的最短路徑。,Floyd算法的形式化描述,

51、void floyd (int a,int p,int n) /*求有向網(wǎng)中所有頂點對之間的最短路徑*/ int i,j,k; for(i=1;i=n;i+) /*對path數(shù)組初始化，假定鄰接矩陣已存入a數(shù)組中*/ for(j=1;j=n;j+) if (i=j) pathij=0; else if(aijmax) pathij=i; else pathij=0; ,Floyd算法的形式化描述(續(xù)),for(k=1;k=n;k+) /*迭代求最短路徑及其長度*/ for(i=1;i=n;i+) for(j=1;j=n;j+) if(aik+akjaij) aij=aik+akj; pathi

52、j=pathkj; /*floyd*/,Floyd算法舉例,Floyd算法舉例(續(xù)),用Floyd算法求前圖所示有向網(wǎng)G9中所有頂點對之間的最短路徑及長度的過程如下表所示。,Floyd算法舉例(續(xù)),由矩陣path可知任一頂點對之間的最短路徑。 例如v1到v3的最短路徑，由path1,3=1知v3的前一個頂點是v1，即只有一步v1v3，其長度為a1,3=8； 又如求v3到v2的最短路徑，由path3,2=1知v2的前一個頂點是v1，由path3,1=3知v1的前一個頂點是v3，即只有兩步路，v3v1v2，其長度為a3,2=3； 再如求v3到v4的最短路徑，由path3,4=2知v4前一個頂點是

53、v2，由path3,2=1知v2前一個頂點是v1，由path3,1=3知v1前一個頂點是v3，即有三步路v3v1v2v4，其長度為a3,4=10。,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念 5.2 圖與網(wǎng)的存儲結(jié)構(gòu) 5.3 圖的遍歷 5.4 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應(yīng)用,5.6 有向無環(huán)圖及其應(yīng)用,5.6.1 有向無環(huán)圖的概念 5.6.2 AOV網(wǎng)與拓?fù)渑判?5.6.3 AOE網(wǎng)與關(guān)鍵路徑,有向無環(huán)圖的概念,有向無環(huán)圖（directed acycline graph）是指無環(huán)的有向圖，簡稱為DAG圖，它是一類比有向樹更一般的特殊有向圖。 下圖給出

54、了有向樹、DAG圖和有向圖的例子，(a)、(b)、(c)都是有向圖，(a)、(b)都是DAG圖，只有(a)是有向樹；可以通過觀察圖例理解三者之間的聯(lián)系與區(qū)別。,有向無環(huán)圖表示舉例,有向無環(huán)圖是描述含有公共子式的一類表達(dá)式的有效工具。例如對于表達(dá)式 (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 可以用第四章討論的二叉樹表示為如下圖所示的有向樹。,仔細(xì)觀察表達(dá)式可以發(fā)現(xiàn)，表達(dá)式中含有一些相同的子表達(dá)式如(c+d)和(c+d)*e等，在二叉樹中這些相同的子表達(dá)式也重復(fù)出現(xiàn)。,有向無環(huán)圖表示舉例(續(xù)),例如對于同樣表達(dá)式 (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*

55、e) 利用有向無環(huán)圖則可實現(xiàn)對相同子式的共享，從而節(jié)省存儲空間，下圖給出了該表達(dá)式的有向無環(huán)圖。,判斷一個圖是否存在環(huán),要檢查一個有向圖是否存在環(huán)，比檢查一個無向圖是否存在環(huán)復(fù)雜。 對于無向圖來說，深度優(yōu)先搜索遍歷過程中若遇到回邊（即指向已訪問過頂點的邊）則必定存在環(huán)。 對于有向圖來說，深度優(yōu)先搜索遍歷過程中遇到的回邊，有可能是指向深度優(yōu)先生成森林中的另一棵生成樹上頂點的弧，這種情況下不構(gòu)成環(huán)； 只有這個回邊是指向深度優(yōu)先森林中同一棵生成樹上頂點的弧，即從有向圖上的某個頂點v出發(fā)遍歷執(zhí)行dfs(v)結(jié)束之前出現(xiàn)回邊弧，由于u在生成樹上是v的子孫，有向圖必定存在包含頂點v和u的環(huán)。,有向無環(huán)圖的

56、應(yīng)用,有向無環(huán)圖也是描述一項工程或系統(tǒng)進(jìn)展過程的有效工具。 除了最簡單的情況之外，幾乎所有的工程（project）都可分為若干個活動（activity）的子工程，而這些子工程之間通常受著一定條件的約束，其中某些子工程的開始必須在另外一些子工程的完成之后。 對整個工程和系統(tǒng)，人們所關(guān)心的是兩個方面的問題： 一是工程能否順利進(jìn)展， 二是預(yù)期完成整個工程所必須花費的時間最短； 對應(yīng)于描述工程進(jìn)展過程的有向無環(huán)圖而言，即為進(jìn)行拓?fù)渑判蚝完P(guān)鍵路徑的操作。,5.6 有向無環(huán)圖及其應(yīng)用,5.6.1 有向無環(huán)圖的概念 5.6.2 AOV網(wǎng)與拓?fù)渑判?5.6.3 AOE網(wǎng)與關(guān)鍵路徑,AOV網(wǎng)及應(yīng)用舉例,如果在有

57、向圖中用頂點表示活動而用弧表示活動間的優(yōu)先關(guān)系，人們稱該有向圖為頂點表示活動的網(wǎng)（activity on vertex network），簡稱為AOV網(wǎng)。 例如，軟件工程專業(yè)的學(xué)生必須學(xué)習(xí)一組基礎(chǔ)課程和專業(yè)基礎(chǔ)課程。其中有些基礎(chǔ)課程是獨立于其它課程的，如高等數(shù)學(xué)和高級語言程序設(shè)計；有些課程必須在學(xué)完其先導(dǎo)課程后才能開始學(xué)習(xí)，如在學(xué)完高級語言程序設(shè)計和離散數(shù)學(xué)之后才能學(xué)習(xí)算法與數(shù)據(jù)結(jié)構(gòu)。 若用頂點表示課程，用弧表示課程之間的先后修關(guān)系（即弧表示課程j的先修課程是i）。,AOV網(wǎng)的應(yīng)用舉例示圖,AOV網(wǎng),AOV網(wǎng)中的關(guān)系是頂點集合上的偏序關(guān)系。 回憶前導(dǎo)課程離散數(shù)學(xué)中關(guān)于偏序關(guān)系的定義，集合X上的

58、偏序關(guān)系R是指R是自反的、反對稱的和可傳遞的。 如上例課程之間的先后修關(guān)系滿足自反性、反對稱性和可傳遞性，課程間的先后修關(guān)系是課程集合上的偏序關(guān)系。,拓?fù)渑判?偏序關(guān)系是集合中僅有部分成員之間可比較； 如果集合中全體成員之間都可以比較，則為全序關(guān)系，即設(shè)R是集合X上的偏序關(guān)系，如果對每個x、yX必有xRy或yRx，則稱R是集合X 上的全序關(guān)系。這個全序稱作拓?fù)溆行颍╰opological order）； 由偏序定義得到拓?fù)溆行虻牟僮鞣Q作拓?fù)渑判?topological sort)。,AOV網(wǎng)與拓?fù)渑判?AOV網(wǎng)應(yīng)是有向無環(huán)圖即DAG圖。 這是因為工程中的各子工程（活動）先后有序不可能存在環(huán)，若

59、存在環(huán)意味著一個子工程以自身的后續(xù)子工程的完成為開始條件的謬論，如上例軟件工程專業(yè)的一組課程之間不可能存在以自身的后修課程作為前導(dǎo)課程的課程。 所以，對設(shè)計的工程流程圖即給定的AOV網(wǎng)，首先要檢查它是否存在環(huán)路。檢查的辦法是構(gòu)造它的頂點的拓?fù)溆行蛐蛄小Ｈ鬉OV網(wǎng)中所有頂點都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)中必定不存在環(huán)。,AOV網(wǎng)與拓?fù)渑判蚴纠?如下圖中的AOV網(wǎng)可以有如下拓?fù)溆行蛐蛄校?c1c2c3c4c5c6c7c8c9c10c11 和 c2c3c4c1c5c6c11c9c7c8c10 當(dāng)然還可以構(gòu)造出其它一些拓?fù)溆行蛐蛄小?拓?fù)溆行蛐蛄械奶攸c,所構(gòu)造出的拓?fù)溆行蛐蛄械奶攸c是： 在AOV

60、網(wǎng)中，若頂點i領(lǐng)先于頂點j，則在拓?fù)溆行蛐蛄兄腥匀活I(lǐng)先； 對于網(wǎng)中無領(lǐng)先關(guān)系的頂點i和j，在拓?fù)溆行蛐蛄兄薪⒁粋€領(lǐng)先關(guān)系，或者i領(lǐng)先于j，或者j領(lǐng)先于i。 拓?fù)渑判蚓褪怯葾OV網(wǎng)中頂點集合上的偏序關(guān)系得到該集合上的一個全序關(guān)系的操作。對于任何一項工程中各個子工程（活動）的安排，必須按照其中某一個拓?fù)溆行蛐蛄兄械捻樞蜻M(jìn)行安排。,AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê筒襟E,對AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê筒襟E如下： 從AOV網(wǎng)中選擇一個入度為0的頂點輸出它； 從網(wǎng)中刪去該頂點和以它為尾（即從它出發(fā)）的所有弧； 重復(fù)和，直到網(wǎng)中不存在入度為0的頂點時止。 操作的結(jié)果有兩種可能，一種是網(wǎng)中全部頂點均已經(jīng)輸出，拓

61、撲排序完成；一種是有剩余頂點未被輸出，但無入度為0的頂點，說明網(wǎng)中有環(huán)路。,AOV網(wǎng)進(jìn)行拓?fù)渑判蚺e例,以右圖的AOV網(wǎng)為例。 網(wǎng)中v1和v6入度為0，則可選其中之一如v6輸出之；刪除v6及弧和之后，只有v1入度為0，輸出v1并刪除v1和弧，；此時v3和v4入度為0，選擇其一如v4輸出，刪除v4和?。滑F(xiàn)在只有v3入度為0，輸出v3并刪除v3和弧與；對最后剩下的兩個入度為0的孤立頂點v2和v5分別輸出，就完成了拓?fù)渑判颉?其過程如右下圖所示，得到的拓?fù)溆行蛐蛄袨関6v1v4v3v2v5。,拓?fù)渑判蛩惴ǖ膶崿F(xiàn),拓?fù)渑判蛩惴ǖ膶崿F(xiàn)：對AOV網(wǎng)采用鄰接表存儲結(jié)構(gòu)，并且在表頭結(jié)點中增加一個域indegre

62、e來存放頂點的入度。選擇并輸出一個入度為0的頂點可通過查表頭數(shù)組實現(xiàn)，而刪除頂點和以它為尾的弧的操作用弧頭頂點的入度減1來實現(xiàn)。 AOV網(wǎng)的鄰接表的表示如下圖所示：,拓?fù)渑判蛩惴ǖ膶崿F(xiàn)舉例,例如，在右圖的AOV網(wǎng)中，其中v6的入度為0，在輸出v6后可將v4和v5的入度分別由2和3減為1和2。為了避免重復(fù)檢測入度為0的頂點，可把所有入度為0的頂點保存于一鏈棧中，每當(dāng)輸出從棧中彈出一個，每當(dāng)出現(xiàn)新的入度為0的頂點便壓入之。其算法步驟如下： 將所有入度為0的頂點入棧； 彈出棧頂元素輸出，并把各鄰接頂點的入度域值減1； 將新產(chǎn)生的入度為0的頂點入棧； 重復(fù)、兩步，直到?？諘r為止。,拓?fù)渑判蛩惴ǖ膶崿F(xiàn)（

63、續(xù)）,在這里棧僅起保存入度為0的頂點的作用，入度為0的頂點誰先誰后無關(guān)緊要，故也可以用鏈隊列或數(shù)組來保存。 可借用值為0的入度域indegree存放鏈中的指針，把入度域為0的表頭結(jié)點鏈接起來形成鏈棧。,拓?fù)渑判蛩惴ǖ膶崿F(xiàn)舉例,對于前面所舉的示例AOV網(wǎng)的鄰接表，入度域初始狀態(tài)和棧狀態(tài)如右圖(a)所示； 執(zhí)行算法步驟后狀態(tài)如右圖所示，此時棧頂指針top指向頂點v6的表頭結(jié)點，其indegree域值為1（即指向頂點v1的表頭結(jié)點），而v1的表頭結(jié)點的indegree域值為0（即為鏈尾結(jié)點）； 執(zhí)行步驟后輸出v6，并將v5和v4的表頭結(jié)點的入度域減1，未產(chǎn)生入度為0的新頂點，步驟相當(dāng)于空操作；棧頂指

64、針top=1，如右圖(c)所示； 再次執(zhí)行步驟輸出v1，并將v4，v3和v2的表頭結(jié)點的入度域減1，產(chǎn)生了兩個入度為0的新頂點v4和v3，執(zhí)行步驟后鏈棧中只有這兩個結(jié)點，棧頂指針top=3而v3的入度域為4指向v4，v4的入度域為0是鏈尾，如右圖(d)所示； 其余的依此類推，分表如右圖的(e)到(h)所示。,鄰接表的表結(jié)點和表頭結(jié)點的定義,AOV網(wǎng)的鄰接表的表結(jié)點和表頭結(jié)點的定義可形式化描述如下： typedef struct node /*表結(jié)點*/ int adjvex; struct node *next; nodetype; /*表結(jié)點類型*/ typedef struct front

65、node /*表頭結(jié)點*/ vertextype data; int indegree; struct node *next frontnodetype; /*鄰接表結(jié)點類型*/ typedef frontnodetype adjlistmaxvernum; /*鄰接表類型*/,拓?fù)渑判蛩惴捎肅語言描述,拓?fù)渑判蛩惴捎肅語言描述如下。函數(shù)toposort值為0時說明AOV網(wǎng)中存在環(huán)路，無法給出所有頂點的拓?fù)溆行蛐蛄校环駝t為1時拓?fù)渑判虺晒?，輸出AOV網(wǎng)中全部頂點的拓?fù)溆行蛐蛄小?int toposort(adjlist g,int n) int i,j,k,m=0; int top=0; nodetype *p; for(i=1;i=n;i+) if(gi.indegree=0) gi.indegree=top; top=i;,拓?fù)渑判蛩惴捎肅語言描述續(xù),while(top!=0) /*開始拓?fù)渑判?/ j=top; top=gtop.indegree; printf(“%dt”,gj.data); m+; p=gj.next; while(p!=NULL) /