數(shù)據(jù)結(jié)構(gòu)-圖.ppt

1、圖是復(fù)雜的非線性結(jié)構(gòu) 頂點(diǎn)的前趨和后繼個(gè)數(shù)不加限制，頂點(diǎn)間關(guān)系是任意的，任意兩個(gè)頂點(diǎn)間可能相關(guān)。 應(yīng)用廣泛,2.6 圖,定義：圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph( V, E ) 其中: V= x | x 某個(gè)數(shù)據(jù)對(duì)象是頂點(diǎn)的非空有窮集合； E1 = (x, y) | x, y V 或E2 = | x, y V E1是頂點(diǎn)間關(guān)系的有窮集合，也叫做邊(edge)集合，此時(shí)的圖稱為無向圖。 E2表示從 x 到 y 的一條弧，且稱x為弧尾，y為弧頭，這樣的圖稱為有向圖。,2.6.1 圖的定義及基本術(shù)語,不考慮頂點(diǎn)到自身的邊或弧。,有向圖與無向圖 在有向圖中

2、， 是有序頂點(diǎn)對(duì)；在無向圖中， (x, y)是無序頂點(diǎn)對(duì)。 完全圖 若有 n 個(gè)頂點(diǎn)的無向圖有 n(n-1)/2 條邊, 則此圖為無向完全圖。有 n 個(gè)頂點(diǎn)的有向圖有n(n-1) 條邊, 則此圖為有向完全圖。,0,0,0,0,1,1,1,1,2,2,2,2,6,5,4,3,3,2.6.1 圖的定義及基本術(shù)語,完全圖有最多的邊數(shù)、弧數(shù)。,鄰接頂點(diǎn) 如果 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點(diǎn)。 子圖 設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。若 V V 且 EE, 則稱 圖G 是 圖G 的子圖。 權(quán) 某些圖的邊具有與它相關(guān)的數(shù), 稱之為權(quán)。這種帶權(quán)圖叫做網(wǎng)絡(luò)

3、。,2.6.1 圖的定義及基本術(shù)語,頂點(diǎn)的度 一個(gè)頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中, 頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和： TD(v) =ID(v)+OD(v)。 頂點(diǎn) v 的入度 是以 v 為終點(diǎn)的有向邊的條數(shù), 記作 ID(v); 頂點(diǎn) v 的出度是以 v 為始點(diǎn)的有向邊的條數(shù), 記作 OD(v)。 路徑 在圖 G=(V, E) 中, 若從頂點(diǎn) vi 出發(fā), 沿一些邊經(jīng)過一些頂點(diǎn) vp1, vp2, , vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列 (vi vp1 vp2 . vpm vj) 為從頂點(diǎn)vi 到頂點(diǎn) vj 的路徑。它經(jīng)過的邊(vi, vp1)、(vp1, v

4、p2)、.、(vpm, vj) 應(yīng)是屬于E的邊。,2.6.1 圖的定義及基本術(shù)語,頂點(diǎn)的出度: 以頂點(diǎn)v 為弧尾的弧的數(shù)目; 頂點(diǎn)的入度: 以頂點(diǎn)v為弧頭的弧的數(shù)目。,有向圖,頂點(diǎn)的度(TD)=出度(OD)+入度(ID) TD(B) =OD(B)+ID(B) = 3,例如:,路徑長度 非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。 簡單路徑 若路徑上各頂點(diǎn) v1,v2,.,vm 均不互相重復(fù), 則稱這樣的路徑為簡單路徑。 簡單回路 若路徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂點(diǎn)vm 重合, 則稱這樣的路徑為回路或環(huán)。,0,1,2,3,0,1,2,3,0,1,2,3,

5、2.6.1 圖的定義及基本術(shù)語,如:從A到F長度為 3 的路徑A,B,C,F,連通圖與連通分量 在無向圖中, 若從頂點(diǎn)vi到頂點(diǎn)vj有路徑, 則稱頂點(diǎn)vi與vj是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱此圖是連通圖。 非連通圖的極大連通子圖叫做連通分量。 強(qiáng)連通圖與強(qiáng)連通分量 在有向圖中, 若對(duì)于每一對(duì)頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的路徑, 則稱此圖是強(qiáng)連通圖。 非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。,2.6.1 圖的定義及基本術(shù)語,連通圖的連通分量是自身。,強(qiáng)連通圖的強(qiáng)連通分量是自身。,無向圖,若圖中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖,若無向圖為

