數(shù)據(jù)結(jié)構(gòu)六章圖ppt課件

1、第六章 圖6.1 圖的概念圖(Graph)是一種結(jié)點(diǎn)之間為多對(duì)多關(guān)系的數(shù)據(jù)構(gòu)造。邏輯特征是：可以有恣意個(gè)開(kāi)場(chǎng)結(jié)點(diǎn)和恣意個(gè)終端結(jié)點(diǎn)，其他各個(gè)結(jié)點(diǎn)可以有恣意個(gè)前趨和恣意個(gè)后繼。圖中的結(jié)點(diǎn)常稱為頂點(diǎn)。圖的邏輯構(gòu)造可以用二元組表示： Graph(V,E) V是頂點(diǎn)(vertex)的集合； E是邊(edge)的集合。v有向圖有向圖(Digraph)假設(shè)圖假設(shè)圖G中的每條邊都是有中的每條邊都是有方向的，那么稱圖方向的，那么稱圖G為有向圖。為有向圖。例 G1 = (V1, E1)V1 = v1, v2, v3E1 = , , G2 = (V2, E2)V2 = v1, v2, v3E2 = , , , ,

2、, v無(wú)向圖無(wú)向圖(Undigraph)假設(shè)圖假設(shè)圖G中的每條邊都是沒(méi)中的每條邊都是沒(méi)有方向的，那么圖有方向的，那么圖G稱為無(wú)向圖。稱為無(wú)向圖。例 G3 = (V3, E3)V3= v1, v2, v3, v4E3= (v1, v2), (v1, v3), (v1, v4), (v2, v3), (v2, v4)G4 = (V4, E4)V4= v1, v2, v3 E4= (v1, v2), (v1, v3), (v2, v3) v頂點(diǎn)的度v有向圖中，頂點(diǎn)的度分成入度與出度v入度：該頂點(diǎn)入邊的數(shù)目v出度：該頂點(diǎn)出邊的數(shù)目v無(wú)向圖中，頂點(diǎn)的度為與該頂點(diǎn)相連的邊數(shù)v鄰接點(diǎn)與關(guān)聯(lián)邊v有向圖中，假設(shè)

3、是有向圖中的一條邊，那么頂點(diǎn)xv 和頂點(diǎn)y稱為鄰接點(diǎn)。稱x鄰接到y(tǒng)或y鄰v 接于x，同時(shí)稱邊是頂點(diǎn)x和頂點(diǎn)yv 相關(guān)聯(lián)的邊Incident； v無(wú)向圖中，假設(shè)x,y是無(wú)向圖中的一條邊，那么頂點(diǎn)v x和頂點(diǎn)y互為鄰接點(diǎn),并且稱邊(x, y)是v 頂點(diǎn) x和頂點(diǎn)y相關(guān)聯(lián)的邊。v子圖設(shè)有圖G=(V,E) ，假設(shè)滿足：vVVvEEvE中邊所鄰接的點(diǎn)均在V中出現(xiàn)v 那么 G= (V,E)也是一個(gè)圖，并且稱之為G的子圖。v有向完全圖n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)v無(wú)向完全圖n個(gè)頂點(diǎn)的無(wú)向圖最大邊數(shù)是n(n-1)/2v途徑有向圖G=(V,E)中，假設(shè)存在一個(gè)頂點(diǎn)序列vp,vi1,vi2,vin,vq

4、，使得,均是圖中的邊，那么稱此序列是從頂點(diǎn)vp到vq一條途徑。v途徑長(zhǎng)度該途徑上經(jīng)過(guò)邊的數(shù)目。v回路一條途徑第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)一樣的 叫v簡(jiǎn)單途徑序列中頂點(diǎn)不反復(fù)出現(xiàn)的途徑叫v簡(jiǎn)單回路除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其他頂點(diǎn)不反復(fù)出現(xiàn)的回路叫v有根圖假設(shè)存在一個(gè)頂點(diǎn)v，從該頂點(diǎn)到其他各個(gè)頂點(diǎn)都有途徑，那么稱此圖為有根圖 v連通從頂點(diǎn)x到頂點(diǎn)y有一條途徑，那么說(shuō)x和y是連通的v連通圖圖中恣意兩個(gè)頂點(diǎn)都是連通的叫連通圖v連通分量無(wú)向圖G的極大連通子圖稱為G的連通分量 v強(qiáng)連通圖假設(shè)G中恣意兩個(gè)頂點(diǎn)都是強(qiáng)連通的，那么稱圖G是強(qiáng)連通圖 v強(qiáng)連通分量 有向圖G的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量 v

