算法與數(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)系，任意兩個(gè)數(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ù)語,圖的定義,圖（graph）是由非空的頂點(diǎn)集合V和描述頂點(diǎn)間關(guān)系的?。ɑ蜻叄┑募螮組成的二元組，即 G=(V，E) 其中： V=vi | vidataobject，E= | vi , vjV， dataobject是具有相同性質(zhì)的數(shù)據(jù)元素（即頂點(diǎn)）的集合； 表示從vi到vj有一條邊單向相連稱作弧，且稱vi為弧尾（起點(diǎn)），vj為弧頭（終點(diǎn)），此時(shí)稱圖為有向圖（digraph）。 若E，必有E，則可以用無序?qū)Γ╲i , vj）代替這兩個(gè)有序?qū)?，即從vi 到 vj有一條雙向邊（即無向邊，也可看作雙向邊）相連稱作邊，此時(shí)圖稱為無向圖（undigraph）。,圖的示例,G1=(V1，E1) 其中： V1=v1，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表示圖中頂點(diǎn)數(shù)目，用e表示邊或弧的數(shù)目，且不考慮頂點(diǎn)到自身的邊或弧，那么對于無向圖e的取值范圍是0到n(n-1)/2，而對于有向圖e的取值范圍為0到n(n-1)。 把具有n(n-1)/2條邊的無向圖稱為無向完全圖； 把具有n(n-1)條弧的有向圖稱為有向完全圖； 有向完全圖和無向完全圖統(tǒng)稱完全圖（completed graph）。 若圖中邊或弧的數(shù)目很少則稱為稀疏圖（sparse graph），反之邊或弧的數(shù)目接近完全圖則稱為稠密圖（dense graph）。,子圖的定義,假設(shè)有兩個(gè)圖G=（V，E）和G=（V，E），如果V V且E E，則稱G是G的子圖（subgraph）。 子圖示例如下：,網(wǎng)的定義,把圖中與邊或弧相關(guān)的數(shù)稱之為權(quán)(weight)；權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離、時(shí)間、電流、電壓、耗費(fèi)等， 通常把這種帶權(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ù)語,在無向圖中，某個(gè)頂點(diǎn)的度（degree）是指所依附于該頂點(diǎn)的邊的數(shù)目，頂點(diǎn)v的度通常記作TD（V）。例如在無向圖G2中，TD（v1）=2，TD（v2）=3，TD（v3）=3，TD（v4）=2，TD（v5）=2。,在有向圖中要區(qū)別頂點(diǎn)的入度和出度的概念， 入度是指以頂點(diǎn)V為終點(diǎn)的弧的數(shù)目，通常記作ID(V)； 出度是指以頂點(diǎn)V為始點(diǎn)的弧的數(shù)目，通常記作OD(V)； 頂點(diǎn)的度定義為入度和出度的和，即: 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； ID（v4）=1，OD（v4）=1，TD（v4）=2。,一般地，對于具有n 個(gè)頂點(diǎn)e條邊或弧的圖，邊或弧的個(gè)數(shù)與各頂點(diǎn)的度TD（vi）之間滿足如下關(guān)系：,圖的相關(guān)術(shù)語（續(xù)）,在無向圖G=（V，E）中，若（vp，vi1），（vi1，vi2） （vin，vq）都是E中的邊，則稱結(jié)點(diǎn)序列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)，所以說從V1到V5存在一條長度各為2和3的路徑。,圖的相關(guān)術(shù)語（續(xù)）,如果頂點(diǎn)序列中不出現(xiàn)重復(fù)頂點(diǎn)，則稱頂點(diǎn)序列為簡單路徑，例如前面所舉三條路徑的頂點(diǎn)序列分別為v3、v4、v1、v2和v1、v2、v5與v1、v4、v3、v5，均無重復(fù)頂點(diǎn)出現(xiàn)都是簡單路徑。 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎ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ù)）,在無向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj 有路徑，則稱vi和vj是連通的；如果圖中任意兩個(gè)頂點(diǎn)vi和vj都是連通的，則稱該無向圖是連通圖（connected graph）。例如無向圖G2是連通圖，,而如下無向圖G5是非連通圖。,圖的相關(guān)術(shù)語（續(xù)）,無向圖的極大連通子圖稱為圖的連通分量（connected component）。 例如下圖給出了無向圖G5的兩個(gè)連通分量。,圖的相關(guān)術(shù)語（續(xù)）,在有向圖中，如果對于任意兩個(gè)頂點(diǎn)vi和vj（vivj）從vi到vj和從vj到vi都存在路徑，則稱該有向圖為強(qiáng)連通圖（strong graph）。 有向圖的極大強(qiáng)連通子圖稱為圖的強(qiáng)連通分量（strongly connected component）。 例如有向圖G1不是強(qiáng)連通圖，它的兩個(gè)強(qiáng)連通分量如下圖所示。,圖的相關(guān)術(shù)語（續(xù)）,一個(gè)連通圖的生成樹（spanning tree）是該圖的一個(gè)極小連通子圖，它包含圖中全部的n個(gè)頂點(diǎn)和連通這n個(gè)頂點(diǎn)的n-1條邊。 如果在生成樹上添加任意一條原圖中的其它邊必定會產(chǎn)生回路或環(huán)；換句話說，有n個(gè)頂點(diǎn)n條或n條以上邊的無向圖一定存在回路或環(huán)。如果n個(gè)頂點(diǎn)的圖其邊數(shù)少于n-1條，則一定是非連通圖。 例如無向圖G2的一棵生成樹如下圖所示。,圖的相關(guān)術(shù)語（續(xù)）,在非連通圖中，由每個(gè)連通分量都可以得到一個(gè)極小連通子圖，即一棵生成樹，這些連通分量的生成樹就構(gòu)成了該非連通圖的生成森林。 對于有向圖，其生成樹或生成森林必定是有向樹和有向森林。 例如無向圖G5的生成森林如下圖所示。,第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)系。由于圖中頂點(diǎn)的度差別一般較大，故也不宜采用多重鏈表存儲結(jié)構(gòu)； 但可根據(jù)圖的具體情況和需要進(jìn)行的操作，設(shè)計(jì)恰當(dāng)?shù)慕Y(jié)點(diǎn)結(jié)構(gòu)和表結(jié)構(gòu)來存儲頂點(diǎn)信息和頂點(diǎn)間的關(guān)系，,5.2 圖與網(wǎng)的存儲結(jié)構(gòu),5.2.1 鄰接矩陣 5.2.2 鄰接表與逆鄰接表 5.2.3 鄰接多重表,鄰接矩陣,所謂鄰接矩陣（adjacency matrix）存儲結(jié)構(gòu)，就是用一維數(shù)組存儲圖或網(wǎng)的頂點(diǎn)信息，用二維數(shù)組表示頂點(diǎn)之間的鄰接關(guān)系（即鄰接矩陣）。 若G=（V，E）是具有n個(gè)頂點(diǎn)的圖或網(wǎng)，G的鄰接矩陣A是如下定義的n階方陣： 當(dāng)G是無向圖或有向圖時(shí)，矩陣A中元素定義為,鄰接矩陣（續(xù)）,當(dāng)G是無向網(wǎng)或有向網(wǎng)時(shí)，矩陣A中元素定義為 其中：Wij表示邊或弧上的權(quán)值，表示一個(gè)所用計(jì)算機(jī)上所允許的大于所有權(quán)值的數(shù)或者一個(gè)特殊的其它值。,鄰接矩陣存儲結(jié)構(gòu)舉例,鄰接矩陣存儲,鄰接矩陣存儲,鄰接矩陣存儲結(jié)構(gòu)舉例(續(xù)),鄰接矩陣存儲,鄰接矩陣存儲,鄰接矩陣存儲結(jié)構(gòu)的特點(diǎn),從圖的鄰接矩陣存儲表示容易看出該表示法具有如下特點(diǎn)： 無向圖或網(wǎng)的鄰接矩陣一定是一個(gè)對稱矩陣，因此在存儲鄰接矩陣時(shí)可以只存儲其上三角陣或下三角陣以節(jié)省存儲空間。 對于無向圖或網(wǎng)，其鄰接矩陣中第i行（或第i列）中非零元素（或非元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度。即,鄰接矩陣存儲結(jié)構(gòu)的特點(diǎn)(續(xù)),對于有向圖或網(wǎng)，其鄰接矩陣中第i行中非零元素（或非元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度OD(vi)，而第i列中非零元素（或非元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的入度ID(vi) 。即 很容易確定圖或網(wǎng)中任意兩個(gè)頂點(diǎn)之間是否有邊或弧相連；但要確定圖或網(wǎng)中有多少條邊或弧則需要逐行逐列掃描方陣，時(shí)間代價(jià)是O(n2)，這是該方法的局限性。,鄰接矩陣存儲圖或網(wǎng)的類型定義,用一維數(shù)組存儲頂點(diǎn)信息，用鄰接矩陣存儲頂點(diǎn)間關(guān)系信息的圖或網(wǎng)的形式描述如下： #define maxvernum 100 #define infinity maxinteger typedef struct vertextype vexmaxvernum; int adjmatrixmaxvernummaxvernum; int n,e; /*定義頂點(diǎn)數(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)。在鄰接表中，對圖或網(wǎng)中的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)是與vi相關(guān)聯(lián)的邊所聯(lián)結(jié)的結(jié)點(diǎn)（對有向圖是以頂點(diǎn)vi為尾的弧所聯(lián)結(jié)的結(jié)點(diǎn)，即弧頭結(jié)點(diǎn)）。 每個(gè)結(jié)點(diǎn)由三個(gè)域組成，其中：鄰接點(diǎn)域adjvex指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置，鏈域next指示下一條邊或弧所聯(lián)結(jié)的結(jié)點(diǎn)，數(shù)據(jù)域info存儲和邊或弧相關(guān)的信息（如網(wǎng)中的權(quán)值等）。每個(gè)單鏈表都附設(shè)一個(gè)表頭結(jié)點(diǎn)，如下圖所示。,鄰接表（續(xù)）,除了設(shè)有鏈域next指向鏈表中的第一個(gè)結(jié)點(diǎn)外，還設(shè)有數(shù)據(jù)域data存放頂點(diǎn)vi的有關(guān)信息（如頂點(diǎn)名，頂點(diǎn)位置等）。 這些表頭結(jié)點(diǎn)也可以組織為一個(gè)鏈表，但通常以向量形式存儲于一維數(shù)組中，以方便隨機(jī)訪問任一頂點(diǎn)的單鏈表。 例如有向網(wǎng)G3的鄰接表如下圖所示。,鄰接表舉例,無向網(wǎng)G4的鄰接表如下圖所示。,鄰接表中結(jié)點(diǎn)和表頭結(jié)點(diǎn)的形式描述,鄰接表中結(jié)點(diǎn)和表頭結(jié)點(diǎn)的形式描述定義如下： #define maxvernum 100 typedef struct node /*定義表結(jié)點(diǎn)結(jié)構(gòu)*/ int adjvex,info; struct node *next; nodetype; typedef struct frontnode /*定義表頭結(jié)點(diǎn)結(jié)構(gòu)*/ vertextype data; struct node *next; frontnodetype; typedef frontnodetype adjlistmaxvernum;,鄰接表與逆鄰接表,若無向圖或網(wǎng)中有n個(gè)頂點(diǎn)e條邊，則它的鄰接表需n個(gè)表頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。顯然在邊稀疏的情況下，用鄰接表比鄰接矩陣節(jié)省存儲空間，當(dāng)與邊相關(guān)的信息較多時(shí)更是如此。 在無向圖或網(wǎng)的鄰接表中，頂點(diǎn)vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)。在有向圖或網(wǎng)的鄰接表中，第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)只是頂點(diǎn)vi的出度；為了求vi的入度，必須遍歷整個(gè)鄰接表，所有鄰接點(diǎn)域adjvex的值為i的結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)vi的入度。 有時(shí)為了便于確定頂點(diǎn)的入度或以vi為頭的弧，可以建立逆鄰接表，即對vi建立一個(gè)鏈接以vi為頭的弧的表。 在鄰接表上，可以很方便地找到任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)；但要判定任意兩個(gè)頂點(diǎn)vi和vj之間是否有邊或弧相連，則需要第i個(gè)或第j個(gè)單鏈表，在這一點(diǎn)上不及鄰接矩陣方便。,逆鄰接表舉例,有向網(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)于頂點(diǎn)和邊的有關(guān)信息；然而和一條邊(vi，vj)相關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)vi和vj分別存儲在第i和第j兩個(gè)單鏈表中，給無向圖或網(wǎng)的某些操作帶來不便。 例如，要對已搜索過的邊作記號或刪除一條邊等操作，需要找到表示同一條邊的兩個(gè)結(jié)點(diǎn)。在對無向圖或網(wǎng)進(jìn)行這一類操作的問題中，宜采用下面將要介紹的鄰接多重表作存儲結(jié)構(gòu)。,鄰接多重表（續(xù)）,在鄰接多重表中，每一條邊用一個(gè)結(jié)點(diǎn)來表示，每個(gè)結(jié)點(diǎn)由五個(gè)或六個(gè)域組成，如下圖所示。 其中：mark為標(biāo)志域，可用來標(biāo)記該條邊是否已被搜索過；ivex和jvex為該邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)在圖中的位置或序號；ilink指向下一條依附于頂點(diǎn)ivex的邊，jlink指向下一條依附于頂點(diǎn)jvex的邊； 需要時(shí)還可增加一個(gè)存放和邊相關(guān)的各種信息的域info。,鄰接多重表（續(xù)）,無向圖或網(wǎng)中的每個(gè)頂點(diǎn)也用一個(gè)結(jié)點(diǎn)表示，它由存儲與該頂點(diǎn)相關(guān)的信息的域data和指示第一條依附于該頂點(diǎn)的邊的域firstedge組成，如下圖所示。 在鄰接多重表中，所有依附于同一個(gè)頂點(diǎn)的邊都鏈接在同一個(gè)鏈表中；由于每一條邊都依附于兩個(gè)頂點(diǎn)，所以每一個(gè)邊結(jié)點(diǎn)都同時(shí)鏈接在兩個(gè)鏈表中。 由此可見，對于無向圖和無向網(wǎng)而言，其鄰接多重表和鄰接表的差別僅在于同一條邊在鄰接表中用兩個(gè)結(jié)點(diǎn)而在鄰接多重表中只用一個(gè)結(jié)點(diǎn)。 除了在邊結(jié)點(diǎn)中增加一個(gè)標(biāo)志域外，鄰接多重表所需的存儲量和鄰接表相同。在鄰接多重表中，各種基本操作的實(shí)現(xiàn)也和鄰接表相似。,鄰接多重表的邊結(jié)點(diǎn)和頂點(diǎn)結(jié)點(diǎn)的形式描述,鄰接多重表的邊結(jié)點(diǎn)和頂點(diǎn)結(jié)點(diǎn)的形式描述定義如下： typedef struct edgenode /*定義邊結(jié)點(diǎn)類型*/ int mark ,ivex ,jvex; /*對于網(wǎng)可增加整型info域*/ struct edgenode *ilink,*jlink; edgenodetype ; typedef struct vexnode /*定義頂點(diǎn)結(jié)點(diǎn)類型*/ 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)用,圖的遍歷,和樹的遍歷類似，圖的遍歷（traversing graph）是指從圖中的任一頂點(diǎn)出發(fā)訪問圖中所有頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次的過程。 然而由于圖結(jié)構(gòu)本身的復(fù)雜性，使得圖的遍歷比樹的遍歷復(fù)雜得多，主要表現(xiàn)在以下幾個(gè)方面： 圖中沒有一個(gè)惟一的開始結(jié)點(diǎn)，可以從任意一個(gè)頂點(diǎn)開始訪問； 從一個(gè)頂點(diǎn)出發(fā)只能訪問到它所在連通分量的各頂點(diǎn)，對于非連通圖還需考慮其它連通分量上頂點(diǎn)的訪問；,圖的遍歷（續(xù)）, 如果有回路存在，一個(gè)頂點(diǎn)被訪問之后又可能沿回路回到該頂點(diǎn)，為了避免對同一頂點(diǎn)的多次訪問，在遍歷過程中必須記下已訪問過的頂點(diǎn)，通常利用一維輔助數(shù)組記錄頂點(diǎn)被訪問的情況； 一個(gè)頂點(diǎn)可以和多個(gè)頂點(diǎn)相鄰接，當(dāng)訪問過這個(gè)頂點(diǎn)之后如何選擇下一個(gè)要訪問的頂點(diǎn)。 圖的遍歷是圖的重要操作，對圖和網(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）遍歷類似于樹的先根次序遍歷，是樹的先根次序遍歷的推廣。 其遞歸定義如下： 從圖中某個(gè)頂點(diǎn)v0出發(fā)并訪問它； 依次從v0的未被訪問的鄰接頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中所有從v0出發(fā)有路徑可達(dá)的頂點(diǎn)都已被訪問到； 若圖中還有頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂點(diǎn)記作v0轉(zhuǎn)，否則圖的深度優(yōu)先遍歷結(jié)束。,深度優(yōu)先搜索遍歷（續(xù)）,在深度優(yōu)先搜索遍歷開始時(shí)，圖G的初始狀態(tài)是所有頂點(diǎn)都未曾被訪問： 首先從某一頂點(diǎn)v0出發(fā)并訪問它； 然后訪問與v0相鄰接的頂點(diǎn)vi，下一個(gè)要訪問的是與頂點(diǎn)vi相鄰接的尚未被訪問的頂點(diǎn)vj，再下一個(gè)是與vj相鄰接的尚未被訪問的頂點(diǎn)vk， 依此類推直到某個(gè)頂點(diǎn)所有的鄰接頂點(diǎn)都已被訪問過時(shí)達(dá)到最“深處”； 此時(shí)逐層回退到某個(gè)尚有鄰接頂點(diǎn)未被訪問的頂點(diǎn)vr，再從vr的一個(gè)未被訪問的鄰接頂點(diǎn)出發(fā)重復(fù)上述過程；,深度優(yōu)先搜索遍歷（續(xù)）,直到圖中從v0出發(fā)有路徑可達(dá)的頂點(diǎn)都訪問到時(shí)，圖的一個(gè)連通分量深度優(yōu)先搜索遍歷結(jié)束， 對于非連通圖中的其它連通分量，還要繼續(xù)上述的深度優(yōu)先搜索遍歷過程，直到圖中所有頂點(diǎn)都被訪問過時(shí)止。,例如，對于右圖的無向圖G6的深度優(yōu)先搜索遍歷，若從v1出發(fā)結(jié)點(diǎn)的訪問順序?yàn)?v1v2v4v8v5v3v6v7,深度優(yōu)先搜索遍歷（續(xù)）,假設(shè)圖用鄰接表作存儲結(jié)構(gòu)，圖中n個(gè)頂點(diǎn)的表頭結(jié)點(diǎn)存入數(shù)組gn+1中，并用1到n作為標(biāo)識每一個(gè)頂點(diǎn)的序號，gi存放頂點(diǎn)vi的有關(guān)信息，v為給定的出發(fā)頂點(diǎn)序號。 為了在遍歷過程中區(qū)分頂點(diǎn)是否已被訪問過，設(shè)置標(biāo)志數(shù)組cn+1，初始值全為0，一旦頂點(diǎn)vi被訪問時(shí)置ci為1。,深度優(yōu)先搜索遍歷（續(xù)）,從頂點(diǎn)v 出發(fā)按深度優(yōu)先搜索遍歷圖的遞歸算法dfs如下： void dfs(adjlist g,int v,int c) int i ; nodetype *p; cv=1; printf(“%dn”,v); /*訪問頂點(diǎn)v*/ for(p=gv.next;p!=NULL;p=p-next) i=p-adjvex; if(ci=0) dfs(g,i,c); ,深度優(yōu)先搜索遍歷（續(xù)）,對整個(gè)圖的遍歷算法travergraph如下： void travergraph(adjlist g ,int n ) int v; int cn+1; for(v=1;v<=n;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ù)）,在遍歷時(shí)，對每個(gè)頂點(diǎn)至多調(diào)用一次dfs函數(shù)；因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志為已被訪問，就不會再從它出發(fā)進(jìn)行搜索。 因此，遍歷圖的過程實(shí)質(zhì)上是對每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程，其時(shí)間耗費(fèi)取決于所采用的存儲結(jié)構(gòu)。 在上述以鄰接表作圖的存儲結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所需時(shí)間為O(e)，e為無向圖的邊數(shù)或有向圖的弧數(shù)。由于在travergraph中需要O(n)的時(shí)間建立標(biāo)志數(shù)組，故深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O(n+e)。,5.3 圖的遍歷,5.3.1 深度優(yōu)先搜索遍歷 5.3.2 廣度優(yōu)先搜索遍歷 5.3.3 圖的遍歷應(yīng)用舉例 圖的連通性與生成樹,廣度優(yōu)先搜索遍歷,廣度優(yōu)先搜索(broadth-first search)遍歷類似于樹的按層次遍歷，是樹的層次次序遍歷的推廣。 其定義如下： 從圖中某個(gè)頂點(diǎn)v0出發(fā)并訪問它； 依次訪問v0的各個(gè)未被訪問的鄰接頂點(diǎn)，然后分別從這些鄰接頂點(diǎn)出發(fā)依次訪問它們的鄰接頂點(diǎn)，并使先被訪問頂點(diǎn)的鄰接頂點(diǎn)先于后被訪問頂點(diǎn)的鄰接頂點(diǎn)，直到圖中已被訪問過的頂點(diǎn)的鄰接頂點(diǎn)都被訪問到； 若圖中還有頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂點(diǎn)記作v0轉(zhuǎn)，否則圖的廣度優(yōu)先遍歷結(jié)束。,廣度優(yōu)先搜索遍歷（續(xù)）,換句話說，圖的廣度優(yōu)先搜索遍歷過程是：從v0出發(fā)由近及遠(yuǎn)依次訪問有路徑可達(dá)且路徑長度分別為1、2、3、的各頂點(diǎn)。,例如對右圖的無向圖G6進(jìn)行廣度優(yōu)先搜索遍歷； 從v1出發(fā)訪問v1，然后訪問v1的鄰接點(diǎn)v2和v3，緊接著訪問v2的鄰接點(diǎn)v4和v5，v3的鄰接點(diǎn)v6和v7，最后訪問v4的鄰接點(diǎn)v8。此時(shí)所有頂點(diǎn)均已被訪問過，圖G6的廣度優(yōu)先搜索遍歷完成，得到的廣度優(yōu)先搜索遍歷頂點(diǎn)序列為 v1v2v3v4v5v6v7v8,廣度優(yōu)先搜索遍歷（續(xù)）,由于先被訪問頂點(diǎn)的鄰接頂點(diǎn)先于后被訪問頂點(diǎn)的鄰接頂點(diǎn)被訪問，在廣度優(yōu)先搜索遍歷時(shí)應(yīng)設(shè)置隊(duì)列q存放已被訪問過的頂點(diǎn)以保證按層次依次訪問它們的鄰接頂點(diǎn)； 同時(shí)需要設(shè)置一個(gè)數(shù)組c記錄頂點(diǎn)是否已被訪問的情況。 假定圖以鄰接表存儲，其它約定也和深度優(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)先搜索算法中，每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。 圖的遍歷過程實(shí)質(zhì)上是通過邊或弧找鄰接頂點(diǎn)的過程， 因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同都為O(n+e)， 兩者的區(qū)別僅在于對頂點(diǎn)的訪問次序不同(即bfs和dfs的差別),5.3 圖的遍歷,5.3.1 深度優(yōu)先搜索遍歷 5.3.2 廣度優(yōu)先搜索遍歷 5.3.3 圖的遍歷應(yīng)用舉例 圖的連通性與生成樹,圖的連通性問題,對于無向圖G進(jìn)行遍歷時(shí)，若G是連通圖，僅需從圖中任一頂點(diǎn)v0出發(fā)進(jìn)行深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷訪問完圖中所有頂點(diǎn)； 若G是非連通圖，則需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索遍歷，每一次從一個(gè)未被訪問過的頂點(diǎn)出發(fā)，遍歷過程中訪問到它所在連通分量中的所有頂點(diǎn)。,例如對左圖的無向圖G2，從v1出發(fā)深度優(yōu)先搜索遍歷得到頂點(diǎn)序列v1v2v3v4v5，訪問完所有頂點(diǎn)；,圖的連通性問題（續(xù)）,例如對右圖的無向圖G5，從A出發(fā)深度優(yōu)先搜索得到頂點(diǎn)序列ABDHGC只訪問完一個(gè)連通分量，還需再從E出發(fā)深度優(yōu)先搜索得到結(jié)點(diǎn)序列EF才訪問完所有結(jié)點(diǎn)。,圖的連通性問題（續(xù)）,由此，我們只要在算法travergraph中設(shè)置一個(gè)計(jì)數(shù)器變量count并賦初值為0，每調(diào)用一次dfs(或bfs)就給count加1，在算法執(zhí)行結(jié)束時(shí)就可依據(jù)count的值是否為1判定圖G 是否連通圖了； 同樣的道理，在travergraph算法中每次調(diào)用dfs(或bfs)之間設(shè)置輸出標(biāo)志，就可以區(qū)分非連通圖G的連通分量了。也就是說，利用圖的遍歷算法可以確定無向圖的連通性，也可以求無向圖的連通分量。 同樣的道理，對于有向圖G進(jìn)行遍歷時(shí)，可利用travergraph算法判定有向圖G是否為強(qiáng)連通圖，也可以利用travergraph算法求有向圖G 的強(qiáng)連通分量。,生成樹,一個(gè)含有n個(gè)頂點(diǎn)的連通圖的生成樹，是圖的一個(gè)極小連通子圖，它包含圖中全部n個(gè)頂點(diǎn)和保證使任意兩個(gè)頂點(diǎn)連通所需的n-1條邊。 對于無向連通圖G=(V,E)，從任一頂點(diǎn)v0出發(fā)遍歷圖G時(shí)，必定將邊的集合E劃分為兩個(gè)集合E1和E2。 其中：E1為遍歷過程中所經(jīng)過的邊(不含回邊)的集合。E2為其余邊的集合。 由E1和頂點(diǎn)集合V一起構(gòu)成圖G的極小連通子圖，就是G的生成樹。 由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹，由廣度優(yōu)先搜索遍歷得到的生成樹稱為廣度優(yōu)先生成樹。,生成樹舉例,由圖可見，連通圖的生成樹不惟一。從圖中的不同頂點(diǎn)出發(fā)，或者采用不同的遍歷方法，遍歷圖的過程中經(jīng)過的邊不同，得到的生成樹也就不同。,生成森林,對于非連通的無向圖，遍歷過程中得到幾棵生成樹；有幾個(gè)連通分量就有幾棵生成樹，即為生成森林。 和生成樹的道理一樣，生成森林也是不惟一的。 對于有向圖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) 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算法,最小生成樹的概念,對于一個(gè)無向網(wǎng)（即帶權(quán)無向圖），生成樹上各邊權(quán)值之和稱為這棵生成樹的代價(jià)；最小代價(jià)生成樹是各邊權(quán)值總和最小的生成樹，簡稱最小生成樹(minimum spanning tree)。 例如下圖所示無向連通網(wǎng)G7和它的最小生成樹：,最小生成樹的應(yīng)用,最小生成樹有很多實(shí)際應(yīng)用。 例如要在n個(gè)城市之間建立通訊網(wǎng)，連通n個(gè)城市只需要n-1條線路；而每兩個(gè)城市之間都可以設(shè)置一條線路，相應(yīng)地都要付出一定代價(jià)；n個(gè)城市之間最多可能設(shè)置n(n-1)/2條線路，如何在其中選擇n-1條以使總的耗費(fèi)最少？即求通訊網(wǎng)的最小生成樹問題。 又如要在m個(gè)村莊之間修建公路，使這m個(gè)村莊村與村之間可達(dá)且總的修建費(fèi)用最少；此問題是一個(gè)以村為頂點(diǎn)，以村與村直達(dá)公路為邊其修建費(fèi)用為權(quán)的公路網(wǎng)求最小生成樹的問題。 一個(gè)無向連通網(wǎng)的最小生成樹也可能不是惟一的，但其總代價(jià)一定是最小的。,5.4 無向連通網(wǎng)的最小生成樹,5.4.1 最小生成樹的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,Prim算法,Prim算法是從連通網(wǎng)中的某一個(gè)頂點(diǎn)開始，以此作為生成樹的初始狀態(tài)，然后不斷地將網(wǎng)中的其它頂點(diǎn)添加到生成樹上，直到最后一個(gè)頂點(diǎn)添加到生成樹上時(shí)得到最小生成樹。 其具體方法是： 從網(wǎng)中任一頂點(diǎn)開始，先把該頂點(diǎn)包含在生成樹中，此時(shí)生成樹只有一個(gè)頂點(diǎn)； 找出一個(gè)端點(diǎn)在生成樹中另一個(gè)端點(diǎn)在生成樹外的所有邊，并把權(quán)值最小的邊連同它所關(guān)聯(lián)的另一個(gè)頂點(diǎn)添加到生成樹中；當(dāng)有兩條及以上具有相同最小權(quán)值的邊可供選擇時(shí)，選擇其中任意一條都可以； 反復(fù)執(zhí)行，直到所有頂點(diǎn)都包含在生成樹中時(shí)止。,利用Prim算法構(gòu)造最小生成樹的過程,下圖給出了利用Prim算法從頂v1開始得到無向連通網(wǎng)G7的最小生成樹的過程：,Prim算法（續(xù)）,為了實(shí)現(xiàn)Prim算法，需設(shè)一個(gè)輔助數(shù)組closedge以記錄每次選擇的權(quán)值最小的邊。 數(shù)組元素closedgei對應(yīng)于序號為i的頂點(diǎn)vi，它包含兩個(gè)域adjvex和lowcost。 若vi已在生成樹上，則置closedgei.lowcost=0； 若頂點(diǎn)vi不在生成樹上，用closedgei. lowcost存放vi與生成樹上的頂點(diǎn)構(gòu)成的最小代價(jià)邊的權(quán)值， 而用closedgei.adjvex存放該邊所關(guān)聯(lián)的生成樹上的另一頂點(diǎn)的序號。,Prim算法（續(xù)）,設(shè)有n個(gè)頂點(diǎn)的無向連通網(wǎng)以鄰接矩陣g存儲，從序號為k的頂點(diǎn)vk開始構(gòu)造最小生成樹，則輔助數(shù)組的初始情況為： closedgek.lowcost=0; closedgei.lowcost=g.adjmatrixk,i (ik且1in) closedgei.adjvex=k; (ik且1in) 然后從數(shù)組中選出某一個(gè)j，它滿足closedgej.lowcost不等于0且是最小的值，將vj添加到生成樹上并修改closedge數(shù)組中的值。如此不斷進(jìn)行下去，直到全部的n個(gè)頂點(diǎn)都在生成樹上，就得到了要求的最小生成樹。,Prim算法的形式化描述,#define m 30 /*m為頂點(diǎn)的個(gè)數(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; 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<n;i+) p=1; min=max; for(j=1;j<=n;j+) /*選最小權(quán)值及對應(yīng)頂點(diǎn)vp*/ if(closedgej.lowcost!=0 ,Prim算法的形式化描述（續(xù)）,for(j=1;j<=n;j+) if(g.adjmatrixpj<closedgej.lowclst) closedgej.lowcost=g.adjmatrixpj; closedgej.adjvex=p; /*選一條邊及對應(yīng)頂點(diǎn)結(jié)束*/ /*prim結(jié)束*/ 在該算法中有一個(gè)兩重循環(huán)，外層執(zhí)行n-1次，里層兩個(gè)并列循環(huán)各執(zhí)行n次。所以Prim算法與網(wǎng)中的邊數(shù)無關(guān)，其時(shí)間復(fù)雜度為O(n2)，適合于求邊稠密的網(wǎng)的最小生成樹。,在Prim算法中輔助數(shù)組中各分量值變化舉例,下表中給出了利用Prim算法求無向連通網(wǎng)G7從頂點(diǎn)v1出發(fā)生成樹的過程中輔助數(shù)組中各分量值的變化情況。,5.4 無向連通網(wǎng)的最小生成樹,5.4.1 最小生成樹的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,Kruskal算法,Kruskal算法是求無向連通網(wǎng)的最小生成樹的另一種常用算法。它與Prim算法不同，時(shí)間復(fù)雜度主要與網(wǎng)中邊的條數(shù)e相關(guān)為O(eloge)，適合用于求邊稀疏的無向連通網(wǎng)的最小生成樹。 Kruskal算法的思想為： 將n個(gè)頂點(diǎn)看作是n個(gè)獨(dú)立的連通分量，將e條邊按權(quán)值大小由小到大排序； 從權(quán)值最小的邊開始依權(quán)值遞增順序查看每一條邊，如果該邊所依附的兩個(gè)頂點(diǎn)在不同的連通分量上，則選定此邊連接兩個(gè)連通分量為一個(gè)連通分量，否則舍棄此邊； 反復(fù)執(zhí)行，直到所有頂點(diǎn)都在同一個(gè)連通分量上為止，這個(gè)連通分量即為所求的最小生成樹。,利用Kruskal算法構(gòu)造最小生成樹的過程,第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)的最短路徑,如果右圖中的G7表示一個(gè)已建成的公路交通網(wǎng)，頂點(diǎn)表示不同的村莊(或城鎮(zhèn))，邊表示村莊(或城鎮(zhèn))間的公路，邊上的權(quán)值表示公路的長度，從村莊(或城鎮(zhèn))v1到村莊(或城鎮(zhèn))v7走哪條路徑最短呢？,或者邊上的權(quán)值代表時(shí)間，走哪條路徑最快呢？或者邊上的權(quán)值代表乘車費(fèi)用，走哪條路徑最省錢呢？如果在每個(gè)村莊(或城鎮(zhèn))都需要換乘車輛，走哪條路換乘次數(shù)最少呢？諸如此類問題，歸結(jié)起來就是一個(gè)求網(wǎng)中頂點(diǎn)之間最短路徑的問題，即要求路徑上邊的權(quán)值之和最小或邊的條數(shù)最少。,有向網(wǎng)的最短路徑（續(xù)）,考慮到交通網(wǎng)的有向性，如公路的上坡和下坡、航運(yùn)的順?biāo)湍嫠鋾r(shí)間等不一樣，這里討論有向網(wǎng)的最短路徑(shortest path)，并稱路徑上的第一個(gè)頂點(diǎn)為源點(diǎn)(sourse)，最后一個(gè)頂點(diǎn)為終點(diǎn)(destination)。 對于無向網(wǎng)的最短路徑問題，可以利用有向網(wǎng)求最短路徑的算法來求解，只不過把無向網(wǎng)中的一條邊看作兩條權(quán)值相等方向相反的弧罷了。,5.5 有向網(wǎng)的最短路徑,5.5.1 單源最短路徑 5.5.2 所有頂點(diǎn)對之間的最短路徑,單源最短路徑,所謂單源最短路徑，是指從一個(gè)頂點(diǎn)（源點(diǎn)）出發(fā)到其它各頂點(diǎn)的最短路徑，即給定有向網(wǎng)G和源點(diǎn)vk，求從vk到G 中其它各頂點(diǎn)vj(j=1,2,n, jk)的最短路徑。 迪杰斯特拉(E.W.Dijkstra)提出了一種按路徑長度遞增的次序產(chǎn)生最短路徑的算法。 其基本思想是，把網(wǎng)中所有頂點(diǎn)分成兩組，第一組是已確定最短路徑的頂點(diǎn)集合S，第二組是尚未確定最短路徑的頂點(diǎn)集合V；把V中的頂點(diǎn)按最短路徑長度遞增的順序逐個(gè)添加到S中，添加過程中始終保持從vk到S中每個(gè)頂點(diǎn)的最短路徑長度都不大于從vk到V中任何頂點(diǎn)的最短路徑長度，直到從vk出發(fā)可以到達(dá)的頂點(diǎn)都在S中時(shí)止。,單源最短路徑（續(xù)）,一開始時(shí)，S中只有頂點(diǎn)vk，其余頂點(diǎn)在V中。 這里引入一維輔助數(shù)組dist，用disti表示在當(dāng)前時(shí)刻所找到的從源點(diǎn)vk到每個(gè)終點(diǎn)vi的最短路徑長度；其初始值為：distk=0，若存在弧則disti為其弧上的權(quán)值，否則從vk到vi無弧時(shí)distk=。 然后每次從V中的頂點(diǎn)中選取一個(gè)dist值最小的頂點(diǎn)vj（distj=mindisti|viV）加入到S中；并對V中頂點(diǎn)的dist值進(jìn)行相應(yīng)修正，即若以加入S中的頂點(diǎn)vj做中間頂點(diǎn)使得V中某頂點(diǎn)的dist值更小時(shí)要相應(yīng)修改該頂點(diǎn)的dist值。這樣從V中選一個(gè)頂點(diǎn)加入S中，對V中頂點(diǎn)的dist值修改一遍，只需做n-1次就可求得從vk到其余各頂點(diǎn)的最短路徑。,單源最短路徑（續(xù)）,在求最短路徑的過程中，最短路徑長度已記在dist數(shù)組中，同時(shí)需要把路徑也記下來。 為此我們設(shè)一維數(shù)組pre，prei中存放從vk到vi的路徑上vi前一個(gè)頂點(diǎn)的序號；若從vk到vi無路徑可達(dá)，則vi的前一個(gè)頂點(diǎn)序號用0表示（即prei=0）。 在算法結(jié)束時(shí)，沿著頂點(diǎn)vi對應(yīng)的prei向前追溯就能確定從vk到vi的最短路徑，其最短路徑長度為disti。 設(shè)有向網(wǎng)用鄰接矩陣a表示，ai,j表示弧上的權(quán)值，無弧時(shí)ai,j為max；ai,i=0，當(dāng)vi進(jìn)入S 中時(shí)用ai,i=1來標(biāo)識。,最短路徑的Dijkstra算法描述,求有向網(wǎng)中從頂點(diǎn)vk出發(fā)到其它各頂點(diǎn)的最短路徑的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<max) 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最小的頂點(diǎn)*/ if (aii=0 /*dijkstra*/,最短路徑的Dijkstra算法舉例,最短路徑的Dijkstra算法舉例(續(xù)),使用Dijkstra算法對于前圖中所示的有向圖G8，求從頂點(diǎn)v1到其它各頂點(diǎn)的最短路徑及其算法執(zhí)行過程中dist數(shù)組和pre數(shù)組的變化情況如下表所示。,最短路徑的Dijkstra算法舉例(續(xù)),各頂點(diǎn)進(jìn)入S中的順序?yàn)関1，v3，v5，v4，v6；最終v2仍留在V中未進(jìn)入S中，說明從v1沒有路徑到達(dá)v2。要求從v1到某個(gè)頂點(diǎn)vi的最短路徑，可由prei回溯得到。 例如求v1到v6的最短路徑，可由pre6=4，pre4=5，pre5=1得到最短路徑為v1v5v4v6，路徑長度為dist6=60。,5.5 有向網(wǎng)的最短路徑,5.5.1 單源最短路徑 5.5.2 所有頂點(diǎn)對之間的最短路徑,所有頂點(diǎn)對之間的最短路徑,求所有頂點(diǎn)對之間的最短路徑的顯而易見的方法是，每次以一個(gè)頂點(diǎn)為源點(diǎn)重復(fù)執(zhí)行Dijkstra算法n 次來求得，總的執(zhí)行時(shí)間為O(n3)。 下面介紹的是由費(fèi)洛伊德（E.W.Floyd）提出的另一個(gè)算法。該算法也是用鄰接矩陣a表示有向網(wǎng)，其時(shí)間復(fù)雜度也是O(n3)，但在形式上更簡單些。,Floyd算法的基本思想,Floyd算法的基本思想是： 從鄰接矩陣a開始進(jìn)行n次迭代，第一次迭代后ai,j的值是從vi到vj且中間不經(jīng)過編號大于1的頂點(diǎn)（即v2到vn）的最短路徑長度；第k次迭代后ai,j的值是從vi到vj且中間不經(jīng)過編號大于k的頂點(diǎn)（即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次迭代時(shí)加入頂點(diǎn)vk后，存在從vi到vk和從vk到vj的兩條路徑，且長度之和小于迭代前從vi到vj的路徑長度，則更新為新路徑的值，否則保留原有的值。,迭代公式直觀地表示,迭代公式可以直觀地表示為下圖所示，圖中用波浪線表示一條路徑。,Floyd算法,為了實(shí)現(xiàn)Floyd算法，還需引入一個(gè)矩陣path。 pathi,j是從vi到vj的最短路徑上vj前一個(gè)頂點(diǎn)的序號，并約定從vi到vj無路徑時(shí)pathi,j=0。 在求得最短路徑后由pathi,j的值向前追溯，可以得到從vi到vj的最短路徑。,Floyd算法的形式化描述,void floyd (int a,int p,int n) /*求有向網(wǎng)中所有頂點(diǎn)對之間的最短路徑*/ 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(aij<max) 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+akj<aij) aij=aik+akj; pathij=pathkj; /*floyd*/,Floyd算法舉例,Floyd算法舉例(續(xù)),用Floyd算法求前圖所示有向網(wǎng)G9中所有頂點(diǎn)對之間的最短路徑及長度的過程如下表所示。,Floyd算法舉例(續(xù)),由矩陣path可知任一頂點(diǎn)對之間的最短路徑。 例如v1到v3的最短路徑，由path1,3=1知v3的前一個(gè)頂點(diǎn)是v1，即只有一步v1v3，其長度為a1,3=8； 又如求v3到v2的最短路徑，由path3,2=1知v2的前一個(gè)頂點(diǎn)是v1，由path3,1=3知v1的前一個(gè)頂點(diǎn)是v3，即只有兩步路，v3v1v2，其長度為a3,2=3； 再如求v3到v4的最短路徑，由path3,4=2知v4前一個(gè)頂點(diǎn)是v2，由path3,2=1知v2前一個(gè)頂點(diǎn)是v1，由path3,1=3知v1前一個(gè)頂點(diǎn)是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圖，它是一類比有向樹更一般的特殊有向圖。 下圖給出了有向樹、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)*e) 利用有向無環(huán)圖則可實(shí)現(xiàn)對相同子式的共享，從而節(jié)省存儲空間，下圖給出了該表達(dá)式的有向無環(huán)圖。,判斷一個(gè)圖是否存在環(huán),要檢查一個(gè)有向圖是否存在環(huán)，比檢查一個(gè)無向圖是否存在環(huán)復(fù)雜。 對于無向圖來說，深度優(yōu)先搜索遍歷過程中若遇到回邊（即指向已訪問過頂點(diǎn)的邊）則必定存在環(huán)。 對于有向圖來說，深度優(yōu)先搜索遍歷過程中遇到的回邊，有可能是指向深度優(yōu)先生成森林中的另一棵生成樹上頂點(diǎn)的弧，這種情況下不構(gòu)成環(huán)； 只有這個(gè)回邊是指向深度優(yōu)先森林中同一棵生成樹上頂點(diǎn)的弧，即從有向圖上的某個(gè)頂點(diǎn)v出發(fā)遍歷執(zhí)行dfs(v)結(jié)束之前出現(xiàn)回邊弧，由于u在生成樹上是v的子孫，有向圖必定存在包含頂點(diǎn)v和u的環(huán)。,有向無環(huán)圖的應(yīng)用,有向無環(huán)圖也是描述一項(xiàng)工程或系統(tǒng)進(jìn)展過程的有效工具。 除了最簡單的情況之外，幾乎所有的工程（project）都可分為若干個(gè)活動（activity）的子工程，而這些子工程之間通常受著一定條件的約束，其中某些子工程的開始必須在另外一些子工程的完成之后。 對整個(gè)工程和系統(tǒng)，人們所關(guān)心的是兩個(gè)方面的問題： 一是工程能否順利進(jìn)展， 二是預(yù)期完成整個(gè)工程所必須花費(fèi)的時(shí)間最短； 對應(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)用舉例,如果在有向圖中用頂點(diǎn)表示活動而用弧表示活動間的優(yōu)先關(guān)系，人們稱該有向圖為頂點(diǎn)表示活動的網(wǎng)（activity on vertex network），簡稱為AOV網(wǎng)。 例如，軟件工程專業(yè)的學(xué)生必須學(xué)習(xí)一組基礎(chǔ)課程和專業(yè)基礎(chǔ)課程。其中有些基礎(chǔ)課程是獨(dú)立于其它課程的，如高等數(shù)學(xué)和高級語言程序設(shè)計(jì)；有些課程必須在學(xué)完其先導(dǎo)課程后才能開始學(xué)習(xí)，如在學(xué)完高級語言程序設(shè)計(jì)和離散數(shù)學(xué)之后才能學(xué)習(xí)算法與數(shù)據(jù)結(jié)構(gòu)。 若用頂點(diǎn)表示課程，用弧表示課程之間的先后修關(guān)系（即弧表示課程j的先修課程是i）。,AOV網(wǎng)的應(yīng)用舉例示圖,AOV網(wǎng),AOV網(wǎng)中的關(guān)系是頂點(diǎn)集合上的偏序關(guān)系。 回憶前導(dǎo)課程離散數(shù)學(xué)中關(guān)于偏序關(guān)系的定義，集合X上的偏序關(guān)系R是指R是自反的、反對稱的和可傳遞的。 如上例課程之間的先后修關(guān)系滿足自反性、反對稱性和可傳遞性，課程間的先后修關(guān)系是課程集合上的偏序關(guān)系。,拓?fù)渑判?偏序關(guān)系是集合中僅有部分成員之間可比較； 如果集合中全體成員之間都可以比較，則為全序關(guān)系，即設(shè)R是集合X上的偏序關(guān)系，如果對每個(gè)x、yX必有xRy或yRx，則稱R是集合X 上的全序關(guān)系。這個(gè)全序稱作拓?fù)溆行颍╰opological order）； 由偏序定義得到拓?fù)溆行虻牟僮鞣Q作拓?fù)渑判?topological sort)。,AOV網(wǎng)與拓?fù)渑判?AOV網(wǎng)應(yīng)是有向無環(huán)圖即DAG圖。 這是因?yàn)楣こ讨械母髯庸こ蹋ɑ顒樱┫群笥行虿豢赡艽嬖诃h(huán)，若存在環(huán)意味著一個(gè)子工程以自身的后續(xù)子工程的完成為開始條件的謬論，如上例軟件工程專業(yè)的一組課程之間不可能存在以自身的后修課程作為前導(dǎo)課程的課程。 所以，對設(shè)計(jì)的工程流程圖即給定的AOV網(wǎng)，首先要檢查它是否存在環(huán)路。檢查的辦法是構(gòu)造它的頂點(diǎn)的拓?fù)溆行蛐蛄?。若AOV網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)中必定不存在環(huán)。,AOV網(wǎng)與拓?fù)渑判蚴纠?如下圖中的AOV網(wǎng)可以有如下拓?fù)溆行蛐蛄校?c1c2c3c4c5c6c7c8c9c10c11 和 c2c3c4c1c5c6c11c9c7c8c10 當(dāng)然還可以構(gòu)造出其它一些拓?fù)溆行蛐蛄小?拓?fù)溆行蛐蛄械奶攸c(diǎn),所構(gòu)造出的拓?fù)溆行蛐蛄械奶攸c(diǎn)是： 在AOV網(wǎng)中，若頂點(diǎn)i領(lǐng)先于頂點(diǎn)j，則在拓?fù)溆行蛐蛄兄腥匀活I(lǐng)先； 對于網(wǎng)中無領(lǐng)先關(guān)系的頂點(diǎn)i和j，在拓?fù)溆行蛐蛄兄薪⒁粋€(gè)領(lǐng)先關(guān)系，或者i領(lǐng)先于j，或者j領(lǐng)先于i。 拓?fù)渑判蚓褪怯葾OV網(wǎng)中頂點(diǎn)集合上的偏序關(guān)系得到該集合上的一個(gè)全序關(guān)系的操作。對于任何一項(xiàng)工程中各個(gè)子工程（活動）的安排，必須按照其中某一個(gè)拓?fù)溆行蛐蛄兄械捻樞蜻M(jìn)行安排。,AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê筒襟E,對AOV網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê筒襟E如下： 從AOV網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)輸出它； 從網(wǎng)中刪去該頂點(diǎn)和以它為尾（即從它出發(fā)）的所有弧； 重復(fù)和，直到網(wǎng)中不存在入度為0的頂點(diǎn)時(shí)止。 操作的結(jié)果有兩種可能，一種是網(wǎng)中全部頂點(diǎn)均已經(jīng)輸出，拓?fù)渑判蛲瓿?；一種是有剩余頂點(diǎn)未被輸出，但無入度為0的頂點(diǎn)，說明網(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和弧，；此時(shí)v3和v4入度為0，選擇其一如v4輸出，刪除v4和??；現(xiàn)在只有v3入度為0，輸出v3并刪除v3和弧與；對最后剩下的兩個(gè)入度為0的孤立頂點(diǎn)v2和v5分別輸出，就完成了拓?fù)渑判颉?其過程如右下圖所示，得到的拓?fù)溆行蛐蛄袨関6v1v4v3v2v5。,拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn),拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)：對AOV網(wǎng)采用鄰接表存儲結(jié)構(gòu)，并且在表頭結(jié)點(diǎn)中增加一個(gè)域indegree來存放頂點(diǎn)的入度。選擇并輸出一個(gè)入度為0的頂點(diǎn)可通過查表頭數(shù)組實(shí)現(xiàn)，而刪除頂點(diǎn)和以它為尾的弧的操作用弧頭頂點(diǎn)的入度減1來實(shí)現(xiàn)。 AOV網(wǎng)的鄰接表的表示如下圖所示：,拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)舉例,例如，在右圖的AOV網(wǎng)中，其中v6的入度為0，在輸出v6后可將v4和v5的入度分別由2和3減為1和2。為了避免重復(fù)檢測入度為0的頂點(diǎn)，可把所有入度為0的頂點(diǎn)保存于一鏈棧中，每當(dāng)輸出從棧中彈出一個(gè)，每當(dāng)出現(xiàn)新的入度為0的頂點(diǎn)便壓入之。其算法步驟如下： 將所有入度為0的頂點(diǎn)入棧； 彈出棧頂元素輸出，并把各鄰接頂點(diǎn)的入度域值減1； 將新產(chǎn)生的入度為0的頂點(diǎn)入棧； 重復(fù)、兩步，直到?？諘r(shí)為止。,拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)（續(xù)）,在這里棧僅起保存入度為0的頂點(diǎn)的作用，入度為0的頂點(diǎn)誰先誰后無關(guān)緊要，故也可以用鏈隊(duì)列或數(shù)組來保存。 可借用值為0的入度域indegree存放鏈中的指針，把入度域?yàn)?的表頭結(jié)點(diǎn)鏈接起來形成鏈棧。,拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)舉例,對于前面所舉的示例AOV網(wǎng)的鄰接表，入度域初始狀態(tài)和棧狀態(tài)如右圖(a)所示； 執(zhí)行算法步驟后狀態(tài)如右圖所示，此時(shí)棧頂指針top指向頂點(diǎn)v6的表頭結(jié)點(diǎn)，其indegree域值為1（即指向頂點(diǎn)v1的表頭結(jié)點(diǎn)），而v1的表頭結(jié)點(diǎn)的indegree域值為0（即為鏈尾結(jié)點(diǎn)）； 執(zhí)行步驟后輸出v6，并將v5和v4的表頭結(jié)點(diǎn)的入度域減1，未產(chǎn)生入度為0的新頂點(diǎn)，步驟相當(dāng)于空操作；棧頂指針top=1，如右圖(c)所示； 再次執(zhí)行步驟輸出v1，并將v4，v3和v2的表頭結(jié)點(diǎn)的入度域減1，產(chǎn)生了兩個(gè)入度為0的新頂點(diǎn)v4和v3，執(zhí)行步驟后鏈棧中只有這兩個(gè)結(jié)點(diǎn)，棧頂指針top=3而v3的入度域?yàn)?指向v4，v4的入度域?yàn)?是鏈尾，如右圖(d)所示； 其余的依此類推，分表如右圖的(e)到(h)所示。,鄰接表的表結(jié)點(diǎn)和表頭結(jié)點(diǎn)的定義,AOV網(wǎng)的鄰接表的表結(jié)點(diǎn)和表頭結(jié)點(diǎn)的定義可形式化描述如下： typedef struct node /*表結(jié)點(diǎn)*/ int adjvex; struct node *next; nodetype; /*表結(jié)點(diǎn)類型*/ typedef struct frontnode /*表頭結(jié)點(diǎn)*/ vertextype data; int indegree; struct node *next frontnodetype; /*鄰接表結(jié)點(diǎn)類型*/ typedef frontnodetype adjlistmaxvernum; /*鄰接表類型*/,拓?fù)渑判蛩惴捎肅語言描述,拓?fù)渑判蛩惴捎肅語言描述如下。函數(shù)toposort值為0時(shí)說明AOV網(wǎng)中存在環(huán)路，無法給出所有頂點(diǎn)的拓?fù)溆行蛐蛄校环駝t為1時(shí)拓?fù)渑判虺晒?，輸出AOV網(wǎng)中全部頂點(diǎn)的拓?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) /