6、非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的連通分量。,有向圖,若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。否則，其各個(gè)強(qiáng)連通子圖稱作它的強(qiáng)連通分量。,A,B,E,C,F,2.6.1 圖的定義及基本術(shù)語,2.6.2 圖的存儲(chǔ)結(jié)構(gòu),在圖的鄰接矩陣表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表(一維數(shù)組)，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣(二維數(shù)組)。 設(shè)圖 A = (V, E)是一個(gè)有 n 個(gè)頂點(diǎn)的圖, 圖的鄰接矩陣是一個(gè)二維數(shù)組 A.edgenn，定義：,鄰接矩陣 (Adjacency Matrix),圖的結(jié)構(gòu)比較復(fù)雜，無法以數(shù)據(jù)元素在存儲(chǔ)區(qū)的物理位置來表示元素間的關(guān)系，所以無法

7、用順序存儲(chǔ)結(jié)構(gòu)。,無向圖的鄰接矩陣是對(duì)稱的(壓縮存儲(chǔ)); 有向圖的鄰接矩陣可能是不對(duì)稱的。,0,1,2,3,0,1,2,在有向圖中, 統(tǒng)計(jì)第 i 行 1 的個(gè)數(shù)可得頂點(diǎn) i 的出度，統(tǒng)計(jì)第 j 列 1 的個(gè)數(shù)可得頂點(diǎn) j 的入度。 在無向圖中, 統(tǒng)計(jì)第 i 行 (列) 1 的個(gè)數(shù)可得頂點(diǎn)i 的度。,2.6.2 圖的存儲(chǔ)結(jié)構(gòu),網(wǎng)絡(luò)的鄰接矩陣,2.6.2 圖的存儲(chǔ)結(jié)構(gòu),const int NumEdges = 50; /邊條數(shù) const int NumVertices = 10; /頂點(diǎn)個(gè)數(shù) typedef char VertexData; /頂點(diǎn)數(shù)據(jù)類型 typedef int EdgeDat

8、a; /邊上權(quán)值類型 typedef struct VertexData vexListNumVertices; /頂點(diǎn)表 EdgeData EdgeNumVerticesNumVertices; /鄰接矩陣, 可視為邊之間的關(guān)系 int n, e; /圖中當(dāng)前的頂點(diǎn)個(gè)數(shù)與邊數(shù) MTGraph;,用鄰接矩陣表示的結(jié)構(gòu)定義,2.6.2 圖的存儲(chǔ)結(jié)構(gòu),鄰接表 (Adjacency List)：圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。,(邊表)邊/弧結(jié)點(diǎn)結(jié)構(gòu) adjvex; /鄰接域， 與頂點(diǎn)vi鄰接的邊/弧所指向的頂點(diǎn)的位置 nextarc;/ 鏈域，指向下一條邊/弧指針 info; / 數(shù)據(jù)域，該邊/弧相關(guān)權(quán)值信

9、息,adjvex info nextarc,(頂點(diǎn)表)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu),data firstarc,data; / 頂點(diǎn)信息 firstarc; /指向第一條依附該頂點(diǎn)的邊/弧,2.6.2 圖的存儲(chǔ)結(jié)構(gòu),無向圖的鄰接表,同一個(gè)頂點(diǎn)Vi發(fā)出的邊鏈接在同一個(gè)邊表中，每一個(gè)邊結(jié)點(diǎn)代表一條邊, 結(jié)點(diǎn)中有與Vi鄰接頂點(diǎn)的下標(biāo)和指針。,A,B,C,D,data first,A B C D,0 1 2 3,adj next,1,3,0,2,1,0,2.6.2 圖的存儲(chǔ)結(jié)構(gòu),adj next,邊表,頂點(diǎn)表,有向圖的鄰接表和逆鄰接表,A,B,C,A B C,0 1 2,鄰接表 (出邊表),A B C,0 1 2,

