《數(shù)據(jù)結(jié)構(gòu)圖》課件

1、數(shù)據(jù)結(jié)構(gòu)圖,9.1 圖的基本概念,第9章 圖,9.2 圖的存儲(chǔ)結(jié)構(gòu),9.3 圖的遍歷,9.4 生成樹(shù)和最小生成樹(shù),9.5 最短路徑,9.6 拓?fù)渑判?本章小結(jié),9.7 AOE網(wǎng)與關(guān)鍵路徑,數(shù)據(jù)結(jié)構(gòu)圖,9.1 圖的基本概念 9.1.1 圖的定義 圖(Graph)G由兩個(gè)集合V(Vertex)和E(Edge)組成,記為G=(V,E),其中V是頂點(diǎn)的有限集合,記為V(G),E是連接V中兩個(gè)不同頂點(diǎn)(頂點(diǎn)對(duì))的邊的有限集合,記為E(G)。,數(shù)據(jù)結(jié)構(gòu)圖,在圖G中,如果代表邊的頂點(diǎn)對(duì)是無(wú)序的,則稱G為無(wú)向圖,無(wú)向圖中代表邊的無(wú)序頂點(diǎn)對(duì)通常用圓括號(hào)括起來(lái),用以表示一條無(wú)向邊。 如果表示邊的頂點(diǎn)對(duì)是有序的,則

2、稱G為有向圖,在有向圖中代表邊的頂點(diǎn)對(duì)通常用尖括號(hào)括起來(lái) 。,數(shù)據(jù)結(jié)構(gòu)圖,9.1.2 圖的基本術(shù)語(yǔ) 1. 端點(diǎn)和鄰接點(diǎn) 在一個(gè)無(wú)向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個(gè)端點(diǎn),并稱它們互為鄰接點(diǎn)。 在一個(gè)有向圖中,若存在一條邊,則稱此邊是頂點(diǎn)vi的一條出邊,同時(shí)也是頂點(diǎn)vj的一條入邊；稱vi和vj分別為此邊的起始端點(diǎn)(簡(jiǎn)稱為起點(diǎn))和終止端點(diǎn)(簡(jiǎn)稱終點(diǎn))；稱vi和vj互為鄰接點(diǎn)。,數(shù)據(jù)結(jié)構(gòu)圖,2. 頂點(diǎn)的度、入度和出度 在無(wú)向圖中,頂點(diǎn)所具有的邊的數(shù)目稱為該頂點(diǎn)的度。 在有向圖中,以頂點(diǎn)vi為終點(diǎn)的入邊的數(shù)目,稱為該頂點(diǎn)的入度。以頂點(diǎn)vi為始點(diǎn)的出邊的數(shù)目,稱為該頂點(diǎn)的出度。

3、一個(gè)頂點(diǎn)的入度與出度的和為該頂點(diǎn)的度。 若一個(gè)圖中有n個(gè)頂點(diǎn)和e條邊,每個(gè)頂點(diǎn)的度為di(1in),則有：,數(shù)據(jù)結(jié)構(gòu)圖,3. 完全圖 若無(wú)向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著一條邊,有向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著方向相反的兩條邊,則稱此圖為完全圖。 顯然,完全無(wú)向圖包含有條邊,完全有向圖包含有n(n-1)條邊。例如,圖(a)所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全無(wú)向圖,共有6條邊。圖(b)所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全有向圖,共有12條邊。,數(shù)據(jù)結(jié)構(gòu)圖,4. 稠密圖、稀疏圖 當(dāng)一個(gè)圖接近完全圖時(shí),則稱為稠密圖。相反,當(dāng)一個(gè)圖含有較少的邊數(shù)(即當(dāng)en(n-1)時(shí),則稱為稀疏圖。 5. 子圖 設(shè)有兩個(gè)圖G

4、=(V,E)和G=(V,E),若V是V的子集,即VV,且E是E的子集,即EE,則稱G是G的子圖。例如圖(b)是圖(a)的子圖,而圖(c)不是圖(a)的子圖。,數(shù)據(jù)結(jié)構(gòu)圖,6. 路徑和路徑長(zhǎng)度 在一個(gè)圖G=(V,E)中,從頂點(diǎn)vi到頂點(diǎn)vj的一條路徑是一個(gè)頂點(diǎn)序列(vi,vi1,vi2,vim,vj),若此圖G是無(wú)向圖,則邊(vi,vi1),(vi1,vi2),(vim-1,vim),(vim,vj)屬于E(G)；若此圖是有向圖,則,屬于E(G)。 路徑長(zhǎng)度是指一條路徑上經(jīng)過(guò)的邊的數(shù)目。若一條路徑上除開(kāi)始點(diǎn)和結(jié)束點(diǎn)可以相同外,其余頂點(diǎn)均不相同,則稱此路徑為簡(jiǎn)單路徑。例如,有圖中,(v0,v2,v

5、1)就是一條簡(jiǎn)單路徑,其長(zhǎng)度為2。,數(shù)據(jù)結(jié)構(gòu)圖,7. 回路或環(huán) 若一條路徑上的開(kāi)始點(diǎn)與結(jié)束點(diǎn)為同一個(gè)頂點(diǎn),則此路徑被稱為回路或環(huán)。開(kāi)始點(diǎn)與結(jié)束點(diǎn)相同的簡(jiǎn)單路徑被稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。 例如,右圖中,(v0,v2,v1,v0)就是一條簡(jiǎn)單回路,其長(zhǎng)度為3。,數(shù)據(jù)結(jié)構(gòu)圖,8. 連通、連通圖和連通分量 在無(wú)向圖G中,若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱vi和vj是連通的。 若圖G中任意兩個(gè)頂點(diǎn)都連通,則稱G為連通圖,否則稱為非連通圖。 無(wú)向圖G中的極大連通子圖稱為G的連通分量。顯然,任何連通圖的連通分量只有一個(gè),即本身,而非連通圖有多個(gè)連通分量。,數(shù)據(jù)結(jié)構(gòu)圖,9. 強(qiáng)連通圖和強(qiáng)連通分量 在有向圖G中,

6、若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱從vi到vj是連通的。 若圖G中的任意兩個(gè)頂點(diǎn)vi和vj都連通,即從vi到vj和從vj到vi都存在路徑,則稱圖G是強(qiáng)連通圖。例如,右邊兩個(gè)圖都是強(qiáng)連通圖。 有向圖G中的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。顯然,強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量,即本身,非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。,數(shù)據(jù)結(jié)構(gòu)圖,10. 權(quán)和網(wǎng) 圖中每一條邊都可以附有一個(gè)對(duì)應(yīng)的數(shù)值,這種與邊相關(guān)的數(shù)值稱為權(quán)。權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或花費(fèi)的代價(jià)。邊上帶有權(quán)的圖稱為帶權(quán)圖,也稱作網(wǎng)。,數(shù)據(jù)結(jié)構(gòu)圖,例9.1 有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多需要多少條邊？最少需要多 少條邊？,答：有n個(gè)頂點(diǎn)的有向強(qiáng)連

7、通圖最多有n(n-1)條邊(構(gòu)成一個(gè)有向完全圖的情況)；最少有n條邊(n個(gè)頂點(diǎn)依次首尾相接構(gòu)成一個(gè)環(huán)的情況)。,數(shù)據(jù)結(jié)構(gòu)圖,9.2 圖的存儲(chǔ)結(jié)構(gòu),9.2.1 鄰接矩陣存儲(chǔ)方法 鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n(n0)個(gè)頂點(diǎn)的圖,頂點(diǎn)的順序依次為(v0,v1,vn-1),則G的鄰接矩陣A是n階方陣,其定義如下： (1) 如果G是無(wú)向圖,則： Aij= 1:若(vi,vj)E(G) 0:其他 (2) 如果G是有向圖,則： Aij= 1:若E(G) 0:其他,數(shù)據(jù)結(jié)構(gòu)圖,(3) 如果G是帶權(quán)無(wú)向圖,則： Aij= wij :若vivj且(vi,vj)E(G) :其他 (

8、4) 如果G是帶權(quán)有向圖,則： Aij= wij :若vivj且E(G) :其他,數(shù)據(jù)結(jié)構(gòu)圖,鄰接矩陣的特點(diǎn)如下： (1) 圖的鄰接矩陣表示是惟一的。 (2) 無(wú)向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。因此,按照壓縮存儲(chǔ)的思想,在具體存放鄰接矩陣時(shí)只需存放上(或下)三角形陣的元素即可。 (3) 不帶權(quán)的有向圖的鄰接矩陣一般來(lái)說(shuō)是一個(gè)稀疏矩陣,因此,當(dāng)圖的頂點(diǎn)較多時(shí),可以采用三元組表的方法存儲(chǔ)鄰接矩陣。 (4) 對(duì)于無(wú)向圖,鄰接矩陣的第i行(或第i列)非零元素(或非元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)vi的度。,數(shù)據(jù)結(jié)構(gòu)圖,(5) 對(duì)于有向圖,鄰接矩陣的第i行(或第i列)非零元素(或非元素)的個(gè)數(shù)正好是第i個(gè)

9、頂點(diǎn)vi的出度(或入度)。 (6) 用鄰接矩陣方法存儲(chǔ)圖,很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連。但是,要確定圖中有多少條邊,則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測(cè),所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣存儲(chǔ)圖的局限性。,數(shù)據(jù)結(jié)構(gòu)圖,鄰接矩陣的數(shù)據(jù)類(lèi)型定義如下： #define MAXV typedef struct int no;/*頂點(diǎn)編號(hào)*/ InfoType info; /*頂點(diǎn)其他信息*/ VertexType;/*頂點(diǎn)類(lèi)型*/ typedef struct /*圖的定義*/ int edgesMAXVMAXV; /*鄰接矩陣*/ int vexnum,arcnum; /*頂點(diǎn)數(shù),弧數(shù)

10、*/ VertexType vexsMAXV;/*存放頂點(diǎn)信息*/ MGraph;,數(shù)據(jù)結(jié)構(gòu)圖,9.2.2 鄰接表存儲(chǔ)方法 圖的鄰接表存儲(chǔ)方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)方法。在鄰接表中,對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表,第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊(對(duì)有向圖是以頂點(diǎn)vi為尾的弧)。每個(gè)單鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn)。表結(jié)點(diǎn)和表頭結(jié)點(diǎn)的結(jié)構(gòu)如下： 表結(jié)點(diǎn) 表頭結(jié)點(diǎn),數(shù)據(jù)結(jié)構(gòu)圖,其中,表結(jié)點(diǎn)由三個(gè)域組成,adjvex指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置,nextarc指示下一條邊或弧的結(jié)點(diǎn),info存儲(chǔ)與邊或弧相關(guān)的信息,如權(quán)值等。表頭結(jié)點(diǎn)由兩個(gè)域組成,data存儲(chǔ)頂點(diǎn)vi的名稱或其他