5、權(quán)與圖的邊相關(guān)的數(shù)值叫權(quán)值。v網(wǎng)絡(luò)邊上帶權(quán)的圖稱為網(wǎng)絡(luò) 6.2 圖的存儲(chǔ)構(gòu)造鄰接矩陣表示頂點(diǎn)之間鄰接關(guān)系的矩陣 設(shè)G=(V,E是具有n個(gè)頂點(diǎn)的圖，那么G的鄰接矩陣是一個(gè)n階方陣A，A中元素的值aij可以定義為： v特點(diǎn)：v無(wú)向圖的鄰接矩陣對(duì)稱；有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n 有向圖鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為nv無(wú)向圖中頂點(diǎn)Vi的度是鄰接矩陣A中第i行元素之和v有向圖中，v頂點(diǎn)Vi的出度是A中第i行元素之和v頂點(diǎn)Vi的入度是A中第i列元素之和v網(wǎng)的鄰接矩陣可定義為：可以得到鄰接矩陣存儲(chǔ)構(gòu)造C言語(yǔ)描畫如下：#define n 5/* 圖的頂點(diǎn)數(shù) */#define e 6

6、/* 圖的邊數(shù) */#define max 10000/* 設(shè)置一個(gè)極大數(shù)無(wú)窮大 */typedef char vextype; /* 頂點(diǎn)類型 */typedef int adjtype;/* 權(quán)值類型 */typedef struct vextype vertexn+1;/* 頂點(diǎn)數(shù)組 */adjtype edgen+1n+1;/* 鄰接矩陣 */adj_matrix;鄰接表鄰接表法(Adjacency List)是圖的一種鏈?zhǔn)酱鎯?chǔ)構(gòu)造 頂點(diǎn)采用順序方式進(jìn)展存儲(chǔ)，用n個(gè)單鏈表來(lái)存儲(chǔ)圖中的邊，第i個(gè)單鏈表是一切與第i個(gè)頂點(diǎn)相關(guān)聯(lián)的邊鏈接而成的，稱此單鏈表為第i個(gè)頂點(diǎn)的邊表，邊表中的每個(gè)結(jié)點(diǎn)稱

7、為邊表結(jié)點(diǎn)。在頂點(diǎn)的順序表中，每個(gè)元素添加一個(gè)指針域用來(lái)存放各個(gè)邊表的頭指針，稱此順序表為頂點(diǎn)表，而順序表中的每個(gè)元素稱為頂點(diǎn)表結(jié)點(diǎn)。頂點(diǎn)表和各頂點(diǎn)的邊表一同組成圖的鄰接表。 鄰接表存儲(chǔ)構(gòu)造C言語(yǔ)描畫如下：typedef struct node int adjvex; /* 鄰接點(diǎn)域 */ struct node *next; /* 指針域 */edgenode; /* 定義邊表結(jié)點(diǎn) */typedef struct vextype vertex; /* 頂點(diǎn)域 */ edgenode *link; /* 指針域 */vexnode; /* 定義頂點(diǎn)表結(jié)點(diǎn) */vexnode adjlistn

8、+1;v特點(diǎn)v無(wú)向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)v有向圖中v頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)v頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)v逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi終點(diǎn)的單鏈表邊集數(shù)組邊集數(shù)組(edgeset array)(edgeset array)是圖的一種順序存儲(chǔ)方式，利用一維數(shù)組是圖的一種順序存儲(chǔ)方式，利用一維數(shù)組來(lái)存儲(chǔ)圖中一切的邊，數(shù)組中的每個(gè)元素用來(lái)存儲(chǔ)圖中的一條邊，包來(lái)存儲(chǔ)圖中一切的邊，數(shù)組中的每個(gè)元素用來(lái)存儲(chǔ)圖中的一條邊，包括：始點(diǎn)、終點(diǎn)的序號(hào)及權(quán)值，該數(shù)組中所含元素的個(gè)數(shù)要大于等于括：始點(diǎn)、終點(diǎn)的序號(hào)及權(quán)值，該數(shù)組中所含元素的個(gè)數(shù)要大于