10、逆鄰接表 (入邊表),1,0,2,0,1,1,2.6.2 圖的存儲(chǔ)結(jié)構(gòu),data first,adj next,adj next,data first,adj next,B,A,C,D,6,9,5,2,8,A B C D,0 1 2 3,1 5,3 6,2 8,3 2,1 9,(出邊表),(頂點(diǎn)表),2.6.2 圖的存儲(chǔ)結(jié)構(gòu),網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表,data first,adj info next,帶權(quán)圖的邊結(jié)點(diǎn)中保存該邊上的權(quán)值info。 頂點(diǎn) i 的邊表的表頭指針adj 在頂點(diǎn)表的下標(biāo)為 i 的頂點(diǎn)記錄中，該記錄還保存了該頂點(diǎn)的data信息。 在鄰接表的邊鏈表中，各個(gè)邊結(jié)點(diǎn)的鏈入順序任意，

11、視邊結(jié)點(diǎn)輸入次序而定。 設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則用鄰接表表示無向圖時(shí)，需要 n 個(gè)頂點(diǎn)結(jié)點(diǎn)，2e 個(gè)邊結(jié)點(diǎn)；用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需 n 個(gè)頂點(diǎn)結(jié)點(diǎn)，e 個(gè)邊結(jié)點(diǎn)。,2.6.2 圖的存儲(chǔ)結(jié)構(gòu),鄰接矩陣是唯一的，但鄰接表不唯一。,typedef char VertexData; /頂點(diǎn)數(shù)據(jù)類型 typedef int EdgeData; /邊上權(quán)值類型 typedef struct node /邊結(jié)點(diǎn) int dest; /目標(biāo)頂點(diǎn)下標(biāo) EdgeData cost; /邊上的權(quán)值 Struct node * link; /下一邊鏈接指針 EdgeNode;,鄰接表表