11、信息,firstarc指向鏈表中第一個(gè)結(jié)點(diǎn)。,數(shù)據(jù)結(jié)構(gòu)圖,鄰接表的特點(diǎn)如下： (1) 鄰接表表示不惟一。這是因?yàn)樵诿總€(gè)頂點(diǎn)對(duì)應(yīng)的單鏈表中,各邊結(jié)點(diǎn)的鏈接次序可以是任意的,取決于建立鄰接表的算法以及邊的輸入次序。 (2) 對(duì)于有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,其鄰接表有n個(gè)頂點(diǎn)結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)。顯然,在總的邊數(shù)小于n(n-1)/2的情況下,鄰接表比鄰接矩陣要節(jié)省空間。 (3) 對(duì)于無(wú)向圖,鄰接表的頂點(diǎn)vi對(duì)應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目正好是頂點(diǎn)vi的度。 (4) 對(duì)于有向圖,鄰接表的頂點(diǎn)vi對(duì)應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目?jī)H僅是vi的出度。其入度為鄰接表中所有adjvex域值為i的邊結(jié)點(diǎn)數(shù)目。,數(shù)據(jù)結(jié)構(gòu)圖

12、,鄰接表存儲(chǔ)結(jié)構(gòu)的定義如下： typedef struct ANode /*弧的結(jié)點(diǎn)結(jié)構(gòu)類(lèi)型*/ int adjvex; /*該弧的終點(diǎn)位置*/ struct ANode *nextarc; /*指向下一條弧的指針*/ InfoType info; /*該弧的相關(guān)信息*/ ArcNode; typedef struct Vnode /*鄰接表頭結(jié)點(diǎn)的類(lèi)型*/ Vertex data; /*頂點(diǎn)信息*/ ArcNode *firstarc; /*指向第一條弧*/ VNode; typedef VNode AdjListMAXV;/*AdjList是鄰接表類(lèi)型*/ typedef struct A