9、等于圖中邊的條數(shù)。圖中邊的條數(shù)。 邊集數(shù)組鄰接表法(Adjacency List)是圖的一種鏈?zhǔn)酱鎯?chǔ)構(gòu)造 typedef struct edge int fromvex; /* 邊的始點(diǎn)域 */int endvex; /* 邊的終點(diǎn)域 */int weight; /* 邊的權(quán)值域 */edgeset; /* 定義邊集數(shù)組類型 */edgeset gee+1; /* 邊集數(shù)組全局量 */ 6.3 圖的遍歷深度優(yōu)先遍歷(DFS)方法：對(duì)于給定的圖G，假設(shè)初始時(shí)一切頂點(diǎn)均未被訪問(wèn)過(guò)，那么可從G中任選一頂點(diǎn)vi做為初始出發(fā)點(diǎn)，深度優(yōu)先搜索可定義為：訪問(wèn)出發(fā)點(diǎn)vi，置訪問(wèn)標(biāo)志為1，然后依次從vi的未被訪

10、問(wèn)過(guò)的鄰接點(diǎn)vj出發(fā)，繼續(xù)進(jìn)展深度優(yōu)先搜索，直至圖中一切和vi有途徑相通的頂點(diǎn)均被訪問(wèn)過(guò)。很顯然圖的深度優(yōu)先搜索過(guò)程是遞歸的。它的特點(diǎn)是盡能夠先對(duì)圖從縱深方向進(jìn)展搜索，故稱為深度優(yōu)先搜索。 DFS序列為：v1，v2，v4，v8，v5，v3，v6，v7。 v深度優(yōu)先遍歷算法v遞歸算法void DFS(int i) int j;printf (輸出序號(hào)為輸出序號(hào)為%d的頂點(diǎn)的頂點(diǎn): %cn,i,adj-vertexi); visitedi=1; /* 標(biāo)志標(biāo)志vi曾經(jīng)訪問(wèn)過(guò)曾經(jīng)訪問(wèn)過(guò) */for (j=1;jedgeij)&(!visitedj)DFS(j);void DFSL(int i) ed

11、genode *p; printf(輸出序號(hào)為%d的頂點(diǎn): %cn,i,adjlisti.vertex); visited i=1; /* 標(biāo)志vi曾經(jīng)訪問(wèn)過(guò) */ p=adjlisti; /* p為vi的邊表頭指針 */ while (p) /* 依次搜索vi的鄰接點(diǎn) */ if(!visitedp-adjvex) DFSL(p-adjvex); p=p-next; 在鄰接矩陣上實(shí)現(xiàn)遍歷的過(guò)程： 生成樹(shù)連通圖G的一個(gè)子圖假設(shè)是一棵包含G的一切頂點(diǎn)的樹(shù)，那么該子圖稱為G的生成樹(shù)(Spanning Tree) 。廣度優(yōu)先遍歷(BFS)方法：對(duì)于給定圖G，假設(shè)初始時(shí)的一切頂點(diǎn)均未被訪問(wèn)過(guò)，從圖G中

12、任選一頂點(diǎn)vi為初始出發(fā)點(diǎn)，廣度優(yōu)先搜索遍歷可定義為：首先訪問(wèn)出發(fā)點(diǎn)vi，接著依次訪問(wèn)vi的一切的鄰接的未被訪問(wèn)過(guò)的點(diǎn)w1， w2, wt，然后，再依次訪問(wèn)與w1，w2,wt相鄰接的未被訪問(wèn)過(guò)的頂點(diǎn)。依此類推，直至圖中一切和初始出發(fā)點(diǎn)vi有途徑相通的頂點(diǎn)都已訪問(wèn)到為止。顯然，此方法的特點(diǎn)是盡能夠先對(duì)橫向進(jìn)展搜索，故稱之為廣度優(yōu)先搜索。 BFS序列為：v1，v2，v3，v4，v5，v6，v7，v8 v廣度優(yōu)先遍歷算法 在廣度優(yōu)先遍歷中，先被訪問(wèn)的頂點(diǎn)，其鄰接點(diǎn)亦先被訪問(wèn)，所以在算法的實(shí)現(xiàn)中需求運(yùn)用一個(gè)隊(duì)列，用來(lái)依次記住被訪問(wèn)過(guò)的頂點(diǎn)。 算法開(kāi)場(chǎng)時(shí)，將初始點(diǎn)Vi訪問(wèn)后插入隊(duì)列中，以后每從隊(duì)列中刪除