12、示的圖的定義(為算法),2.6.2 圖的存儲(chǔ)結(jié)構(gòu),typedef struct /頂點(diǎn)結(jié)點(diǎn) VertexData data; /頂點(diǎn)數(shù)據(jù)域 EdgeNode * firstAdj; /邊鏈表頭指針 VertexNode; typedef struct /圖的鄰接表 VertexNode VexList NumVertices; /鄰接表 int n, e; /圖中當(dāng)前的頂點(diǎn)個(gè)數(shù)與邊數(shù) AdjGraph;,2.6.2 圖的存儲(chǔ)結(jié)構(gòu),void CreateGraph (AdjGraph G) cin G.n G.e; /輸入頂點(diǎn)個(gè)數(shù)和邊數(shù) for ( int i = 0; i G.VexListi

13、.data; /輸入頂點(diǎn)信息 G.VexListi.firstAdj = NULL; for ( i = 0; i tail head weight; / tail和head是下標(biāo) EdgeNode * p = new EdgeNode; p-dest = head; p-cost = weight;,鄰接表的構(gòu)造算法(無向圖),2.6.2 圖的存儲(chǔ)結(jié)構(gòu),/鏈入第 tail 號(hào)鏈表的前端 p-link = G.VexListtail.firstAdj; G.VexListtail.firstAdj = p; p = new EdgeNode; p-dest = tail; p-cost = w

14、eight; /鏈入第 head 號(hào)鏈表的前端 p-link = G.VexListhead.firstAdj; G.VexListhead.firstAdj = p; ,2.6.3 圖的遍歷,從圖中某一頂點(diǎn)出發(fā)訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，這一過程就叫做圖的遍歷 (Traversing Graph)。 圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。 為了避免重復(fù)訪問，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組 visited 。,輔助數(shù)組 visited 的初始狀態(tài)為 0, 在圖的遍歷過程中, 一旦某一個(gè)頂點(diǎn)

15、 i 被訪問, 就立即讓 visited i為 1, 防止它被多次訪問。 兩種圖的遍歷方法: 深度優(yōu)先搜索 DFS (Depth First Search) 廣度優(yōu)先搜索 BFS (Breadth First Search),2.6.3 圖的遍歷,深度優(yōu)先搜索DFS ( Depth First Search ),深度優(yōu)先搜索過程,6,7,前進(jìn) 回退,深度優(yōu)先生成樹,2.6.3 圖的遍歷,DFS 在訪問圖中某一起始頂點(diǎn) v 后, 由 v 出發(fā), 訪問它的任一鄰接頂點(diǎn) w1; 再從 w1 出發(fā),訪問與 w1鄰接但還沒有訪問過的頂點(diǎn) w2; 然后再從 w2 出發(fā), 進(jìn)行類似訪問, 如此, 直至到達(dá)所

16、有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。 接著, 退回一步, 退到前一次剛訪問過的頂點(diǎn), 看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有, 則訪問此頂點(diǎn), 之后再從此頂點(diǎn)出發(fā), 進(jìn)行與前述類似的訪問(遞歸); 如果沒有, 就再退回一步進(jìn)行搜索。 重復(fù)上述過程, 直到連通圖中所有頂點(diǎn)都被訪問過為止。,2.6.3 圖的遍歷,void Graph_Traverse (AdjGraph G) int * visited = new int NumVertices; for ( int i = 0; i G.n; i+ ) visited i = 0; /訪問數(shù)組 visited 初始化 for ( int

17、 i = 0; i G.n; i+ ) if ( ! visitedi ) DFS (G, i, visited ); /從頂點(diǎn) i 出發(fā)開始搜索 delete visited ; /釋放 visited ,圖的深度優(yōu)先搜索算法,2.6.3 圖的遍歷,DFS被調(diào)用幾次就有幾個(gè)連通分量。,void DFS (AdjGraph G, int v, int visited ) cout GetValue (G, v) ; /訪問頂點(diǎn) v visitedv = 1; /頂點(diǎn) v 作訪問標(biāo)記 int w = GetFirstNeighbor (G, v); /取 v 的第一個(gè)鄰接頂點(diǎn) w while (

18、 w != -1 ) /若鄰接頂點(diǎn) w 存在 if ( !visitedw ) DFS (G, w, visited ); /若頂點(diǎn) w 未訪問過, 遞歸訪問頂點(diǎn) w w = GetNextNeighbor (G, v, w ); /取頂點(diǎn) v 排在 w 后的下一個(gè)鄰接頂點(diǎn) ,2.6.3 圖的遍歷,廣度優(yōu)先搜索BFS ( Breadth First Search ),廣度優(yōu)先搜索過程,A,C,D,E,G,B,F,I,H,A,C,D,E,G,B,F,H,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,廣度優(yōu)先生成樹,I,2.6.3 圖的遍歷,BFS在訪問了起始頂點(diǎn) v 之

19、后, 由 v 出發(fā), 依次訪問 v 的各個(gè)未被訪問過的鄰接頂點(diǎn) w1, w2, , wt, 然后再順序訪問 w1, w2, , wt 的所有還未被訪問過的鄰接頂點(diǎn)。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點(diǎn)， 如此做下去，直到圖中所有頂點(diǎn)都被訪問到為止。 廣度優(yōu)先搜索是一種分層的搜索過程, 每向前走一步可能訪問一批頂點(diǎn), 不像深度優(yōu)先搜索那樣有往回退的情況。因此, 廣度優(yōu)先搜索不是一個(gè)遞歸的過程。,2.6.3 圖的遍歷,為了實(shí)現(xiàn)逐層訪問, 算法中使用了一個(gè)隊(duì)列,以記憶正在訪問的這一層和下一層的頂點(diǎn),以便于向下一層訪問。 為避免重復(fù)訪問, 需要一個(gè)輔助數(shù)組 visited

20、，給被訪問過的頂點(diǎn)加標(biāo)記。,2.6.3 圖的遍歷,void Graph_Traverse (AdjGraph G) for ( int i = 0; i G.n; i+ ) if ( ! visitedi ) BFS (G, i, visited ); ,圖的廣度優(yōu)先搜索算法,2.6.3 圖的遍歷,void BFS (AdjGraph G, int v, int visited ) cout GetValue (v) ; visitedv = 1; Queue q; InitQueue(,2.6.3 圖的遍歷,visitedw = 1; EnQueue ( ,DFS和BFS的空間復(fù)雜度：O(n

21、) 輔助空間(棧和隊(duì)列)，每個(gè)頂點(diǎn)最多進(jìn)一次?；蜿?duì)。 DFS和BFS的時(shí)間復(fù)雜度： 鄰接表存儲(chǔ)：O(e)；鄰接矩陣存儲(chǔ)：O(n2) 一個(gè)圖的訪問序列不是唯一的，它與算法、圖的存儲(chǔ)結(jié)構(gòu)以及初始出發(fā)點(diǎn)有關(guān)。 因?yàn)猷徑泳仃嚤硎疚ㄒ唬訢FS序列唯一。 鄰接表表示不唯一，所以DFS序列不唯一,2.6.3 圖的遍歷,當(dāng)無向圖為非連通圖時(shí), 從圖中某一頂點(diǎn)出發(fā), 利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn), 只能訪問到該頂點(diǎn)所在的最大連通子圖(連通分量)的所有頂點(diǎn)。 對(duì)圖的每一個(gè)頂點(diǎn)進(jìn)行檢測(cè)：若已被訪問過，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點(diǎn)出發(fā)遍歷圖

22、，可求得圖的另一個(gè)連通分量。,非連通圖的遍歷,2.6.3 圖的遍歷,A,C,D,E,I,B,F,O,G,H,J,N,M,L,K,非連通無向圖的三個(gè)連通分量,應(yīng)用問題：設(shè)用有向網(wǎng)中頂點(diǎn)表示城市，弧表示城市間的交通路線，弧上的權(quán)表示兩點(diǎn)之間的交通路線長度，要求求出從某個(gè)城市出發(fā)到其余各個(gè)城市之間的最短路徑。 最短路徑問題：如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不只一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。 迪杰斯特拉(Dijkstra)提出按路徑長度遞增的次序產(chǎn)生從源點(diǎn)到其余各頂點(diǎn)的最短路徑的算法。,2.6.4 圖的應(yīng)用,最短路徑 (Shortest

23、Path),引入輔助數(shù)組dist。每個(gè)分量disti表示當(dāng)前找到的從源點(diǎn) v0到終點(diǎn) vi 的最短路徑的長度。初始狀態(tài)： 若從源點(diǎn)v0到頂點(diǎn)vi有邊, 則disti為該邊上的權(quán)值； 若從源點(diǎn)v0到頂點(diǎn)vi無邊, 則disti為 。 假設(shè) S 是已求得的最短路徑的終點(diǎn)的集合，可證明： 下一條最短路徑必然是從v0 出發(fā)，中間只經(jīng)過 S 中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn)vx (vxV-S )的路徑中的一條。 每次求得一條最短路徑后, 其終點(diǎn)vk 加入集合S，然后對(duì)所有的viV-S，修改其 disti值。,2.6.4 圖的應(yīng)用,迪杰斯特拉(Dijkstra)算法的基本思想：,Dijkstra算法, 初始化：