13、djList adjlist; /*鄰接表*/ int n,e; /*圖中頂點(diǎn)數(shù)n和邊數(shù)e*/ ALGraph; /*圖的類(lèi)型*/,數(shù)據(jù)結(jié)構(gòu)圖,例9.2 給定一個(gè)具有n個(gè)結(jié)點(diǎn)的無(wú)向圖的鄰接矩陣和鄰接表。 (1) 設(shè)計(jì)一個(gè)將鄰接矩陣轉(zhuǎn)換為鄰接表的算法； (2) 設(shè)計(jì)一個(gè)將鄰接表轉(zhuǎn)換為鄰接矩陣的算法； (3) 分析上述兩個(gè)算法的時(shí)間復(fù)雜度。 解：(1)在鄰接矩陣上查找值不為0的元素,找到這樣的元素后創(chuàng)建一個(gè)表結(jié)點(diǎn)并在鄰接表對(duì)應(yīng)的單鏈表中采用前插法插入該結(jié)點(diǎn)。算法如下：,數(shù)據(jù)結(jié)構(gòu)圖,void MatToList(MGraph g,ALGraph * ,數(shù)據(jù)結(jié)構(gòu)圖,(2) 在鄰接表上查找相鄰結(jié)點(diǎn),找到

14、后修改相應(yīng)鄰接矩陣元素的值。算法如下： void ListToMat(ALGraph *G,MGraph ,數(shù)據(jù)結(jié)構(gòu)圖,(3) 算法1的時(shí)間復(fù)雜度均為O(n2)。算法2的時(shí)間復(fù)雜度為O(n+e),其中e為圖的邊數(shù)。,數(shù)據(jù)結(jié)構(gòu)圖,9.3 圖的遍歷 9.3.1 圖的遍歷的概念 從給定圖中任意指定的頂點(diǎn)(稱為初始點(diǎn))出發(fā),按照某種搜索方法沿著圖的邊訪問(wèn)圖中的所有頂點(diǎn),使每個(gè)頂點(diǎn)僅被訪問(wèn)一次,這個(gè)過(guò)程稱為圖的遍歷。如果給定圖是連通的無(wú)向圖或者是強(qiáng)連通的有向圖,則遍歷過(guò)程一次就能完成,并可按訪問(wèn)的先后順序得到由該圖所有頂點(diǎn)組成的一個(gè)序列。 根據(jù)搜索方法的不同,圖的遍歷方法有兩種：一種叫做深度優(yōu)先搜索法(

15、DFS)；另一種叫做廣度優(yōu)先搜索法(BFS)。,數(shù)據(jù)結(jié)構(gòu)圖,9.3.2 深度優(yōu)先搜索遍歷 深度優(yōu)先搜索遍歷的過(guò)程是：從圖中某個(gè)初始頂點(diǎn)v出發(fā),首先訪問(wèn)初始頂點(diǎn)v,然后選擇一個(gè)與頂點(diǎn)v相鄰且沒(méi)被訪問(wèn)過(guò)的頂點(diǎn)w為初始頂點(diǎn),再?gòu)膚出發(fā)進(jìn)行深度優(yōu)先搜索,直到圖中與當(dāng)前頂點(diǎn)v鄰接的所有頂點(diǎn)都被訪問(wèn)過(guò)為止。顯然,這個(gè)遍歷過(guò)程是個(gè)遞歸過(guò)程。 以鄰接表為存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先搜索遍歷算法如下(其中,v是初始頂點(diǎn)編號(hào),visited是一個(gè)全局?jǐn)?shù)組,初始時(shí)所有元素均為0表示所有頂點(diǎn)尚未訪問(wèn)過(guò))：,數(shù)據(jù)結(jié)構(gòu)圖,void DFS(ALGraph *G,int v) ArcNode *p; visitedv=1; /*置已

16、訪問(wèn)標(biāo)記*/ printf(%d ,v); /*輸出被訪問(wèn)頂點(diǎn)的編號(hào)*/ p=G-adjlistv.firstarc; /*p指向頂點(diǎn)v的第一條弧的弧頭結(jié)點(diǎn)*/ while (p!=NULL) if (visitedp-adjvex=0) DFS(G,p-adjvex); /*若p-adjvex頂點(diǎn)未訪問(wèn),遞歸訪問(wèn)它*/ p=p-nextarc; /*p指向頂點(diǎn)v的下一條弧的弧頭結(jié)點(diǎn)*/ ,數(shù)據(jù)結(jié)構(gòu)圖,例如,以上圖的鄰接表為例調(diào)用DFS()函數(shù),假設(shè)初始頂點(diǎn)編號(hào)v=2,給出調(diào)用DFS()的執(zhí)行過(guò)程,見(jiàn)教材。,數(shù)據(jù)結(jié)構(gòu)圖,9.3.3 廣度優(yōu)先搜索遍歷 廣度優(yōu)先搜索遍歷的過(guò)程是：首先訪問(wèn)初始點(diǎn)vi

17、,接著訪問(wèn)vi的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)vi1,vi2,vit,然后再按照vi1,vi2,vit的次序,訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接點(diǎn),依次類(lèi)推,直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。 以鄰接表為存儲(chǔ)結(jié)構(gòu),用廣度優(yōu)先搜索遍歷圖時(shí),需要使用一個(gè)隊(duì)列,以類(lèi)似于按層次遍歷二叉樹(shù)遍歷圖。對(duì)應(yīng)的算法如下(其中,v是初始頂點(diǎn)編號(hào))：,數(shù)據(jù)結(jié)構(gòu)圖,void BFS(ALGraph *G,int v) ArcNode *p; int w,i; int queueMAXV,front=0,rear=0;/*定義循環(huán)隊(duì)列*/ int visitedMAXV; /*定義存放結(jié)點(diǎn)的訪問(wèn)標(biāo)志的數(shù)

18、組*/ for (i=0;in;i+) visitedi=0; /*訪問(wèn)標(biāo)志數(shù)組初始化*/ printf(%2d,v); /*輸出被訪問(wèn)頂點(diǎn)的編號(hào)*/ visitedv=1; /*置已訪問(wèn)標(biāo)記*/ rear=(rear+1)%MAXV; queuerear=v; /*v進(jìn)隊(duì)*/,數(shù)據(jù)結(jié)構(gòu)圖,while (front!=rear) /*若隊(duì)列不空時(shí)循環(huán)*/ front=(front+1)%MAXV; w=queuefront; /*出隊(duì)并賦給w*/ p=G-adjlistw.firstarc; /*找w的第一個(gè)的鄰接點(diǎn)*/ while (p!=NULL) if (visitedp-adjvex=

19、0) printf(“%2d”,p-adjvex); /*訪問(wèn)之*/ visitedp-adjvex=1; rear=(rear+1)%MAXV;/*該頂點(diǎn)進(jìn)隊(duì)*/ queuerear=p-adjvex; p=p-nextarc; /*找下一個(gè)鄰接頂點(diǎn)*/ printf(n); ,數(shù)據(jù)結(jié)構(gòu)圖,例如,以上圖的鄰接表為例調(diào)用BFS()函數(shù),假設(shè)初始頂點(diǎn)編號(hào)v=2,給出調(diào)用BFS()的執(zhí)行過(guò)程,見(jiàn)教材。,數(shù)據(jù)結(jié)構(gòu)圖,9.3.4 非連通圖的遍歷 對(duì)于無(wú)向圖來(lái)說(shuō),若無(wú)向圖是連通圖,則一次遍歷能夠訪問(wèn)到圖中的所有頂點(diǎn)； 但若無(wú)向圖是非連通圖,則只能訪問(wèn)到初始點(diǎn)所在連通分量中的所有頂點(diǎn),其他連通分量中的頂點(diǎn)