13、一個(gè)元素，就依次訪問(wèn)它的每一個(gè)未被訪問(wèn)過(guò)的鄰接點(diǎn)，并令其進(jìn)隊(duì)。這樣當(dāng)隊(duì)列為空時(shí)，闡明一切與初始點(diǎn)有途徑相通的頂點(diǎn)都已訪問(wèn)終了，算法到此終了。例1423512341342adjvexnext 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍歷序列：10 1 2 3 4 54fr遍歷序列：1 40 1 2 3 4 54 3fr遍歷序列：1 4 3例1423512341342adjvexnext 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 54 3 2fr遍歷序列：1 4 3 20 1 2 3 4

14、5 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 2 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 fr遍歷序列：1 4 3 2 5例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 2鄰接表法廣度優(yōu)先：鄰接表法廣度優(yōu)先：void BFSL(int k) /* 用用adjlist存儲(chǔ)存儲(chǔ) */ int i;edgenode *p;SETNULL(Q);printf(輸出

15、序號(hào)為輸出序號(hào)為%d的頂點(diǎn)的頂點(diǎn): %cn,k,adjlistk.vertex); /* 訪問(wèn)出發(fā)點(diǎn)訪問(wèn)出發(fā)點(diǎn)vk */visitedk=1; /* 標(biāo)志標(biāo)志vk曾經(jīng)訪問(wèn)過(guò)曾經(jīng)訪問(wèn)過(guò) */ENQUEUE (Q,k); /* 頂點(diǎn)頂點(diǎn)vk的序號(hào)的序號(hào)k入隊(duì)入隊(duì) */while(!EMPTY(Q) /* 隊(duì)列非空?qǐng)?zhí)行隊(duì)列非空?qǐng)?zhí)行 */ i= DEQUEUE(Q);/* 隊(duì)頭元素頂點(diǎn)序號(hào)出隊(duì)隊(duì)頭元素頂點(diǎn)序號(hào)出隊(duì) */p=adjlisti;while (p!=NULL) if(!visitedp-adjvex) printf(輸出序號(hào)為輸出序號(hào)為%d的頂點(diǎn)的頂點(diǎn): %cn,p-adjvex,adjli

16、stp-adjvex.vertex);visitedp-adjvex =1;ENQUEUE(Q,p-adjvex);p=p-next;深度優(yōu)先生成樹(shù)與廣度優(yōu)先生成樹(shù)闡明一個(gè)圖可以有許多棵不同的生成樹(shù)一切生成樹(shù)具有以下共同特點(diǎn)：生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)一樣生成樹(shù)是圖的極小連通子圖一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有n-1條邊生成樹(shù)中恣意兩個(gè)頂點(diǎn)間的途徑是獨(dú)一的在生成樹(shù)中再加一條邊必然構(gòu)成回路含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹(shù)生成樹(shù)連通圖G的一個(gè)子圖假設(shè)是一棵包含G的一切頂點(diǎn)的樹(shù)，那么該子圖稱為G的生成樹(shù)(Spanning Tree) 。6.4最小生成樹(shù)問(wèn)題提出要在n個(gè)城市間建立通訊聯(lián)絡(luò)網(wǎng)，

17、頂點(diǎn)表示城市權(quán)城市間建立通訊線路所需破費(fèi)代價(jià)希望找到一棵生成樹(shù)，它的每條邊上的權(quán)值之和即建立該通訊網(wǎng)所需破費(fèi)的總代價(jià)最小最小代價(jià)生成樹(shù)v問(wèn)題分析1654327131791812752410n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路n個(gè)城市間建立通訊網(wǎng)，只需n-1條線路問(wèn)題轉(zhuǎn)化為：如何在能夠的線路中選擇n-1條，能把 一切城市頂點(diǎn)均連起來(lái)，且總耗費(fèi) 各邊權(quán)值之和最小v定義：連通網(wǎng)絡(luò)的一切生成樹(shù)中邊上權(quán)值之和最小的生成樹(shù)稱為最小生成樹(shù)Minimun Spanning Tree) MST性質(zhì)：性質(zhì)： 假設(shè)假設(shè)G=(V, E)是一個(gè)連通網(wǎng)絡(luò)，是一個(gè)連通網(wǎng)絡(luò)，U為頂點(diǎn)集為頂點(diǎn)集V的一個(gè)非空子集。假設(shè)邊

