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

1、第六章 圖6.1 圖的概念圖(Graph)是一種結(jié)點(diǎn)之間為多對多關(guān)系的數(shù)據(jù)構(gòu)造。邏輯特征是：可以有恣意個開場結(jié)點(diǎn)和恣意個終端結(jié)點(diǎn)，其他各個結(jié)點(diǎn)可以有恣意個前趨和恣意個后繼。圖中的結(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無向圖無向圖(Undigraph)假設(shè)圖假設(shè)圖G中的每條邊都是沒中的每條邊都是沒有方向的，那么圖有方向的，那么圖G稱為無向圖。稱為無向圖。例 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無向圖中，頂點(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，同時稱邊是頂點(diǎn)x和頂點(diǎn)yv 相關(guān)聯(lián)的邊Incident； v無向圖中，假設(shè)x,y是無向圖中的一條邊，那么頂點(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的子圖。v有向完全圖n個頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)v無向完全圖n個頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2v途徑有向圖G=(V,E)中，假設(shè)存在一個頂點(diǎn)序列vp,vi1,vi2,vin,vq

4、，使得,均是圖中的邊，那么稱此序列是從頂點(diǎn)vp到vq一條途徑。v途徑長度該途徑上經(jīng)過邊的數(shù)目。v回路一條途徑第一個頂點(diǎn)和最后一個頂點(diǎn)一樣的 叫v簡單途徑序列中頂點(diǎn)不反復(fù)出現(xiàn)的途徑叫v簡單回路除了第一個頂點(diǎn)和最后一個頂點(diǎn)外，其他頂點(diǎn)不反復(fù)出現(xiàn)的回路叫v有根圖假設(shè)存在一個頂點(diǎn)v，從該頂點(diǎn)到其他各個頂點(diǎn)都有途徑，那么稱此圖為有根圖 v連通從頂點(diǎn)x到頂點(diǎn)y有一條途徑，那么說x和y是連通的v連通圖圖中恣意兩個頂點(diǎn)都是連通的叫連通圖v連通分量無向圖G的極大連通子圖稱為G的連通分量 v強(qiáng)連通圖假設(shè)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 圖的存儲構(gòu)造鄰接矩陣表示頂點(diǎn)之間鄰接關(guān)系的矩陣 設(shè)G=(V,E是具有n個頂點(diǎn)的圖，那么G的鄰接矩陣是一個n階方陣A，A中元素的值aij可以定義為： v特點(diǎn)：v無向圖的鄰接矩陣對稱；有n個頂點(diǎn)的無向圖需存儲空間為n 有向圖鄰接矩陣不一定對稱；有n個頂點(diǎn)的有向圖需存儲空間為nv無向圖中頂點(diǎn)Vi的度是鄰接矩陣A中第i行元素之和v有向圖中，v頂點(diǎn)Vi的出度是A中第i行元素之和v頂點(diǎn)Vi的入度是A中第i列元素之和v網(wǎng)的鄰接矩陣可定義為：可以得到鄰接矩陣存儲構(gòu)造C言語描畫如下：#define n 5/* 圖的頂點(diǎn)數(shù) */#define e 6

6、/* 圖的邊數(shù) */#define max 10000/* 設(shè)置一個極大數(shù)無窮大 */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)酱鎯?gòu)造 頂點(diǎn)采用順序方式進(jìn)展存儲，用n個單鏈表來存儲圖中的邊，第i個單鏈表是一切與第i個頂點(diǎn)相關(guān)聯(lián)的邊鏈接而成的，稱此單鏈表為第i個頂點(diǎn)的邊表，邊表中的每個結(jié)點(diǎn)稱

7、為邊表結(jié)點(diǎn)。在頂點(diǎn)的順序表中，每個元素添加一個指針域用來存放各個邊表的頭指針，稱此順序表為頂點(diǎn)表，而順序表中的每個元素稱為頂點(diǎn)表結(jié)點(diǎn)。頂點(diǎn)表和各頂點(diǎn)的邊表一同組成圖的鄰接表。 鄰接表存儲構(gòu)造C言語描畫如下：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無向圖中頂點(diǎn)Vi的度為第i個單鏈表中的結(jié)點(diǎn)數(shù)v有向圖中v頂點(diǎn)Vi的出度為第i個單鏈表中的結(jié)點(diǎn)個數(shù)v頂點(diǎn)Vi的入度為整個單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個數(shù)v逆鄰接表：有向圖中對每個結(jié)點(diǎn)建立以Vi終點(diǎn)的單鏈表邊集數(shù)組邊集數(shù)組(edgeset array)(edgeset array)是圖的一種順序存儲方式，利用一維數(shù)組是圖的一種順序存儲方式，利用一維數(shù)組來存儲圖中一切的邊，數(shù)組中的每個元素用來存儲圖中的一條邊，包來存儲圖中一切的邊，數(shù)組中的每個元素用來存儲圖中的一條邊，包括：始點(diǎn)、終點(diǎn)的序號及權(quán)值，該數(shù)組中所含元素的個數(shù)要大于等于括：始點(diǎn)、終點(diǎn)的序號及權(quán)值，該數(shù)組中所含元素的個數(shù)要大于

9、等于圖中邊的條數(shù)。圖中邊的條數(shù)。 邊集數(shù)組鄰接表法(Adjacency List)是圖的一種鏈?zhǔn)酱鎯?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)方法：對于給定的圖G，假設(shè)初始時一切頂點(diǎn)均未被訪問過，那么可從G中任選一頂點(diǎn)vi做為初始出發(fā)點(diǎn)，深度優(yōu)先搜索可定義為：訪問出發(fā)點(diǎn)vi，置訪問標(biāo)志為1，然后依次從vi的未被訪

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

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

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

13、一個元素，就依次訪問它的每一個未被訪問過的鄰接點(diǎn)，并令其進(jìn)隊(duì)。這樣當(dāng)隊(duì)列為空時，闡明一切與初始點(diǎn)有途徑相通的頂點(diǎ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存儲存儲 */ int i;edgenode *p;SETNULL(Q);printf(輸出

15、序號為輸出序號為%d的頂點(diǎn)的頂點(diǎn): %cn,k,adjlistk.vertex); /* 訪問出發(fā)點(diǎn)訪問出發(fā)點(diǎn)vk */visitedk=1; /* 標(biāo)志標(biāo)志vk曾經(jīng)訪問過曾經(jīng)訪問過 */ENQUEUE (Q,k); /* 頂點(diǎn)頂點(diǎn)vk的序號的序號k入隊(duì)入隊(duì) */while(!EMPTY(Q) /* 隊(duì)列非空執(zhí)行隊(duì)列非空執(zhí)行 */ i= DEQUEUE(Q);/* 隊(duì)頭元素頂點(diǎn)序號出隊(duì)隊(duì)頭元素頂點(diǎn)序號出隊(duì) */p=adjlisti;while (p!=NULL) if(!visitedp-adjvex) printf(輸出序號為輸出序號為%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)先生成樹與廣度優(yōu)先生成樹闡明一個圖可以有許多棵不同的生成樹一切生成樹具有以下共同特點(diǎn)：生成樹的頂點(diǎn)個數(shù)與圖的頂點(diǎn)個數(shù)一樣生成樹是圖的極小連通子圖一個有n個頂點(diǎn)的連通圖的生成樹有n-1條邊生成樹中恣意兩個頂點(diǎn)間的途徑是獨(dú)一的在生成樹中再加一條邊必然構(gòu)成回路含n個頂點(diǎn)n-1條邊的圖不一定是生成樹生成樹連通圖G的一個子圖假設(shè)是一棵包含G的一切頂點(diǎn)的樹，那么該子圖稱為G的生成樹(Spanning Tree) 。6.4最小生成樹問題提出要在n個城市間建立通訊聯(lián)絡(luò)網(wǎng)，

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

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

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

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

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

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

23、集合中，擴(kuò)展集合S。此時該點(diǎn)的間隔值就是最短途徑長。此時該點(diǎn)的間隔值就是最短途徑長度。度。然后，對集合然后，對集合V-S中剩余頂點(diǎn)的間隔值進(jìn)展修正。方法是中剩余頂點(diǎn)的間隔值進(jìn)展修正。方法是：假設(shè)：假設(shè)u是是V-S中的一個頂點(diǎn)，中的一個頂點(diǎn)，u點(diǎn)當(dāng)前的間隔值為點(diǎn)當(dāng)前的間隔值為len_u，而新參與，而新參與S的點(diǎn)的點(diǎn)m的最短途徑的最短途徑len_m加上邊加上邊 的的長度為長度為L，假設(shè)，假設(shè)Llen_u，那么，那么u點(diǎn)當(dāng)前的間隔值修正為點(diǎn)當(dāng)前的間隔值修正為：len_u=L。同時修正途徑，即在。同時修正途徑，即在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中。此時S= 1，2，V-S= 3，4，5。然后對V-S中各點(diǎn)的間隔值進(jìn)展修正，修正后各點(diǎn)的間隔值及途徑為： 3.再從V-S中選擇間隔值最小的頂點(diǎn)4，參與到S中。此時S= 1，2，4， V-S= 3，5。修正V-S中的點(diǎn)的間隔值為： 4. 繼續(xù)從V-S中選擇間隔值最小的頂點(diǎn)3，參與到S中。此時S= 1，2， 3，4，V-S= 5。修正V-S中的點(diǎn)的間隔值為：5.最后從V-S中選擇間隔值最小的頂點(diǎn)5，

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

26、排成一個線性序列，通常稱為拓?fù)湫蛄小?，通常稱為拓?fù)湫蛄小?拓?fù)湫蛄斜匦铦M足如下條件：對一個有向無拓?fù)湫蛄斜匦铦M足如下條件：對一個有向無環(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)表示活動，頂點(diǎn)之間的有向：用頂點(diǎn)表示活動，頂點(diǎn)之間的有向邊表示活動之間的先后關(guān)系，從而將實(shí)踐問邊表示活動之間的先后關(guān)系，從而將實(shí)踐問題轉(zhuǎn)化為一個有向圖，稱其為頂點(diǎn)活動網(wǎng)題轉(zhuǎn)化為一個有向圖，稱其為頂點(diǎn)活動網(wǎng)Activity On Vertex network，簡稱，簡稱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中選一個沒有前驅(qū)的頂點(diǎn)且輸出之從網(wǎng)中刪除該頂點(diǎn)及一切出邊反復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)網(wǎng)中不存在入度為0的頂點(diǎn)為止。一個AOV網(wǎng)的拓?fù)湫蛄胁皇仟?dú)一的AOV網(wǎng)求拓?fù)渑判虻倪^程 算法實(shí)現(xiàn)以鄰接表作存儲構(gòu)造每次都需求查找入度為0的頂點(diǎn)并刪除出邊，在鄰接表上刪除出邊很容易，而要查找入度為0的頂點(diǎn)需求遍歷一切的單鏈表，較費(fèi)事。為此，添加一個存放頂點(diǎn)入度的域id，先將每個頂點(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)算 在