24、 S v0 ; distj Edge0j, j = 1, 2, , n-1;(n為圖中頂點(diǎn)數(shù)) 求出最短路徑的長度： distk min disti , i V- S ; S S U k ; 對(duì)于每一個(gè)iV-S; 修改： disti min disti, distk + Edgeki , 判斷：若 S = V, 則算法結(jié)束，否則轉(zhuǎn) 。,2.6.4 圖的應(yīng)用,舉例：Dijkstra逐步求解的過程,1,0,4,3,2,10,100,30,50,20,60,10,源點(diǎn) s 終點(diǎn) 最短路徑path 路徑長度dist,v0 v0 v1 (v0,v1) 10 v0,1 v2 (v0,v1,v2) (v0,

25、v3,v2) ,60,50 v0,1,3 v3 (v0,v3) 30 v0,1,3,2 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100,90,60 v0,1,3,2,4,void ShortestPath (MTGraph G, int v ) /MTGraph是一個(gè)有 n 個(gè)頂點(diǎn)的帶權(quán)有向圖,各邊上的權(quán)值由Edgeij給出。 /distj, 0 jn, 是當(dāng)前求到的從頂點(diǎn)v 到頂點(diǎn) j 的最短路徑長度, 用數(shù)組pathj, 0 jn, 存放求到的最短路徑。 EdgeData distG.n; /最短路徑長度數(shù)組 int pathG.n; /最短路徑數(shù)組 in