18、的一個(gè)非空子集。假設(shè)邊(u,v)是一切的一個(gè)是一切的一個(gè)端點(diǎn)在端點(diǎn)在U中即中即uU，另一個(gè)端點(diǎn)不在，另一個(gè)端點(diǎn)不在U中即中即vV-U的這些邊里面，權(quán)值最小的的這些邊里面，權(quán)值最小的一條，那么一定存在一棵一條，那么一定存在一棵G的最小生成樹(shù)包的最小生成樹(shù)包括此邊括此邊(u,v)。 v構(gòu)造最小生成樹(shù)方法v方法一：普里姆(Prim)算法v算法思想：設(shè)G=(V, E)是連通網(wǎng)，T=U，TE是G的最小生成樹(shù)，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空集。v初始令U=u0,(u0V), TE=v在一切uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)v將(u0,v0)并入集合

19、TE，同時(shí)v0并入U(xiǎn)v反復(fù)上述操作直至U=V為止，那么T=(V,TE)為G的最小生成樹(shù)用Prim算法構(gòu)造最小生成樹(shù)的過(guò)程 生成樹(shù)T的邊集數(shù)組數(shù)組變化過(guò)程l方法二：克魯斯卡爾(Kruskal)算法l算法思想：設(shè)連通網(wǎng)G=(V,E)，令最小生成樹(shù)T=(U,TE)l初始形狀U=V,TE=l將圖G中的邊按權(quán)值從小到大的順序依次選取，假設(shè)選取的邊使生成樹(shù)T不構(gòu)成回路，那么把它并入TE中，保管作為T的一條邊；假設(shè)選取的邊使生成樹(shù)T構(gòu)成回路，那么將其舍棄。l依此類推，直至TE中包含n-1條邊為止，此時(shí)的T 即為最小生成樹(shù)。用Kruskal算法構(gòu)造最小生成樹(shù)的過(guò)程 7.5 拓?fù)渑判騿?wèn)題提出：學(xué)生選修課程問(wèn)題頂

20、點(diǎn)表示課程有向邊表示先決條件，假設(shè)課程i是課程j的先決條件，那么圖中有邊學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才干無(wú)矛盾、順利地完成學(xué)業(yè)拓?fù)渑判蚨xAOV網(wǎng)用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)的先后關(guān)系的有向圖稱為頂點(diǎn)活動(dòng)網(wǎng)(Activity On Vertex network)，簡(jiǎn)稱AOV網(wǎng)假設(shè)是圖中有向邊，那么vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路65 最短路經(jīng)最短路經(jīng)最短途徑問(wèn)題通常是指如何從圖中某一頂點(diǎn)最短途徑問(wèn)題通常是指如何從圖中某一頂點(diǎn)(稱為源點(diǎn)稱為源點(diǎn))到達(dá)另一頂點(diǎn)到達(dá)另一頂點(diǎn)(稱為終點(diǎn)稱為終點(diǎn))的多條途的多條途徑中，找到一條途徑，使得此途徑上經(jīng)過(guò)的徑中，找到一條

21、途徑，使得此途徑上經(jīng)過(guò)的各邊上的權(quán)值總和到達(dá)最小。各邊上的權(quán)值總和到達(dá)最小。最短途徑問(wèn)題通?？梢苑殖伤姆N不同情況最短途徑問(wèn)題通常可以分成四種不同情況: 單源點(diǎn)、單目的點(diǎn)最短途徑問(wèn)題；單源點(diǎn)、單目的點(diǎn)最短途徑問(wèn)題；單源點(diǎn)、多目的點(diǎn)最短途徑問(wèn)題；單源點(diǎn)、多目的點(diǎn)最短途徑問(wèn)題；多源點(diǎn)、單目的點(diǎn)最短途徑問(wèn)題；多源點(diǎn)、單目的點(diǎn)最短途徑問(wèn)題；多源點(diǎn)、多目的點(diǎn)最短途徑問(wèn)題。多源點(diǎn)、多目的點(diǎn)最短途徑問(wèn)題。我們討論最常見(jiàn)的兩種情況：?jiǎn)卧袋c(diǎn)最短途我們討論最常見(jiàn)的兩種情況：?jiǎn)卧袋c(diǎn)最短途徑和恣意兩點(diǎn)間的最短途徑。徑和恣意兩點(diǎn)間的最短途徑。 單源最短路經(jīng) 從源點(diǎn)1到其他各頂點(diǎn)的最短途徑 迪杰斯特拉迪杰斯特拉Dijkst