20、是不可能訪問(wèn)到的。為此需要從其他每個(gè)連通分量中選擇初始點(diǎn),分別進(jìn)行遍歷,才能夠訪問(wèn)到圖中的所有頂點(diǎn)；,數(shù)據(jù)結(jié)構(gòu)圖,對(duì)于有向圖來(lái)說(shuō),若從初始點(diǎn)到圖中的每個(gè)頂點(diǎn)都有路徑,則能夠訪問(wèn)到圖中的所有頂點(diǎn)；否則不能訪問(wèn)到所有頂點(diǎn),為此同樣需要再選初始點(diǎn),繼續(xù)進(jìn)行遍歷,直到圖中的所有頂點(diǎn)都被訪問(wèn)過(guò)為止。,數(shù)據(jù)結(jié)構(gòu)圖,采用深度優(yōu)先搜索遍歷非連通無(wú)向圖的算法如下： DFS1(ALGraph *g) int i; for (i=0;in;i+) /*遍歷所有未訪問(wèn)過(guò)的頂點(diǎn)*/ if (visitedi=0) DFS(g,i); ,數(shù)據(jù)結(jié)構(gòu)圖,采用廣度優(yōu)先搜索遍歷非連通無(wú)向圖的算法如下： BFS1(ALGraph

21、*g) int i; for (i=0;in;i+) /*遍歷所有未訪問(wèn)過(guò)的頂點(diǎn)*/ if (visitedi=0) BFS(g,i); ,數(shù)據(jù)結(jié)構(gòu)圖,9.3.5 圖遍歷的應(yīng)用,例 假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，判斷無(wú)向圖G是否連通。若連通則返回1；否則返回0。 解：采用遍歷方式判斷無(wú)向圖G是否連通。這里用深度優(yōu)先遍歷方法，先給visited數(shù)組（為全局變量）置初值0，然后從0頂點(diǎn)開(kāi)始遍歷該圖。 在一次遍歷之后，若所有頂點(diǎn)i的visitedi均為1，則該圖是連通的；否則不連通。對(duì)應(yīng)的算法如下：,數(shù)據(jù)結(jié)構(gòu)圖,int Connect(ALGraph *G) /*判斷無(wú)向圖G的連通性*/ i

22、nt i,flag=1; for (i=0;in;i+)/*visited數(shù)組置初值*/ visitedi=0; DFS(G,0);/*調(diào)用DSF算法,從頂點(diǎn)0開(kāi)始深度優(yōu)先遍歷*/ for (i=0;in;i+) if (visitedi=0) flag=0; break; return flag; ,數(shù)據(jù)結(jié)構(gòu)圖,例 假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的長(zhǎng)度為l的所有簡(jiǎn)單路徑。,解：所謂簡(jiǎn)單路徑是指路徑上的頂點(diǎn)不重復(fù)。利用回溯的深度優(yōu)先搜索方法。 從頂點(diǎn)u開(kāi)始，進(jìn)行深度優(yōu)先搜索，在搜索過(guò)程中，需要把當(dāng)前的搜索線路記錄下來(lái)。為此設(shè)立一個(gè)數(shù)組path保存走過(guò)的路徑，用d記

23、錄走過(guò)的路徑長(zhǎng)度。若當(dāng)前掃描到的結(jié)點(diǎn)u等于v且路徑長(zhǎng)度為l時(shí)，表示找到了一條路徑，則輸出路徑path。 對(duì)應(yīng)的算法如下：,數(shù)據(jù)結(jié)構(gòu)圖,void PathAll(ALGraph *G,int u,int v,int l,int path,int d) /*d是到當(dāng)前為止已走過(guò)的路徑長(zhǎng)度，調(diào)用時(shí)初值為-1*/ int m,i; ArcNode *p; visitedu=1; d+; /*路徑長(zhǎng)度增1*/ pathd=u;/*將當(dāng)前頂點(diǎn)添加到路徑中*/ if (u=v /*恢復(fù)環(huán)境*/ ,數(shù)據(jù)結(jié)構(gòu)圖,void main() int pathMAXV,u=1,v=4,d=3,i,j; MGraph g

24、; ALGraph *G; g.n=5;g.e=6; int AMAXVMAXV= 0,1,0,1,0,1,0,1,0,0, 0,1,0,1,1, 1,0,1,0,1, 0,0,1,1,0 ; for (i=0;ig.n;i+)/*建立圖9.1(a)的鄰接矩陣*/ for (j=0;jg.n;j+) g.edgesij=Aij; MatToList(g,G); for (i=0;ig.n;i+) visitedi=0; printf(圖G:n);DispAdj(G);/*輸出鄰接表*/ printf(從%d到%d的所有長(zhǎng)度為%d路徑:n,u,v,d); PathAll(G,u,v,d,path

25、,-1); printf(n); ,數(shù)據(jù)結(jié)構(gòu)圖,程序執(zhí)行結(jié)果如下： 圖G: 0: 1 3 1: 0 2 2: 1 3 4 3: 0 2 4 4: 2 3 從1到4的所有長(zhǎng)度為3路徑: 1 0 3 4 1 2 3 4,1,3,2,4,0,數(shù)據(jù)結(jié)構(gòu)圖,9.4 生成樹(shù)和最小生成樹(shù) 9.4.1 生成樹(shù)的概念 一個(gè)連通圖的生成樹(shù)是一個(gè)極小連通子圖,它含有圖中全部頂點(diǎn),但只有構(gòu)成一棵樹(shù)的(n-1)條邊。 如果在一棵生成樹(shù)上添加一條邊,必定構(gòu)成一個(gè)環(huán)：因?yàn)檫@條邊使得它依附的那兩個(gè)頂點(diǎn)之間有了第二條路徑。一棵有n個(gè)頂點(diǎn)的生成樹(shù)(連通無(wú)回路圖)有且僅有(n-1)條邊,如果一個(gè)圖有n個(gè)頂點(diǎn)和小于(n-1)條邊,則

26、是非連通圖。如果它多于(n-1)條邊,則一定有回路。但是,有(n-1)條邊的圖不一定都是生成樹(shù)。,數(shù)據(jù)結(jié)構(gòu)圖,對(duì)于一個(gè)帶權(quán)(假定每條邊上的權(quán)均為大于零的實(shí)數(shù))連通無(wú)向圖G中的不同生成樹(shù),其每棵樹(shù)的所有邊上的權(quán)值之和也可能不同；圖的所有生成樹(shù)中具有邊上的權(quán)值之和最小的樹(shù)稱為圖的最小生成樹(shù)。 按照生成樹(shù)的定義,n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有n個(gè)頂點(diǎn)、n-1條邊。因此,構(gòu)造最小生成樹(shù)的準(zhǔn)則有三條： (1) 必須只使用該圖中的邊來(lái)構(gòu)造最小生成樹(shù)； (2) 必須使用且僅使用n-1條邊來(lái)連接圖中的n個(gè)頂點(diǎn)； (3) 不能使用產(chǎn)生回路的邊。,數(shù)據(jù)結(jié)構(gòu)圖,9.4.2 無(wú)向圖的連通分量和生成樹(shù) 在對(duì)無(wú)向圖進(jìn)行遍歷時(shí)