26、t SG.n; /最短路徑頂點(diǎn)集,計(jì)算從單個(gè)頂點(diǎn)到其它各頂點(diǎn)最短路徑,2.6.4 圖的應(yīng)用,for ( int i = 0; i n; i+) disti = G.Edgevi; /dist數(shù)組初始化 Si = 0; /集合S初始化 if ( i != v ,2.6.4 圖的應(yīng)用,for ( int j = 0; j n; j+ )/選當(dāng)前不在集合S中具有最if ( !Sj /修改到w的最短路徑 # /選定各頂點(diǎn)到頂點(diǎn) v 的最短路徑,/打印各頂點(diǎn)的最短路徑: 路徑是逆向輸出的 for ( i = 0; i G.n; i+ ) cout endl; cout “Distance: ” dist

27、i “ Path: ” i; /輸出終點(diǎn)的最短路徑長度和終點(diǎn) int pre = pathi; /取終點(diǎn)的直接前驅(qū) while ( pre != v ) /沿路徑上溯輸出 cout “, ” pre; pre = pathpre; ,拓?fù)渑判?計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。 例：計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。,頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(Activ

28、ity On Vertex Network/AOV網(wǎng)絡(luò)),2.6.4 圖的應(yīng)用,C1 高等數(shù)學(xué) C2 程序設(shè)計(jì)基礎(chǔ) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級(jí)語言程序設(shè)計(jì) C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計(jì)算機(jī)原理 C8,課程代號(hào) 課程名稱 先修課程,學(xué)生課程學(xué)習(xí)工程圖,C8,C3,C5,C4,C9,C6,C7,C1,C2,可以用有向圖表示一個(gè)工程。在這種有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)Vi 必須先于活動(dòng)Vj 進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動(dòng)的AOV網(wǎng)絡(luò) (Activity On Vertex)

29、。 在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路, 即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。 因此，對(duì)給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。,2.6.4 圖的應(yīng)用,檢測(cè)有向環(huán)的一種方法是對(duì)AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄小＜磳⒏鱾€(gè)頂點(diǎn) (代表各個(gè)活動(dòng))排列成一個(gè)線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。 這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判颉?如果通過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個(gè)拓?fù)溆行虻男蛄兄? 則該網(wǎng)絡(luò)中必定不會(huì)出現(xiàn)有向環(huán)。,2.6.4 圖的應(yīng)用,如果AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可

30、行的。 例如, 對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判? 得到的拓?fù)溆行蛐蛄袨?C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6,2.6.4 圖的應(yīng)用,拓?fù)渑判虻姆椒? 輸入AOV網(wǎng)絡(luò)。令 n 為頂點(diǎn)個(gè)數(shù)。 在AOV網(wǎng)中選一個(gè)沒有直接前驅(qū)的頂點(diǎn), 并輸出之; 從圖中刪去該頂點(diǎn), 同時(shí)刪去所有它發(fā)出的有向邊; 重復(fù)以上 、步, 直到 全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿桑换?圖中還有未輸出的頂點(diǎn), 但已跳出處理循環(huán)。說明圖中還剩下一些頂點(diǎn), 它們都有直接前驅(qū)。這時(shí)網(wǎng)絡(luò)中

31、必存在有向環(huán)。,2.6.4 圖的應(yīng)用,C0,C1,C2,C3,C4,C5,拓?fù)渑判虻倪^程,(a) 有向無環(huán)圖,C2,C5,C1,C0,C3,(b) 輸出頂點(diǎn)C4,C1,C2,C5,C3,(c) 輸出頂點(diǎn)C0,C4,C0,C2,C5,C1,C3,(d) 輸出頂點(diǎn)C3,C1,C2,C5,(e) 輸出頂點(diǎn)C2,C5,C1,(f) 輸出頂點(diǎn)C1,C5,(g) 輸出頂點(diǎn)C5,拓?fù)溆行蛐蛄袨?C4 , C0 , C3 , C2 , C1 , C5 。 它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對(duì)于本來沒有這種關(guān)系的頂點(diǎn)(如C4和C2)，也排出了先后次序。,(h) 拓?fù)渑判蛲瓿?AOV網(wǎng)絡(luò)及其鄰接表表示,C0,C1,C2,C3,C4,C5,C0 C1 C2 C3 0 C4 C5 0,0 1