22、ra算法：算法： 初始化：集合初始化：集合S中只需一個(gè)源點(diǎn)，其他頂點(diǎn)都在集合中只需一個(gè)源點(diǎn)，其他頂點(diǎn)都在集合V-S中。此時(shí)中。此時(shí)S中源點(diǎn)的間隔值最短途徑為中源點(diǎn)的間隔值最短途徑為0；V-S中各中各個(gè)頂點(diǎn)的間隔值為：只經(jīng)過(guò)源點(diǎn)到達(dá)該頂點(diǎn)的當(dāng)時(shí)最短個(gè)頂點(diǎn)的間隔值為：只經(jīng)過(guò)源點(diǎn)到達(dá)該頂點(diǎn)的當(dāng)時(shí)最短途徑，即從源點(diǎn)到達(dá)該頂點(diǎn)的邊長(zhǎng)無(wú)邊時(shí)，間隔值為途徑，即從源點(diǎn)到達(dá)該頂點(diǎn)的邊長(zhǎng)無(wú)邊時(shí)，間隔值為。當(dāng)某點(diǎn)的間隔值不等于。當(dāng)某點(diǎn)的間隔值不等于時(shí)，可以得到該點(diǎn)的途徑時(shí)，可以得到該點(diǎn)的途徑一條邊。一條邊。首先，從首先，從V-S中選擇一個(gè)間隔值最小的頂點(diǎn)中選擇一個(gè)間隔值最小的頂點(diǎn)v，將其參與，將其參與到到S中，擴(kuò)展

23、集合中，擴(kuò)展集合S。此時(shí)該點(diǎn)的間隔值就是最短途徑長(zhǎng)。此時(shí)該點(diǎn)的間隔值就是最短途徑長(zhǎng)度。度。然后，對(duì)集合然后，對(duì)集合V-S中剩余頂點(diǎn)的間隔值進(jìn)展修正。方法是中剩余頂點(diǎn)的間隔值進(jìn)展修正。方法是：假設(shè)：假設(shè)u是是V-S中的一個(gè)頂點(diǎn)，中的一個(gè)頂點(diǎn)，u點(diǎn)當(dāng)前的間隔值為點(diǎn)當(dāng)前的間隔值為len_u，而新參與，而新參與S的點(diǎn)的點(diǎn)m的最短途徑的最短途徑len_m加上邊加上邊 的的長(zhǎng)度為長(zhǎng)度為L(zhǎng)，假設(shè)，假設(shè)Llen_u，那么，那么u點(diǎn)當(dāng)前的間隔值修正為點(diǎn)當(dāng)前的間隔值修正為：len_u=L。同時(shí)修正途徑，即在。同時(shí)修正途徑，即在m點(diǎn)的途徑后面加上點(diǎn)的途徑后面加上u點(diǎn)即可。點(diǎn)即可。最后，反復(fù)最后，反復(fù)2、3步，直到一

24、切頂點(diǎn)全部進(jìn)入集步，直到一切頂點(diǎn)全部進(jìn)入集合合S，即，即V=S為止。為止。 1. 初始化：S= 1，V-S= 2，3，4，5。各點(diǎn)的間隔值及途徑為： 2. 從V-S中選擇間隔值最小的頂點(diǎn)2，參與到S中。此時(shí)S= 1，2，V-S= 3，4，5。然后對(duì)V-S中各點(diǎn)的間隔值進(jìn)展修正，修正后各點(diǎn)的間隔值及途徑為： 3.再?gòu)腣-S中選擇間隔值最小的頂點(diǎn)4，參與到S中。此時(shí)S= 1，2，4， V-S= 3，5。修正V-S中的點(diǎn)的間隔值為： 4. 繼續(xù)從V-S中選擇間隔值最小的頂點(diǎn)3，參與到S中。此時(shí)S= 1，2， 3，4，V-S= 5。修正V-S中的點(diǎn)的間隔值為：5.最后從V-S中選擇間隔值最小的頂點(diǎn)5，

