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

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

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

3、，v2，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）。,子圖的定義,假設有兩個圖G=（V，E）和G=（V，E），如果V V且E E，則稱G是G的子圖（subgraph）。 子圖示例如下：,,,網(wǎng)的定義,把圖中與邊或弧相關的數(shù)稱之為權(weight)；權可以表示從一個頂點到另一個頂點的距離、時間、電流、電壓、耗費等， 通常把這種帶權圖稱作網(wǎng)（network）； 當然也可以依據(jù)邊或弧有無向網(wǎng)和有向網(wǎng)的概念。 網(wǎng)的示例如下圖：,5.1 圖與網(wǎng)的基本概念,5.1.1 圖與網(wǎng)的定義 5.1.2 圖的相關術語,圖的相關術語,在無向圖中，某個頂點的度（

5、degree）是指所依附于該頂點的邊的數(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）。,圖的相關術語（續(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

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

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

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

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

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

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

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

13、，這是該方法的局限性。,鄰接矩陣存儲圖或網(wǎng)的類型定義,用一維數(shù)組存儲頂點信息，用鄰接矩陣存儲頂點間關系信息的圖或網(wǎng)的形式描述如下： #define maxvernum 100 #define infinity maxinteger typedef struct vertextype vexmaxvernum; int adjmatrixmaxvernummaxvernum; int n,e; /*定義頂點數(shù)和邊或弧數(shù)變量單元*/ mgraph;,5.2 圖與網(wǎng)的存儲結構,5.2.1 鄰接矩陣 5.2.2 鄰接表與逆鄰接表 5.2.3 鄰接多重表,鄰接表,鄰接表（adjacency list

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

15、一維數(shù)組中，以方便隨機訪問任一頂點的單鏈表。 例如有向網(wǎng)G3的鄰接表如下圖所示。,鄰接表舉例,無向網(wǎng)G4的鄰接表如下圖所示。,鄰接表中結點和表頭結點的形式描述,鄰接表中結點和表頭結點的形式描述定義如下： #define maxvernum 100 typedef struct node /*定義表結點結構*/ int adjvex,info; struct node *next; nodetype; typedef struct frontnode /*定義表頭結點結構*/ vertextype data; struct node *next; frontnodetype

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

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

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

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

20、/*定義邊結點類型*/ int mark ,ivex ,jvex; /*對于網(wǎng)可增加整型info域*/ struct edgenode *ilink,*jlink; edgenodetype ; typedef struct vexnode /*定義頂點結點類型*/ int data; struct edgenode *firstedge; vexnodetype; typedef vexnodetype adjmulistmaxvernum;,鄰接多重表舉例,鄰接多重表舉例（續(xù)）,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念 5.2 圖與網(wǎng)的存儲結構 5.3 圖的遍歷 5.4

21、 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應用,圖的遍歷,和樹的遍歷類似，圖的遍歷（traversing graph）是指從圖中的任一頂點出發(fā)訪問圖中所有頂點，且使每個頂點僅被訪問一次的過程。 然而由于圖結構本身的復雜性，使得圖的遍歷比樹的遍歷復雜得多，主要表現(xiàn)在以下幾個方面： 圖中沒有一個惟一的開始結點，可以從任意一個頂點開始訪問； 從一個頂點出發(fā)只能訪問到它所在連通分量的各頂點，對于非連通圖還需考慮其它連通分量上頂點的訪問；,圖的遍歷（續(xù)）, 如果有回路存在，一個頂點被訪問之后又可能沿回路回到該頂點，為了避免對同一頂點的多次訪問，在遍歷過程中必須記下已訪問過

22、的頂點，通常利用一維輔助數(shù)組記錄頂點被訪問的情況； 一個頂點可以和多個頂點相鄰接，當訪問過這個頂點之后如何選擇下一個要訪問的頂點。 圖的遍歷是圖的重要操作，對圖和網(wǎng)的許多操作都是建立在對圖的遍歷操作的基礎之上，如圖的連通性問題，拓撲排序問題等。通常有兩種遍歷圖的方法，即深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷，這兩種遍歷方法對無向圖和有向圖都適用。,5.3 圖的遍歷,5.3.1 深度優(yōu)先搜索遍歷 5.3.2 廣度優(yōu)先搜索遍歷 5.3.3 圖的遍歷應用舉例 圖的連通性與生成樹,深度優(yōu)先搜索遍歷,圖的深度優(yōu)先搜索（depth-first search）遍歷類似于樹的先根次序遍歷，是樹的先根次序

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

24、到某個尚有鄰接頂點未被訪問的頂點vr，再從vr的一個未被訪問的鄰接頂點出發(fā)重復上述過程；,深度優(yōu)先搜索遍歷（續(xù)）,直到圖中從v0出發(fā)有路徑可達的頂點都訪問到時，圖的一個連通分量深度優(yōu)先搜索遍歷結束， 對于非連通圖中的其它連通分量，還要繼續(xù)上述的深度優(yōu)先搜索遍歷過程，直到圖中所有頂點都被訪問過時止。,例如，對于右圖的無向圖G6的深度優(yōu)先搜索遍歷，若從v1出發(fā)結點的訪問順序為 v1v2v4v8v5v3v6v7,深度優(yōu)先搜索遍歷（續(xù)）,假設圖用鄰接表作存儲結構，圖中n個頂點的表頭結點存入數(shù)組gn+1中，并用1到n作為標識每一個頂點的序號，gi存放頂點vi的有關信息，v為給定的出發(fā)頂點序號。 為了在遍

25、歷過程中區(qū)分頂點是否已被訪問過，設置標志數(shù)組cn+1，初始值全為0，一旦頂點vi被訪問時置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 trave

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

27、于在travergraph中需要O(n)的時間建立標志數(shù)組，故深度優(yōu)先搜索遍歷圖的時間復雜度為O(n+e)。,5.3 圖的遍歷,5.3.1 深度優(yōu)先搜索遍歷 5.3.2 廣度優(yōu)先搜索遍歷 5.3.3 圖的遍歷應用舉例 圖的連通性與生成樹,廣度優(yōu)先搜索遍歷,廣度優(yōu)先搜索(broadth-first search)遍歷類似于樹的按層次遍歷，是樹的層次次序遍歷的推廣。 其定義如下： 從圖中某個頂點v0出發(fā)并訪問它； 依次訪問v0的各個未被訪問的鄰接頂點，然后分別從這些鄰接頂點出發(fā)依次訪問它們的鄰接頂點，并使先被訪問頂點的鄰接頂點先于后被訪問頂點的鄰接頂點，直到圖中已被訪問過的頂點的鄰接頂點都

28、被訪問到； 若圖中還有頂點未被訪問到，則另選一個未被訪問的頂點記作v0轉，否則圖的廣度優(yōu)先遍歷結束。,廣度優(yōu)先搜索遍歷（續(xù)）,換句話說，圖的廣度優(yōu)先搜索遍歷過程是：從v0出發(fā)由近及遠依次訪問有路徑可達且路徑長度分別為1、2、3、的各頂點。,例如對右圖的無向圖G6進行廣度優(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ù)）,由于先被訪問頂點的鄰接頂點先

29、于后被訪問頂點的鄰接頂點被訪問，在廣度優(yōu)先搜索遍歷時應設置隊列q存放已被訪問過的頂點以保證按層次依次訪問它們的鄰接頂點； 同時需要設置一個數(shù)組c記錄頂點是否已被訪問的情況。 假定圖以鄰接表存儲，其它約定也和深度優(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

30、; p=p-next; ,廣度優(yōu)先搜索遍歷（續(xù)）,在圖的廣度優(yōu)先搜索算法中，每個頂點至多進一次隊列。 圖的遍歷過程實質上是通過邊或弧找鄰接頂點的過程， 因此廣度優(yōu)先搜索遍歷圖的時間復雜度和深度優(yōu)先搜索遍歷相同都為O(n+e)， 兩者的區(qū)別僅在于對頂點的訪問次序不同(即bfs和dfs的差別),5.3 圖的遍歷,5.3.1 深度優(yōu)先搜索遍歷 5.3.2 廣度優(yōu)先搜索遍歷 5.3.3 圖的遍歷應用舉例 圖的連通性與生成樹,圖的連通性問題,對于無向圖G進行遍歷時，若G是連通圖，僅需從圖中任一頂點v0出發(fā)進行深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷訪問完圖中所有頂點； 若G是非連通圖，則需從多

31、個頂點出發(fā)進行搜索遍歷，每一次從一個未被訪問過的頂點出發(fā)，遍歷過程中訪問到它所在連通分量中的所有頂點。,例如對左圖的無向圖G2，從v1出發(fā)深度優(yōu)先搜索遍歷得到頂點序列v1v2v3v4v5，訪問完所有頂點；,圖的連通性問題（續(xù)）,例如對右圖的無向圖G5，從A出發(fā)深度優(yōu)先搜索得到頂點序列ABDHGC只訪問完一個連通分量，還需再從E出發(fā)深度優(yōu)先搜索得到結點序列EF才訪問完所有結點。,圖的連通性問題（續(xù)）,由此，我們只要在算法travergraph中設置一個計數(shù)器變量count并賦初值為0，每調用一次dfs(或bfs)就給count加1，在算法執(zhí)行結束時就可依據(jù)count的值是否為1判定圖G 是否連通

32、圖了； 同樣的道理，在travergraph算法中每次調用dfs(或bfs)之間設置輸出標志，就可以區(qū)分非連通圖G的連通分量了。也就是說，利用圖的遍歷算法可以確定無向圖的連通性，也可以求無向圖的連通分量。 同樣的道理，對于有向圖G進行遍歷時，可利用travergraph算法判定有向圖G是否為強連通圖，也可以利用travergraph算法求有向圖G 的強連通分量。,生成樹,一個含有n個頂點的連通圖的生成樹，是圖的一個極小連通子圖，它包含圖中全部n個頂點和保證使任意兩個頂點連通所需的n-1條邊。 對于無向連通圖G=(V,E)，從任一頂點v0出發(fā)遍歷圖G時，必定將邊的集合E劃分為兩個集合E1和E2。

33、 其中：E1為遍歷過程中所經(jīng)過的邊(不含回邊)的集合。E2為其余邊的集合。 由E1和頂點集合V一起構成圖G的極小連通子圖，就是G的生成樹。 由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹，由廣度優(yōu)先搜索遍歷得到的生成樹稱為廣度優(yōu)先生成樹。,生成樹舉例,,,由圖可見，連通圖的生成樹不惟一。從圖中的不同頂點出發(fā)，或者采用不同的遍歷方法，遍歷圖的過程中經(jīng)過的邊不同，得到的生成樹也就不同。,生成森林,對于非連通的無向圖，遍歷過程中得到幾棵生成樹；有幾個連通分量就有幾棵生成樹，即為生成森林。 和生成樹的道理一樣，生成森林也是不惟一的。 對于有向圖G進行深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷，若有向圖G是強連通

34、圖，則得到的是一棵深度優(yōu)先有向樹或一棵廣度優(yōu)先有向樹；若有向圖G是非強連通圖，則得到的是有向森林。,生成森林舉例,,,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念 5.2 圖與網(wǎng)的存儲結構 5.3 圖的遍歷 5.4 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應用,5.4 無向連通網(wǎng)的最小生成樹,5.4.1 最小生成樹的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,最小生成樹的概念,對于一個無向網(wǎng)（即帶權無向圖），生成樹上各邊權值之和稱為這棵生成樹的代價；最小代價生成樹是各邊權值總和最小的生成樹，簡稱最小生成樹(minimum spanning tre

35、e)。 例如下圖所示無向連通網(wǎng)G7和它的最小生成樹：,,最小生成樹的應用,最小生成樹有很多實際應用。 例如要在n個城市之間建立通訊網(wǎng)，連通n個城市只需要n-1條線路；而每兩個城市之間都可以設置一條線路，相應地都要付出一定代價；n個城市之間最多可能設置n(n-1)/2條線路，如何在其中選擇n-1條以使總的耗費最少？即求通訊網(wǎng)的最小生成樹問題。 又如要在m個村莊之間修建公路，使這m個村莊村與村之間可達且總的修建費用最少；此問題是一個以村為頂點，以村與村直達公路為邊其修建費用為權的公路網(wǎng)求最小生成樹的問題。 一個無向連通網(wǎng)的最小生成樹也可能不是惟一的，但其總代價一定是最小的。,5.4 無向連通網(wǎng)的最

36、小生成樹,5.4.1 最小生成樹的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,Prim算法,Prim算法是從連通網(wǎng)中的某一個頂點開始，以此作為生成樹的初始狀態(tài)，然后不斷地將網(wǎng)中的其它頂點添加到生成樹上，直到最后一個頂點添加到生成樹上時得到最小生成樹。 其具體方法是： 從網(wǎng)中任一頂點開始，先把該頂點包含在生成樹中，此時生成樹只有一個頂點； 找出一個端點在生成樹中另一個端點在生成樹外的所有邊，并把權值最小的邊連同它所關聯(lián)的另一個頂點添加到生成樹中；當有兩條及以上具有相同最小權值的邊可供選擇時，選擇其中任意一條都可以； 反復執(zhí)行，直到所有頂點都包含在生成樹中時止。,利用Prim算

37、法構造最小生成樹的過程,下圖給出了利用Prim算法從頂v1開始得到無向連通網(wǎng)G7的最小生成樹的過程：,,Prim算法（續(xù)）,為了實現(xiàn)Prim算法，需設一個輔助數(shù)組closedge以記錄每次選擇的權值最小的邊。 數(shù)組元素closedgei對應于序號為i的頂點vi，它包含兩個域adjvex和lowcost。 若vi已在生成樹上，則置closedgei.lowcost=0； 若頂點vi不在生成樹上，用closedgei. lowcost存放vi與生成樹上的頂點構成的最小代價邊的權值， 而用closedgei.adjvex存放該邊所關聯(lián)的生成樹上的另一頂點的序號。,Prim算法（續(xù)）,設有n個頂點的無

38、向連通網(wǎng)以鄰接矩陣g存儲，從序號為k的頂點vk開始構造最小生成樹，則輔助數(shù)組的初始情況為： closedgek.lowcost=0; closedgei.lowcost=g.adjmatrixk,i (ik且1in) closedgei.adjvex=k; (ik且1in) 然后從數(shù)組中選出某一個j，它滿足closedgej.lowcost不等于0且是最小的值，將vj添加到生成樹上并修改closedge數(shù)組中的值。如此不斷進行下去，直到全部的n個頂點都在生成樹上，就得到了要求的最小生成樹。,Prim算法的形式化描述,#define m 30 /*m為頂點的個數(shù)最大值*/ #define

39、max 99 /*max為權的上限值*/ void prim(mgraph g,int k,int n) int i,j,min,p; struct int adjvex; int lowcost; 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;i

40、) /*選最小權值及對應頂點vp*/ if(closedgej.lowcost!=0 ,Prim算法的形式化描述（續(xù)）,for(j=1;j<=n;j++) if(g.adjmatrixpj

41、中輔助數(shù)組中各分量值變化舉例,下表中給出了利用Prim算法求無向連通網(wǎng)G7從頂點v1出發(fā)生成樹的過程中輔助數(shù)組中各分量值的變化情況。,5.4 無向連通網(wǎng)的最小生成樹,5.4.1 最小生成樹的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,Kruskal算法,Kruskal算法是求無向連通網(wǎng)的最小生成樹的另一種常用算法。它與Prim算法不同，時間復雜度主要與網(wǎng)中邊的條數(shù)e相關為O(eloge)，適合用于求邊稀疏的無向連通網(wǎng)的最小生成樹。 Kruskal算法的思想為： 將n個頂點看作是n個獨立的連通分量，將e條邊按權值大小由小到大排序； 從權值最小的邊開始依權值遞增順序查看每一條邊

42、，如果該邊所依附的兩個頂點在不同的連通分量上，則選定此邊連接兩個連通分量為一個連通分量，否則舍棄此邊； 反復執(zhí)行，直到所有頂點都在同一個連通分量上為止，這個連通分量即為所求的最小生成樹。,利用Kruskal算法構造最小生成樹的過程,,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念 5.2 圖與網(wǎng)的存儲結構 5.3 圖的遍歷 5.4 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應用,有向網(wǎng)的最短路徑,如果右圖中的G7表示一個已建成的公路交通網(wǎng)，頂點表示不同的村莊(或城鎮(zhèn))，邊表示村莊(或城鎮(zhèn))間的公路，邊上的權值表示公路的長度，從村莊(或城鎮(zhèn))v1到村莊(或城鎮(zhèn))v7走哪條

43、路徑最短呢？,或者邊上的權值代表時間，走哪條路徑最快呢？或者邊上的權值代表乘車費用，走哪條路徑最省錢呢？如果在每個村莊(或城鎮(zhèn))都需要換乘車輛，走哪條路換乘次數(shù)最少呢？諸如此類問題，歸結起來就是一個求網(wǎng)中頂點之間最短路徑的問題，即要求路徑上邊的權值之和最小或邊的條數(shù)最少。,有向網(wǎng)的最短路徑（續(xù)）,考慮到交通網(wǎng)的有向性，如公路的上坡和下坡、航運的順水和逆水其時間等不一樣，這里討論有向網(wǎng)的最短路徑(shortest path)，并稱路徑上的第一個頂點為源點(sourse)，最后一個頂點為終點(destination)。 對于無向網(wǎng)的最短路徑問題，可以利用有向網(wǎng)求最短路徑的算法來求解，只不過把無向網(wǎng)

44、中的一條邊看作兩條權值相等方向相反的弧罷了。,5.5 有向網(wǎng)的最短路徑,5.5.1 單源最短路徑 5.5.2 所有頂點對之間的最短路徑,單源最短路徑,所謂單源最短路徑，是指從一個頂點（源點）出發(fā)到其它各頂點的最短路徑，即給定有向網(wǎng)G和源點vk，求從vk到G 中其它各頂點vj(j=1,2,,n, jk)的最短路徑。 迪杰斯特拉(E.W.Dijkstra)提出了一種按路徑長度遞增的次序產生最短路徑的算法。 其基本思想是，把網(wǎng)中所有頂點分成兩組，第一組是已確定最短路徑的頂點集合S，第二組是尚未確定最短路徑的頂點集合V；把V中的頂點按最短路徑長度遞增的順序逐個添加到S中，添加過程中始終保持從vk到S中

45、每個頂點的最短路徑長度都不大于從vk到V中任何頂點的最短路徑長度，直到從vk出發(fā)可以到達的頂點都在S中時止。,單源最短路徑（續(xù)）,一開始時，S中只有頂點vk，其余頂點在V中。 這里引入一維輔助數(shù)組dist，用disti表示在當前時刻所找到的從源點vk到每個終點vi的最短路徑長度；其初始值為：distk=0，若存在弧則disti為其弧上的權值，否則從vk到vi無弧時distk=。 然后每次從V中的頂點中選取一個dist值最小的頂點vj（distj=mindisti|viV）加入到S中；并對V中頂點的dist值進行相應修正，即若以加入S中的頂點vj做中間頂點使得V中某頂點的dist值更小時要相應修

46、改該頂點的dist值。這樣從V中選一個頂點加入S中，對V中頂點的dist值修改一遍，只需做n-1次就可求得從vk到其余各頂點的最短路徑。,單源最短路徑（續(xù)）,在求最短路徑的過程中，最短路徑長度已記在dist數(shù)組中，同時需要把路徑也記下來。 為此我們設一維數(shù)組pre，prei中存放從vk到vi的路徑上vi前一個頂點的序號；若從vk到vi無路徑可達，則vi的前一個頂點序號用0表示（即prei=0）。 在算法結束時，沿著頂點vi對應的prei向前追溯就能確定從vk到vi的最短路徑，其最短路徑長度為disti。 設有向網(wǎng)用鄰接矩陣a表示，ai,j表示弧上的權值，無弧時ai,j為max；ai,i=0，當

47、vi進入S 中時用ai,i=1來標識。,最短路徑的Dijkstra算法描述,求有向網(wǎng)中從頂點vk出發(fā)到其它各頂點的最短路徑的Dijkstra算法如下： void dijkstra(int a,int k,int pre,int dist,int n) int i,j,p,min; for (i=1;i<=n;i++) disti=aki; if (disti

48、1; for(i=1;i<=n;i++) /*在V中選dist最小的頂點*/ if (aii==0 /*dijkstra*/,最短路徑的Dijkstra算法舉例,,最短路徑的Dijkstra算法舉例(續(xù)),使用Dijkstra算法對于前圖中所示的有向圖G8，求從頂點v1到其它各頂點的最短路徑及其算法執(zhí)行過程中dist數(shù)組和pre數(shù)組的變化情況如下表所示。,最短路徑的Dijkstra算法舉例(續(xù)),各頂點進入S中的順序為v1，v3，v5，v4，v6；最終v2仍留在V中未進入S中，說明從v1沒有路徑到達v2。要求從v1到某個頂點vi的最短路徑，可由prei回溯得到。 例如求v1

49、到v6的最短路徑，可由pre6=4，pre4=5，pre5=1得到最短路徑為v1v5v4v6，路徑長度為dist6=60。,5.5 有向網(wǎng)的最短路徑,5.5.1 單源最短路徑 5.5.2 所有頂點對之間的最短路徑,所有頂點對之間的最短路徑,求所有頂點對之間的最短路徑的顯而易見的方法是，每次以一個頂點為源點重復執(zhí)行Dijkstra算法n 次來求得，總的執(zhí)行時間為O(n3)。 下面介紹的是由費洛伊德（E.W.Floyd）提出的另一個算法。該算法也是用鄰接矩陣a表示有向網(wǎng)，其時間復雜度也是O(n3)，但在形式上更簡單些。,Floyd算法的基本思想,Floyd算法的基本思想是： 從鄰接矩陣a開始進行n

50、次迭代，第一次迭代后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,j 其中：1kn，迭代初值a0即為有向網(wǎng)的鄰接矩陣。 迭代公式的意義是，如果在第k次迭代時加入頂點vk后，存在從vi到vk和從vk到vj的兩條路徑，且長度之和小于迭代前從vi到vj的路徑長度，則更新為新路徑的值，否則保留原有的值。,迭代公式直觀地表示,迭

51、代公式可以直觀地表示為下圖所示，圖中用波浪線表示一條路徑。,Floyd算法,為了實現(xiàn)Floyd算法，還需引入一個矩陣path。 pathi,j是從vi到vj的最短路徑上vj前一個頂點的序號，并約定從vi到vj無路徑時pathi,j=0。 在求得最短路徑后由pathi,j的值向前追溯，可以得到從vi到vj的最短路徑。,Floyd算法的形式化描述,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

52、<=n;j++) if (i==j) pathij=0; else if(aij

53、圖所示有向網(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前一個頂點是v2，由path3,2=1知v2前一個頂點是v1，由path3,1=3知v1前一個頂點是v3，即有三步路v

54、3v1v2v4，其長度為a3,4=10。,第5章 圖與網(wǎng),5.1 圖與網(wǎng)的基本概念 5.2 圖與網(wǎng)的存儲結構 5.3 圖的遍歷 5.4 無向連通網(wǎng)的最小生成樹 5.5 有向網(wǎng)的最短路徑 5.6 有向無環(huán)圖及其應用,5.6 有向無環(huán)圖及其應用,5.6.1 有向無環(huán)圖的概念 5.6.2 AOV網(wǎng)與拓撲排序 5.6.3 AOE網(wǎng)與關鍵路徑,有向無環(huán)圖的概念,有向無環(huán)圖（directed acycline graph）是指無環(huán)的有向圖，簡稱為DAG圖，它是一類比有向樹更一般的特殊有向圖。 下圖給出了有向樹、DAG圖和有向圖的例子，(a)、(b)、(c)都是有向圖，(a)、(b)都是DAG圖，只有(a)

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

56、。,判斷一個圖是否存在環(huán),要檢查一個有向圖是否存在環(huán)，比檢查一個無向圖是否存在環(huán)復雜。 對于無向圖來說，深度優(yōu)先搜索遍歷過程中若遇到回邊（即指向已訪問過頂點的邊）則必定存在環(huán)。 對于有向圖來說，深度優(yōu)先搜索遍歷過程中遇到的回邊，有可能是指向深度優(yōu)先生成森林中的另一棵生成樹上頂點的弧，這種情況下不構成環(huán)； 只有這個回邊是指向深度優(yōu)先森林中同一棵生成樹上頂點的弧，即從有向圖上的某個頂點v出發(fā)遍歷執(zhí)行dfs(v)結束之前出現(xiàn)回邊弧，由于u在生成樹上是v的子孫，有向圖必定存在包含頂點v和u的環(huán)。,有向無環(huán)圖的應用,有向無環(huán)圖也是描述一項工程或系統(tǒng)進展過程的有效工具。 除了最簡單的情況之外，幾乎所有的工

57、程（project）都可分為若干個活動（activity）的子工程，而這些子工程之間通常受著一定條件的約束，其中某些子工程的開始必須在另外一些子工程的完成之后。 對整個工程和系統(tǒng)，人們所關心的是兩個方面的問題： 一是工程能否順利進展， 二是預期完成整個工程所必須花費的時間最短； 對應于描述工程進展過程的有向無環(huán)圖而言，即為進行拓撲排序和關鍵路徑的操作。,5.6 有向無環(huán)圖及其應用,5.6.1 有向無環(huán)圖的概念 5.6.2 AOV網(wǎng)與拓撲排序 5.6.3 AOE網(wǎng)與關鍵路徑,AOV網(wǎng)及應用舉例,如果在有向圖中用頂點表示活動而用弧表示活動間的優(yōu)先關系，人們稱該有向圖為頂點表示活動的網(wǎng)（activi

58、ty on vertex network），簡稱為AOV網(wǎng)。 例如，軟件工程專業(yè)的學生必須學習一組基礎課程和專業(yè)基礎課程。其中有些基礎課程是獨立于其它課程的，如高等數(shù)學和高級語言程序設計；有些課程必須在學完其先導課程后才能開始學習，如在學完高級語言程序設計和離散數(shù)學之后才能學習算法與數(shù)據(jù)結構。 若用頂點表示課程，用弧表示課程之間的先后修關系（即弧表示課程j的先修課程是i）。,AOV網(wǎng)的應用舉例示圖,,AOV網(wǎng),AOV網(wǎng)中的關系是頂點集合上的偏序關系。 回憶前導課程離散數(shù)學中關于偏序關系的定義，集合X上的偏序關系R是指R是自反的、反對稱的和可傳遞的。 如上例課程之間的先后修關系滿足自反性、反對稱

59、性和可傳遞性，課程間的先后修關系是課程集合上的偏序關系。,拓撲排序,偏序關系是集合中僅有部分成員之間可比較； 如果集合中全體成員之間都可以比較，則為全序關系，即設R是集合X上的偏序關系，如果對每個x、yX必有xRy或yRx，則稱R是集合X 上的全序關系。這個全序稱作拓撲有序（topological order）； 由偏序定義得到拓撲有序的操作稱作拓撲排序(topological sort)。,AOV網(wǎng)與拓撲排序,AOV網(wǎng)應是有向無環(huán)圖即DAG圖。 這是因為工程中的各子工程（活動）先后有序不可能存在環(huán)，若存在環(huán)意味著一個子工程以自身的后續(xù)子工程的完成為開始條件的謬論，如上例軟件工程專業(yè)的一組課程

60、之間不可能存在以自身的后修課程作為前導課程的課程。 所以，對設計的工程流程圖即給定的AOV網(wǎng)，首先要檢查它是否存在環(huán)路。檢查的辦法是構造它的頂點的拓撲有序序列。若AOV網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)中必定不存在環(huán)。,AOV網(wǎng)與拓撲排序示例,如下圖中的AOV網(wǎng)可以有如下拓撲有序序列： c1c2c3c4c5c6c7c8c9c10c11 和 c2c3c4c1c5c6c11c9c7c8c10 當然還可以構造出其它一些拓撲有序序列。,拓撲有序序列的特點,所構造出的拓撲有序序列的特點是： 在AOV網(wǎng)中，若頂點i領先于頂點j，則在拓撲有序序列中仍然領先； 對于網(wǎng)中無領先關系的頂點i和j，

61、在拓撲有序序列中建立一個領先關系，或者i領先于j，或者j領先于i。 拓撲排序就是由AOV網(wǎng)中頂點集合上的偏序關系得到該集合上的一個全序關系的操作。對于任何一項工程中各個子工程（活動）的安排，必須按照其中某一個拓撲有序序列中的順序進行安排。,AOV網(wǎng)進行拓撲排序的方法和步驟,對AOV網(wǎng)進行拓撲排序的方法和步驟如下： 從AOV網(wǎng)中選擇一個入度為0的頂點輸出它； 從網(wǎng)中刪去該頂點和以它為尾（即從它出發(fā)）的所有??； 重復和，直到網(wǎng)中不存在入度為0的頂點時止。 操作的結果有兩種可能，一種是網(wǎng)中全部頂點均已經(jīng)輸出，拓撲排序完成；一種是有剩余頂點未被輸出，但無入度為0的頂點，說明網(wǎng)中有環(huán)路。,AOV網(wǎng)

62、進行拓撲排序舉例,以右圖的AOV網(wǎng)為例。 網(wǎng)中v1和v6入度為0，則可選其中之一如v6輸出之；刪除v6及弧和之后，只有v1入度為0，輸出v1并刪除v1和弧，，；此時v3和v4入度為0，選擇其一如v4輸出，刪除v4和??；現(xiàn)在只有v3入度為0，輸出v3并刪除v3和弧與；對最后剩下的兩個入度為0的孤立頂點v2和v5分別輸出，就完成了拓撲排序。 其過程如右下圖所示，得到的拓撲有序序列為v6v1v4v3v2v5。,拓撲排序算法的實現(xiàn),拓撲排序算法的實現(xiàn)：對AOV網(wǎng)采用鄰接表存儲結構，并且在表頭結點中增加一個域indegree來存放頂點的入度。選擇并輸出一個入度為0的頂點可通過查表頭數(shù)組實現(xiàn)，而刪除頂點和

63、以它為尾的弧的操作用弧頭頂點的入度減1來實現(xiàn)。 AOV網(wǎng)的鄰接表的表示如下圖所示：,,拓撲排序算法的實現(xiàn)舉例,例如，在右圖的AOV網(wǎng)中，其中v6的入度為0，在輸出v6后可將v4和v5的入度分別由2和3減為1和2。為了避免重復檢測入度為0的頂點，可把所有入度為0的頂點保存于一鏈棧中，每當輸出從棧中彈出一個，每當出現(xiàn)新的入度為0的頂點便壓入之。其算法步驟如下： 將所有入度為0的頂點入棧； 彈出棧頂元素輸出，并把各鄰接頂點的入度域值減1； 將新產生的入度為0的頂點入棧； 重復、兩步，直到?？諘r為止。,拓撲排序算法的實現(xiàn)（續(xù)）,在這里棧僅起保存入度為0的頂點的作用，入度為0的頂點誰先誰后無關緊要，

64、故也可以用鏈隊列或數(shù)組來保存。 可借用值為0的入度域indegree存放鏈中的指針，把入度域為0的表頭結點鏈接起來形成鏈棧。,拓撲排序算法的實現(xiàn)舉例,對于前面所舉的示例AOV網(wǎng)的鄰接表，入度域初始狀態(tài)和棧狀態(tài)如右圖(a)所示； 執(zhí)行算法步驟后狀態(tài)如右圖所示，此時棧頂指針top指向頂點v6的表頭結點，其indegree域值為1（即指向頂點v1的表頭結點），而v1的表頭結點的indegree域值為0（即為鏈尾結點）； 執(zhí)行步驟后輸出v6，并將v5和v4的表頭結點的入度域減1，未產生入度為0的新頂點，步驟相當于空操作；棧頂指針top=1，如右圖(c)所示； 再次執(zhí)行步驟輸出v1，并將v4，v3和v2

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

66、 int indegree; struct node *next frontnodetype; /*鄰接表結點類型*/ typedef frontnodetype adjlistmaxvernum; /*鄰接表類型*/,拓撲排序算法可用C語言描述,拓撲排序算法可用C語言描述如下。函數(shù)toposort值為0時說明AOV網(wǎng)中存在環(huán)路，無法給出所有頂點的拓撲有序序列；否則為1時拓撲排序成功，輸出AOV網(wǎng)中全部頂點的拓撲有序序列。 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;,拓撲排序算法可用C語言描述續(xù),while(top!=0) /*開始拓撲排序*/ j=top; top=gtop.indegree; printf(“%dt”,gj.data); m++; p=gj.next; while(p!=NULL) /