27、,對(duì)于連通圖,僅需調(diào)用遍歷過(guò)程(DFS或BFS)一次,從圖中任一頂點(diǎn)出發(fā),便可以遍歷圖中的各個(gè)頂點(diǎn)。對(duì)非連通圖,則需多次調(diào)用遍歷過(guò)程,每次調(diào)用得到的頂點(diǎn)集連同相關(guān)的邊就構(gòu)成圖的一個(gè)連通分量。 設(shè)G=(V,E)為連通圖,則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí),必定將E(G)分成兩個(gè)集合T和B,其中T是遍歷圖過(guò)程中走過(guò)的邊的集合,B是剩余的邊的集合：TB=,TB=E(G)。顯然,G=(V,T)是G的極小連通子圖,即G是G的一棵生成樹(shù)。,數(shù)據(jù)結(jié)構(gòu)圖,由深度優(yōu)先遍歷得到的生成樹(shù)稱為深度優(yōu)先生成樹(shù)；由廣度優(yōu)先遍歷得到的生成樹(shù)稱為廣度優(yōu)先生成樹(shù)。這樣的生成樹(shù)是由遍歷時(shí)訪問(wèn)過(guò)的n個(gè)頂點(diǎn)和遍歷時(shí)經(jīng)歷的n-1條邊組成。

28、對(duì)于非連通圖,每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過(guò)的邊一起構(gòu)成一棵生成樹(shù),各個(gè)連通分量的生成樹(shù)組成非連通圖的生成森林。,數(shù)據(jù)結(jié)構(gòu)圖,9.4.4 普里姆算法 普里姆(Prim)算法是一種構(gòu)造性算法。 假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖,T=(U,TE)是G的最小生成樹(shù),其中U是T的頂點(diǎn)集,TE是T的邊集,則由G構(gòu)造最小生成樹(shù)T的步驟如下：,數(shù)據(jù)結(jié)構(gòu)圖,(1) 初始化U=v0。v0到其他頂點(diǎn)的所有邊為候選邊； (2) 重復(fù)以下步驟n-1次,使得其他n-1個(gè)頂點(diǎn)被加入到U中： 從候選邊中挑選權(quán)值最小的邊輸出,設(shè)該邊在V-U中的頂點(diǎn)是v,將v加入U(xiǎn)中,刪除和v關(guān)聯(lián)的邊； 考察當(dāng)前V-U

29、中的所有頂點(diǎn)vi,修改候選邊：若(v,vi)的權(quán)值小于原來(lái)和vi關(guān)聯(lián)的候選邊,則用(v,vi)取代后者作為候選邊。,數(shù)據(jù)結(jié)構(gòu)圖,普里姆算法求解最小生成樹(shù)的過(guò)程,數(shù)據(jù)結(jié)構(gòu)圖,普里姆(Prim)算法如下： #define INF 32767 /*INF表示*/ void Prim(int costMAXV,int n,int v) int lowcostMAXV,min; int closestMAXV,i,j,k; for (i=0;in;i+) /*給lowcost和closest置初值*/ lowcosti=costvi; closesti=v; ,數(shù)據(jù)結(jié)構(gòu)圖,for (i=1;in;i+)

30、 /*找出n-1個(gè)頂點(diǎn)*/ min=INF; for (j=0;jn;j+) /*在(V-U)中找出離U最近的頂點(diǎn)k*/ if (lowcostj!=0 ,數(shù)據(jù)結(jié)構(gòu)圖,Prim()算法中有兩重for循環(huán),所以時(shí)間復(fù)雜度為O(n2)。,數(shù)據(jù)結(jié)構(gòu)圖,9.4.5 克魯斯卡爾算法 克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增次序選擇合適的邊來(lái)構(gòu)造最小生成樹(shù)的方法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖,T=(U,TE)是G的最小生成樹(shù),則構(gòu)造最小生成樹(shù)的步驟如下： (1) 置U的初值等于V(即包含有G中的全部頂點(diǎn)),TE的初值為空集(即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量)。 (2) 將

31、圖G中的邊按權(quán)值從小到大的順序依次選取：若選取的邊未使生成樹(shù)T形成回路,則加入TE；否則舍棄,直到TE中包含(n-1)條邊為止。,數(shù)據(jù)結(jié)構(gòu)圖,克魯斯卡爾算法求解最小生成樹(shù)的過(guò)程,數(shù)據(jù)結(jié)構(gòu)圖,為了簡(jiǎn)便,在實(shí)現(xiàn)克魯斯卡爾算法Kruskal()時(shí),參數(shù)E存放圖G中的所有邊,假設(shè)它們是按權(quán)值從小到大的順序排列的。n為圖G的頂點(diǎn)個(gè)數(shù),e為圖G的邊數(shù)。 typedef struct int u; /*邊的起始頂點(diǎn)*/ int v; /*邊的終止頂點(diǎn)*/ int w; /*邊的權(quán)值*/ Edge;,數(shù)據(jù)結(jié)構(gòu)圖,void Kruskal(Edge E,int n,int e) int i,j,m1,m2,sn

32、1,sn2,k; int vsetMAXV; for (i=0;in;i+) vseti=i;/*初始化輔助數(shù)組*/ k=1; /*k表示當(dāng)前構(gòu)造最小生成樹(shù)的第幾條邊,初值為1*/ j=0; /*E中邊的下標(biāo),初值為0*/ while (kn) /*生成的邊數(shù)小于n時(shí)循環(huán)*/ m1=Ej.u;m2=Ej.v; /*取一條邊的頭尾頂點(diǎn)*/ sn1=vsetm1;sn2=vsetm2; /*分別得到兩個(gè)頂點(diǎn)所屬的集合編號(hào)*/,數(shù)據(jù)結(jié)構(gòu)圖,if (sn1!=sn2) /*屬不同的集合-最小生成樹(shù)的一條邊*/ printf(%d,%d):%dn,m1,m2,Ej.w); k+; /*生成邊數(shù)增1*/

33、for (i=0;in;i+) /*兩個(gè)集合統(tǒng)一編號(hào)*/ if (vseti=sn2) /*集合編號(hào)為sn2的改為sn1*/ vseti=sn1; j+; /*掃描下一條邊*/ ,數(shù)據(jù)結(jié)構(gòu)圖,完整的克魯斯卡爾算法應(yīng)包括對(duì)邊按權(quán)值遞增排序，上述算法假設(shè)邊已排序的情況下，時(shí)間復(fù)雜度為O(n2)。 如果給定的帶權(quán)連通無(wú)向圖G有e條邊,n個(gè)頂點(diǎn)，采用堆排序(在第11章中介紹)對(duì)邊按權(quán)值遞增排序，那么用克魯斯卡爾算法構(gòu)造最小生成樹(shù)的時(shí)間復(fù)雜度降為O(elog2e)。 由于它與n無(wú)關(guān)，只與e有關(guān)，所以說(shuō)克魯斯卡爾算法適合于稀疏圖。,數(shù)據(jù)結(jié)構(gòu)圖,9.5 最短路徑 9.5.1 路徑的概念 在一個(gè)無(wú)權(quán)的圖中,若