25、參與到S中。此時(shí)S= 1，2， 3，4，5，V-S= ，算法終了。存前點(diǎn)方式存儲(chǔ)構(gòu)造 存儲(chǔ)構(gòu)造C言語(yǔ)描畫：typedef struct int prenode; int pathlength;shortestpath;int flagn+1;shortestpath spn+1; 恣意兩點(diǎn)間最短路經(jīng) Floyd算法的實(shí)現(xiàn)是經(jīng)過(guò)矩陣迭代來(lái)完成的。有向圖及其鄰接矩陣 66 拓?fù)渑判蛲負(fù)渑判?拓?fù)渑判蚴怯邢驘o(wú)環(huán)圖拓?fù)渑判蚴怯邢驘o(wú)環(huán)圖directed acycline graph上的重要運(yùn)算。拓?fù)渑判虻哪康氖菍⑸系闹匾\(yùn)算。拓?fù)渑判虻哪康氖菍⒂邢驘o(wú)環(huán)圖中一切的頂點(diǎn)排成一個(gè)線性序列有向無(wú)環(huán)圖中一切的頂點(diǎn)

26、排成一個(gè)線性序列，通常稱為拓?fù)湫蛄?。，通常稱為拓?fù)湫蛄小?拓?fù)湫蛄斜匦铦M足如下條件：對(duì)一個(gè)有向無(wú)拓?fù)湫蛄斜匦铦M足如下條件：對(duì)一個(gè)有向無(wú)環(huán)圖環(huán)圖G=V，E，假設(shè)頂點(diǎn)，假設(shè)頂點(diǎn)u，vV，且，且u到到v有途徑，那么在此線性序列中，頂點(diǎn)有途徑，那么在此線性序列中，頂點(diǎn)u必必陳列在頂點(diǎn)陳列在頂點(diǎn)v之前。之前。 AOV網(wǎng)網(wǎng) ：用頂點(diǎn)表示活動(dòng)，頂點(diǎn)之間的有向：用頂點(diǎn)表示活動(dòng)，頂點(diǎn)之間的有向邊表示活動(dòng)之間的先后關(guān)系，從而將實(shí)踐問(wèn)邊表示活動(dòng)之間的先后關(guān)系，從而將實(shí)踐問(wèn)題轉(zhuǎn)化為一個(gè)有向圖，稱其為頂點(diǎn)活動(dòng)網(wǎng)題轉(zhuǎn)化為一個(gè)有向圖，稱其為頂點(diǎn)活動(dòng)網(wǎng)Activity On Vertex network，簡(jiǎn)稱，簡(jiǎn)稱AOV網(wǎng)網(wǎng)

27、。 可以得到拓?fù)湫蛄校篊1，C3，C3，C4，C5，C6，C7，C8，C9，C10和C2，C6，C1，C5，C7，C10，C4，C3，C8，C9 拓?fù)渑判虻姆椒ㄔ谟邢驁D中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之從網(wǎng)中刪除該頂點(diǎn)及一切出邊反復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)網(wǎng)中不存在入度為0的頂點(diǎn)為止。一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇仟?dú)一的AOV網(wǎng)求拓?fù)渑判虻倪^(guò)程 算法實(shí)現(xiàn)以鄰接表作存儲(chǔ)構(gòu)造每次都需求查找入度為0的頂點(diǎn)并刪除出邊，在鄰接表上刪除出邊很容易，而要查找入度為0的頂點(diǎn)需求遍歷一切的單鏈表，較費(fèi)事。為此，添加一個(gè)存放頂點(diǎn)入度的域id，先將每個(gè)頂點(diǎn)的入度求出后依次存放在該域中。反復(fù)上述操作直至棧空為止,拓?fù)渑判蚪K了。67 關(guān)鍵途徑關(guān)鍵途徑 關(guān)鍵途徑那么是關(guān)鍵途徑那么是AOE網(wǎng)網(wǎng)Activity On Edge network上的典型運(yùn)算上的典型運(yùn)算 在