34、從一頂點(diǎn)到另一頂點(diǎn)存在著一條路徑,則稱該路徑長(zhǎng)度為該路徑上所經(jīng)過(guò)的邊的數(shù)目,它等于該路徑上的頂點(diǎn)數(shù)減1。 由于從一頂點(diǎn)到另一頂點(diǎn)可能存在著多條路徑,每條路徑上所經(jīng)過(guò)的邊數(shù)可能不同,即路徑長(zhǎng)度不同,我們把路徑長(zhǎng)度最短(即經(jīng)過(guò)的邊數(shù)最少)的那條路徑叫做最短路徑,其路徑長(zhǎng)度叫做最短路徑長(zhǎng)度或最短距離。,數(shù)據(jù)結(jié)構(gòu)圖,對(duì)于帶權(quán)的圖,考慮路徑上各邊上的權(quán)值,則通常把一條路徑上所經(jīng)邊的權(quán)值之和定義為該路徑的路徑長(zhǎng)度或稱帶權(quán)路徑長(zhǎng)度。 從源點(diǎn)到終點(diǎn)可能不止一條路徑,把帶權(quán)路徑長(zhǎng)度最短的那條路徑稱為最短路徑,其路徑長(zhǎng)度(權(quán)值之和)稱為最短路徑長(zhǎng)度或者最短距離。,數(shù)據(jù)結(jié)構(gòu)圖,9.5.2 從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最

35、短路徑 問(wèn)題：給定一個(gè)帶權(quán)有向圖G與源點(diǎn)v,求從v到G中其他頂點(diǎn)的最短路徑,并限定各邊上的權(quán)值大于或等于0。,數(shù)據(jù)結(jié)構(gòu)圖,采用狄克斯特拉(Dijkstra)算法求解 基本思想是：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖, 把圖中頂點(diǎn)集合V分成兩組： 第一組為已求出最短路徑的頂點(diǎn)集合(用S表示,初始時(shí)S中只有一個(gè)源點(diǎn),以后每求得一條最短路徑v,vk,就將vk加入到集合S中,直到全部頂點(diǎn)都加入到S中,算法就結(jié)束了) 第二組為其余未確定最短路徑的頂點(diǎn)集合(用U表示)。,數(shù)據(jù)結(jié)構(gòu)圖,按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中,總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中

36、任何頂點(diǎn)的最短路徑長(zhǎng)度。 此外,每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離,S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度,U中的頂點(diǎn)的距離從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。,數(shù)據(jù)結(jié)構(gòu)圖,狄克斯特拉算法的具體步驟如下： (1) 初始時(shí),S只包含源點(diǎn),即S=v,v的距離為0。U包含除v外的其他頂點(diǎn),U中頂點(diǎn)u距離為邊上的權(quán)(若v與u有邊)或(若u不是v的出邊鄰接點(diǎn))。 (2) 從U中選取一個(gè)距離v最小的頂點(diǎn)k,把k加入S中(該選定的距離就是v到k的最短路徑長(zhǎng)度)。 (3) 以k為新考慮的中間點(diǎn),修改U中各頂點(diǎn)的距離：若從源點(diǎn)v到頂點(diǎn)u(uU)的距離(經(jīng)過(guò)頂點(diǎn)k)比原來(lái)距離(不經(jīng)過(guò)頂點(diǎn)k)短,則

37、修改頂點(diǎn)u的距離值,修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。 (4) 重復(fù)步驟(2)和(3)直到所有頂點(diǎn)都包含在S中。,數(shù)據(jù)結(jié)構(gòu)圖,V到j(luò)的最小距離MIN(cvk+wkj,cvj),數(shù)據(jù)結(jié)構(gòu)圖,S U dist path 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1,2,3,4,5,6 0,4,6,6, 0,0,0,0,-1,-1,-1 0,1 2,3,4,5,6 0,4,5,6,11, 0,0,1,0,1,-1,-1 0,1,2 3,4,5,6 0,4,5,6,11,9, 0,0,1,0,1,2,-1 0,1,2,3 4,5,6 0,4,5,6,11,9, 0,0,1,0

38、,1,2,-1 0,1,2,3,5 4,6 0,4,5,6,10,9,17 0,0,1,0,5,2,5 0,1,2,3,5,4 6 0,4,5,6,10,9,16 0,0,1,0,5,2,4 0,1,2,3,5,4,6 0,4,5,6,10,9,16 0,0,1,0,5,2,4,數(shù)據(jù)結(jié)構(gòu)圖,狄克斯特拉算法如下(n為圖G的頂點(diǎn)數(shù),v0為源點(diǎn)編號(hào))： void Dijkstra(int costMAXV,int n,int v0) int distMAXV,pathMAXV; int sMAXV;int mindis,i,j,u; for (i=0;in;i+) disti=costv0i; /*

39、距離初始化*/ si=0; /*s置空*/ if (costv0iINF)/*路徑初始化*/ pathi=v0; else pathi=-1; sv0=1;pathv0=0; /*源點(diǎn)編號(hào)v0放入s中*/,數(shù)據(jù)結(jié)構(gòu)圖,for (i=0;in;i+) /*循環(huán)直到所有頂點(diǎn)的最短路徑都求出*/ mindis=INF; u=-1; for (j=0;jn;j+) /*選取不在s中且具有最小距離的頂點(diǎn)u*/ if (sj=0 /*輸出最短路徑*/ ,數(shù)據(jù)結(jié)構(gòu)圖,void Ppath(int path,int i,int v0) /*前向遞歸查找路徑上的頂點(diǎn)*/ int k; k=pathi; if (

40、k=v0) return;/*找到了起點(diǎn)則返回*/ Ppath(path,k,v0);/*找k頂點(diǎn)的前一個(gè)頂點(diǎn)*/ printf(%d,k);/*輸出k頂點(diǎn)*/ ,數(shù)據(jù)結(jié)構(gòu)圖,void Dispath(int dist,int path,int s,int n,int v0) int i; for (i=0;in;i+) if (si=1) printf(“從%d到%d的最短路徑長(zhǎng)度為: %dt路徑為:,v0,i,disti); printf(%d,v0);/*輸出路徑上的起點(diǎn)*/ Ppath(path,i,v0);/*輸出路徑上的中間點(diǎn)*/ printf(%dn,i);/*輸出路徑上的終點(diǎn)*

41、/ else printf(從%d到%d不存在路徑n,v0,i); ,數(shù)據(jù)結(jié)構(gòu)圖,9.5.3 每對(duì)頂點(diǎn)之間的最短路徑 問(wèn)題：對(duì)于一個(gè)各邊權(quán)值均大于零的有向圖,對(duì)每一對(duì)頂點(diǎn)vivj,求出vi與vj之間的最短路徑和最短路徑長(zhǎng)度。 可以通過(guò)以每個(gè)頂點(diǎn)作為源點(diǎn)循環(huán)求出每對(duì)頂點(diǎn)之間的最短路徑。除此之外,弗洛伊德(Floyd)算法也可用于求兩頂點(diǎn)之間最短路徑。,數(shù)據(jù)結(jié)構(gòu)圖,假設(shè)有向圖G=(V,E)采用鄰接矩陣cost存儲(chǔ),另外設(shè)置一個(gè)二維數(shù)組A用于存放當(dāng)前頂點(diǎn)之間的最短路徑長(zhǎng)度,分量Aij表示當(dāng)前頂點(diǎn)vi到頂點(diǎn)vj的最短路徑長(zhǎng)度。 弗洛伊德算法的基本思想是遞推產(chǎn)生一個(gè)矩陣序列A0,A1,Ak,An,其中A

42、kij表示從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度。,數(shù)據(jù)結(jié)構(gòu)圖,初始時(shí),有A-1ij=costij。當(dāng)求從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k+1的最短路徑長(zhǎng)度時(shí),要分兩種情況考慮： 一種情況是該路徑不經(jīng)過(guò)頂點(diǎn)編號(hào)為k+1的頂點(diǎn),此時(shí)該路徑長(zhǎng)度與從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度相同； 另一種情況是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑上經(jīng)過(guò)編號(hào)為k+1的頂點(diǎn)。,數(shù)據(jù)結(jié)構(gòu)圖,Ak+1i,j=MIN(Aki,j,Aki,k+1+Akk+1,j,數(shù)據(jù)結(jié)構(gòu)圖,那么,該路徑可分為兩段: (1) 從頂點(diǎn)vi到頂點(diǎn)vk+1的最短路徑; (2

43、) 從頂點(diǎn)vk+1到頂點(diǎn)vj的最短路徑。 此時(shí)最短路徑長(zhǎng)度等于這兩段路徑長(zhǎng)度之和。這兩種情況中的較小值,就是所要求的從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k+1的最短路徑。,數(shù)據(jù)結(jié)構(gòu)圖,弗洛伊德思想可用如下的表達(dá)式來(lái)描述： A-1ij=costij Ak+1ij=MIN Akij, Akik+1+Akk+1j (0kn-1),數(shù)據(jù)結(jié)構(gòu)圖,采用弗洛伊德算法求解過(guò)程,數(shù)據(jù)結(jié)構(gòu)圖,考慮頂點(diǎn)v0,A0ij表示由vi到vj,經(jīng)由頂點(diǎn)v0的最短路徑。只有從v2到v1經(jīng)過(guò)v0的路徑和從v2到v3經(jīng)過(guò)v0的路徑,不影響v2到v1和v2到v3的路徑長(zhǎng)度,因此,有：,數(shù)據(jù)結(jié)構(gòu)圖,考慮頂點(diǎn)v1,A1ij

44、表示由vi到vj,經(jīng)由頂點(diǎn)v1的最短路徑。存在路徑v0-v1-v2,路徑長(zhǎng)度為9,將A02改為9,path02改為1,因此,有：,數(shù)據(jù)結(jié)構(gòu)圖,考慮頂點(diǎn)v2,A2ij表示由vi到vj,經(jīng)由頂點(diǎn)v2的最短路徑。存在路徑v3-v2-v0,長(zhǎng)度為4,將A30改為4；存在路徑v3-v2-v1,長(zhǎng)度為4,將A31改為4。存在路徑v1-v2-v0,長(zhǎng)度為7,將A10改為7。將path30、path31和path10均改為2。因此,有：,數(shù)據(jù)結(jié)構(gòu)圖,考慮頂點(diǎn)v3,A3ij表示由vi到vj,經(jīng)由頂點(diǎn)v3的最短路徑。存在路徑v0-v3-v2,長(zhǎng)度為8比原長(zhǎng)度短,將A02改為8；存在路徑v1-v3-v2-v0,長(zhǎng)度

45、為6(A13+A30=2+4=6)比原長(zhǎng)度短,將A10改為6；存在路徑v1-v3-v2,長(zhǎng)度為3,比原長(zhǎng)度短,將A12改為3；將path02、path10后path12均改為3。因此,有：,數(shù)據(jù)結(jié)構(gòu)圖,從0到0路徑為：0,0路徑長(zhǎng)度為：0 從0到1路徑為：0,1路徑長(zhǎng)度為：5 從0到2路徑為：0,3,2路徑長(zhǎng)度為：8 從0到3路徑為：0,3路徑長(zhǎng)度為：7 從1到0路徑為：1,3,2,0路徑長(zhǎng)度為：6 從1到1路徑為：1,1路徑長(zhǎng)度為：0 從1到2路徑為：1,3,2 路徑長(zhǎng)度為：3 從1到3路徑為：1,3路徑長(zhǎng)度為：2,A=,Path=,數(shù)據(jù)結(jié)構(gòu)圖,從2到0路徑為：2,0路徑長(zhǎng)度為：3 從2到1

46、路徑為：2,1路徑長(zhǎng)度為：3 從2到2路徑為：2,2路徑長(zhǎng)度為：0 從2到3路徑為：2,3路徑長(zhǎng)度為：2 從3到0路徑為：3,2,0 路徑長(zhǎng)度為：4 從3到1路徑為：3,2,1 路徑長(zhǎng)度為：4 從3到2路徑為：3,2路徑長(zhǎng)度為：1 從3到3路徑為：3,3路徑長(zhǎng)度為：0,數(shù)據(jù)結(jié)構(gòu)圖,弗洛伊德算法如下： void Floyd(int costMAXV,int n) int AMAXVMAXV,pathMAXVMAXV;int i,j,k; for (i=0;i(Aik+Akj) Aij=Aik+Akj; pathij=k; Dispath(A,path,n); /*輸出最短路徑*/ ,數(shù)據(jù)結(jié)構(gòu)圖,

47、9.6 拓?fù)渑判?設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖,V中頂點(diǎn)序列v1,v2,vn稱為一個(gè)拓?fù)湫蛄?當(dāng)且僅當(dāng)該頂點(diǎn)序列滿足下列條件： 若是圖中的邊(即從頂點(diǎn)vi到vj有一條路徑),則在序列中頂點(diǎn)vi必須排在頂點(diǎn)vj之前。 在一個(gè)有向圖中找一個(gè)拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判颉?數(shù)據(jù)結(jié)構(gòu)圖,例如,計(jì)算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè),假設(shè)這些課程的名稱與相應(yīng)代號(hào)有如下關(guān)系：,數(shù)據(jù)結(jié)構(gòu)圖,課程之間的先后關(guān)系可用有向圖表示 ：,數(shù)據(jù)結(jié)構(gòu)圖,對(duì)這個(gè)有向圖進(jìn)行拓?fù)渑判蚩傻玫揭粋€(gè)拓?fù)湫蛄校篊1-C3-C2-C4-C7-C6-C5。也可得到另一個(gè)拓?fù)湫蛄校篊2-C7-C1-C3-C4

48、-C5-C6,還可以得到其他的拓?fù)湫蛄?。學(xué)生按照任何一個(gè)拓?fù)湫蛄卸伎梢皂樞虻剡M(jìn)行課程學(xué)習(xí)。,數(shù)據(jù)結(jié)構(gòu)圖,拓?fù)渑判蚍椒ㄈ缦拢?(1) 從有向圖中選擇一個(gè)沒(méi)有前驅(qū)(即入度為0)的頂點(diǎn)并且輸出它。 (2) 從網(wǎng)中刪去該頂點(diǎn),并且刪去從該頂點(diǎn)發(fā)出的全部有向邊。 (3) 重復(fù)上述兩步,直到剩余的網(wǎng)中不再存在沒(méi)有前驅(qū)的頂點(diǎn)為止。,數(shù)據(jù)結(jié)構(gòu)圖,為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?對(duì)于給定的有向圖,采用鄰接表作為存儲(chǔ)結(jié)構(gòu),為每個(gè)頂點(diǎn)設(shè)立一個(gè)鏈表,每個(gè)鏈表有一個(gè)表頭結(jié)點(diǎn),這些表頭結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組,表頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域count。即將鄰接表定義中的VNode類(lèi)型修改如下： typedef struct /*表頭

49、結(jié)點(diǎn)類(lèi)型*/ Vertex data; /*頂點(diǎn)信息*/ int count; /*存放頂點(diǎn)入度*/ ArcNode *firstarc; /*指向第一條弧*/ VNode;,數(shù)據(jù)結(jié)構(gòu)圖,void TopSort(VNode adj,int n) int i,j;int StMAXV,top=-1; /*棧St的指針為top*/ ArcNode *p; for (i=0;i-1) /*棧不為空時(shí)循環(huán)*/ i=Sttop;top-; /*出棧*/ printf(%d ,i); p=adji.firstarc; while (p!=NULL) j=p-adjvex; adjj.count-; if

50、 (adjj.count=0) top+; Sttop=j; p=p-nextarc; /*找下一個(gè)相鄰頂點(diǎn)*/ ,數(shù)據(jù)結(jié)構(gòu)圖,9.7 AOE網(wǎng)與關(guān)鍵路徑 若用前面介紹過(guò)的帶權(quán)有向圖(DAG)描述工程的預(yù)計(jì)進(jìn)度,以頂點(diǎn)表示事件,有向邊表示活動(dòng),邊e的權(quán)c(e)表示完成活動(dòng)e所需的時(shí)間(比如天數(shù)),或者說(shuō)活動(dòng)e持續(xù)時(shí)間。 圖中入度為0的頂點(diǎn)表示工程的開(kāi)始事件(如開(kāi)工儀式),出度為0的頂點(diǎn)表示工程結(jié)束事件。則稱這樣的有向圖為AOE網(wǎng)(Activity On Edge)。,數(shù)據(jù)結(jié)構(gòu)圖,通常每個(gè)工程都只有一個(gè)開(kāi)始事件和一個(gè)結(jié)束事件,因此表示工程的AOE網(wǎng)都只有一個(gè)入度為0的頂點(diǎn),稱為源點(diǎn)(source

51、),和一個(gè)出度為0的頂點(diǎn),稱為匯點(diǎn)(converge)。 如果圖中存在多個(gè)入度為0的頂點(diǎn),只要加一個(gè)虛擬源點(diǎn),使這個(gè)虛擬源點(diǎn)到原來(lái)所有入度為0的點(diǎn)都有一條長(zhǎng)度為0的邊,變成只有一個(gè)源點(diǎn)。對(duì)存在多個(gè)出度為0的頂點(diǎn)的情況作類(lèi)似的處理。所以只需討論單源點(diǎn)和單匯點(diǎn)的情況。,數(shù)據(jù)結(jié)構(gòu)圖,在AOE網(wǎng)中,從源點(diǎn)到匯點(diǎn)的所有路徑中,具有最大路徑長(zhǎng)度的路徑稱為關(guān)鍵路徑。完成整個(gè)工程的最短時(shí)間就是網(wǎng)中關(guān)鍵路徑的長(zhǎng)度,也就是網(wǎng)中關(guān)鍵路徑上各活動(dòng)持續(xù)時(shí)間的總和,我們把關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。因此,只要找出AOE網(wǎng)中的關(guān)鍵活動(dòng),也就找到了關(guān)鍵路徑。 注意:在一個(gè)AOE網(wǎng)中,可以有不止一條的關(guān)鍵路徑。,數(shù)據(jù)結(jié)構(gòu)圖,

52、例如,下圖表示某工程的AOE網(wǎng)。共有9個(gè)事件和11項(xiàng)活動(dòng)。其中 A表示開(kāi)始事件,G表示結(jié)束事件。,數(shù)據(jù)結(jié)構(gòu)圖,幾個(gè)定義： (1) 事件v的最早可發(fā)生時(shí)間：假設(shè)事件x是源點(diǎn),事件y為匯點(diǎn),并規(guī)定事件x的發(fā)生時(shí)間為0。定義圖中任一事件v的最早(event early)可發(fā)生時(shí)間ve(v)等于x到v所有路徑長(zhǎng)度的最大值,即：,ve(v)=,上式中的MAX是對(duì)x到v的所有路徑p取最大值,c(p)表示路徑p的長(zhǎng)度(路徑上邊長(zhǎng)之和) ,即：,c(p)=,完成整個(gè)工程所需的最少時(shí)間,等于事件y的最早可發(fā)生時(shí)間ve(y)。,數(shù)據(jù)結(jié)構(gòu)圖,(2) 事件v的最遲可發(fā)生時(shí)間：定義在不影響整個(gè)工程進(jìn)度的前提下,事件v必

53、須發(fā)生的時(shí)間稱為v的最遲(event late)可發(fā)生時(shí)間,記作vl(v)。vl(v)應(yīng)等于ve(y)與v到y(tǒng)的最長(zhǎng)路徑長(zhǎng)度之差(y是匯點(diǎn)),即：,vl(v)=ve(y) -,(3) 關(guān)鍵活動(dòng):若活動(dòng)v滿足ve(v)+c(ai)=vl(w),則稱活動(dòng)ai為關(guān)鍵活動(dòng)。 對(duì)關(guān)鍵活動(dòng)來(lái)說(shuō),不存在富余時(shí)間。顯然,關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)。找出關(guān)鍵活動(dòng)的意義在于,可以適當(dāng)?shù)卦黾訉?duì)關(guān)鍵活動(dòng)的投資(人力、物力等),相應(yīng)地減少對(duì)非關(guān)鍵活動(dòng)的投資,從而減少關(guān)鍵活動(dòng)的持續(xù)時(shí)間,縮短整個(gè)工程的工期。,數(shù)據(jù)結(jié)構(gòu)圖,只要計(jì)算出各項(xiàng)點(diǎn)的ve(v)和vl(v)的值,根據(jù)9.3等式就能找出所有的關(guān)鍵活動(dòng)。為了便于計(jì)算,引入下面兩個(gè)遞推式,其中,x和y分別是源點(diǎn)和匯點(diǎn)。 ve(x)=0 ve(w)= wx 上式中的MAX對(duì)所有射入w的邊取最大值。 vl(y)=0 vl(v)= vy,數(shù)據(jù)結(jié)構(gòu)圖,求AOE網(wǎng)的關(guān)鍵活動(dòng)的步驟： (1) 對(duì)于源點(diǎn)x,置ve(x)=0； (2) 對(duì)AOE網(wǎng)進(jìn)行拓?fù)渑判?。如發(fā)現(xiàn)回路,工程無(wú)法進(jìn)行,則退出；否則繼續(xù)下一步。 (3) 按頂點(diǎn)的拓?fù)浯涡?反復(fù)用式9.4,依次求其余各項(xiàng)點(diǎn)v的ve(v)值。(實(shí)際上,步驟(2)和步驟(3)可以合在一起完成,即一邊對(duì)頂點(diǎn)進(jìn)行拓?fù)渑判?一邊求出各點(diǎn)的e(v)之值。