數(shù)據(jù)結(jié)構(gòu)(長安大學(xué))講課PPT6

1、數(shù)據(jù)結(jié)構(gòu)教師教師：楊云 班級班級：24020803/04 學(xué)院學(xué)院：長安大學(xué)信息工程學(xué)院 地址地址：WM1506 Email：數(shù)據(jù)結(jié)構(gòu) -學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的方法邏輯結(jié)構(gòu)運算定義存儲結(jié)構(gòu)實現(xiàn)運算分析 第七章 圖7.1 圖的定義和基本概念7.2 圖的存儲結(jié)構(gòu) 7.2.1 數(shù)組表示法 7.2.2 鄰接表 7.2.3 十字鏈表 7.2.4 鄰接多重表7.3 圖的遍歷 7.3.1 深度優(yōu)先搜索 7.3.2 廣度優(yōu)先搜索7.4 圖的連通性 7.4.1 無向圖的連通分量和生成樹 7.4.2 最小生成樹7.5 有向五環(huán)圖及其應(yīng)用 7.5.1 拓?fù)渑判?7.5.2 關(guān)鍵路徑7.6 最短路徑 7.6.1 從某個源點到

2、其余各頂點的最短路徑 7.6.2 每一對頂點之間的最短路徑 7 圖 圖是另一種非線性結(jié)構(gòu)，它比樹更復(fù)雜、更一般化，因此可以把樹看成是簡單的圖。 圖的應(yīng)用范圍極廣，近年來已經(jīng)滲入到各個領(lǐng)域，如語言學(xué)、邏輯學(xué)、數(shù)學(xué)、物理、化學(xué)、計算機科學(xué)和各種工程學(xué)領(lǐng)域。 比樹的結(jié)構(gòu)更加復(fù)雜 沒有嚴(yán)格的層次 結(jié)點之間的關(guān)系是任意的 回憶：離散數(shù)學(xué)中關(guān)于圖的概念7.1 圖的定義和基本術(shù)語基本概念：什么是圖無向圖、邊、度有向圖、弧、出度和入度鄰接結(jié)點、鄰接邊路徑、連通性、連通分支生成樹特殊圖：完全圖、稀疏圖、帶權(quán)圖一、圖的定義一、圖的定義圖圖:由頂點集V和連接頂點的邊（弧）集E所組成的結(jié)構(gòu)，記作G=(V,E)； V是

3、頂點(元素)的有窮非空集， E是兩個頂點之間的關(guān)系的集合。12343124V=1,2,3,4E=,V=1,2,3,4E=(1,2),(1,3),(2,4),(1,4),(3,4) 圖的數(shù)據(jù)對象：圖的頂點集合 圖的數(shù)據(jù)關(guān)系：圖中各頂點之間的關(guān)系，就是邊（或稱作?。?注意：上述關(guān)系是非線性的，多對多的關(guān)系，即前驅(qū)/后繼關(guān)系都不是唯一的！ 圖中的數(shù)據(jù)元素具有相同特性，稱為頂點； 若頂點a,c之間的關(guān)系為有序?qū)τ行驅(qū)?且E 則稱為從a到c的一條弧弧/有向邊有向邊； a是的弧尾弧尾， c是的弧頭弧頭； 此時的圖G稱為有向圖有向圖。 例 G1=V1,E1, V1=A,B,C,D,E E1=, 二、基本概念

4、二、基本概念A(yù)BCEDG1 圖中若頂點之間的關(guān)系有則必，即為無序?qū)Γ╝,c）； 則無序?qū)Γ╝,c）表示a和c之間的一條邊， 此時的圖G稱為無向圖。 例 G2=V2,E2, V2=A,B,C,D ABCDE2=（A,B）,（A,C）,（A,D）,（B,D）G2 若無向圖G中任意兩點間都有一條邊，則稱此圖G為無向完全圖無向完全圖。即n個頂點的無向完全圖有n(n-1)/2條邊；v1Av2Cv3G1 G2 G3 G4 G5 Bv1v1v2DACBDEe=1(1-1)/2 =0e=2(2-1)/2 =1e=3(3-1)/2 =3e=4(4-1)/2 =6e=5(5-1)/2 =10 若有向圖G中任意一個

5、頂點到其余各點間均有一條弧，則稱G為有向完全圖有向完全圖。即n個頂點的有向完全圖有n(n-1)條??；123G1 G2 G3112e=1(1-1) =0e=2(2-1) =2e=3(3-1) =6 圖的邊或弧具有與其相關(guān)的數(shù)值，這個數(shù)值稱為權(quán)(weight) 。 網(wǎng)(Network)-邊(弧)上加權(quán)的圖。123無向網(wǎng)G14ABC41559943有向網(wǎng)G2 有很少的邊或弧的圖稱為稀疏圖； 反之稱為稠密圖。若一個圖G1=(V1，E1)是從G中選取部分頂點和部分邊（或?。┙M成，即V1V，E1E，則稱G1是G的子圖子圖。123G412G1341G2341G4123G34G1,G2,G3是G的子圖 G4不

6、是G的子圖2相鄰相鄰：若無向圖中（i，j）E i，j相鄰，若有向圖中 E i，j相鄰； i與j互為鄰接點，或者稱i與j相關(guān)聯(lián)。123456度度與頂點x相關(guān)聯(lián)的邊(x,y)的數(shù)目,稱為x的度度，記作TD(x) 或D(x)；25413G1 TD(1)=1 TD(2)=3 TD(3)=0出度出度以頂點x為弧尾的弧的數(shù)目,稱為x的出出度度，記作OD(x)。入度入度以頂點x為弧頭的弧的數(shù)目, 稱為x的入度入度，記作ID(x)。ABCG2OD(A)=1OD(B)=2OD(C)=0ID(A)=1 ID(B)=1ID(C)=1TD(A)=OD(A)+ID(A)=2 TD(B)=OD(B)+ID(B)=3TD(

7、C)=OD(C)+ID(C)=1注意： 無向圖：度 有向圖：入度，出度。 有向圖中某結(jié)點的度入度出度。路徑路徑：圖中從頂點x到達(dá)頂點y的頂點序列稱為路徑；有向圖中路徑也是有向的，路徑上的邊或弧的數(shù)目稱為路徑的長度； （1）序列中頂點無重復(fù)出現(xiàn)簡單路徑； （2）若首尾頂點相同回路； （3）若首尾相同且序列中間頂點無重復(fù)出現(xiàn)簡單回路 ；12341234 對無向圖G： 若從頂點vi到vj有路徑,則稱vi和vj是連通連通的。 若圖G中任意兩頂點是連通的,則稱G是連通圖連通圖。123456GAFECBGDAFECBG1DG2G3 連通分量連通分量- -是無向圖中的是無向圖中的極大連通子圖極大連通子圖。G

8、GG有三個連通分量有三個連通分量否則不連通不連通，就存在若干連通分量連通分量。如：G為連通圖，而G為非連通圖。 對有向圖G 若在圖G中,每對頂點vi和vj之間, 從vi到vj,且從vj 到vi都存在路徑,則稱G是強連通圖強連通圖。 若圖G是G的一個極大強連通子圖極大強連通子圖,則稱G是G的一個 強連通分量強連通分量。BCG1ADBC G11 是是G1的強連通分量強連通分量ADBC G12不是不是G1的強連通分量強連通分量ADBCG2ADBCG21ADG22G2有兩個強連通分量有兩個強連通分量 設(shè)G=(V,E),G=(V,E),V=V,若G是連通圖, G是G的一個極小連通子圖極小連通子圖, ,

9、則G是G的一棵生成樹生成樹。 注：生成樹包含圖中全部頂點，但只有足以構(gòu)成一顆樹的n-1條邊。EDGBCAEDT1BCAEDT4BCAEDT3BCAEDT2BCAG的多棵生成樹 若有向圖G有且僅有一個頂點的入度為0，其余頂點的入度為1,則G是一棵有向樹有向樹。 注意：一個有向圖的有向森林由若干棵有向樹組成，含有圖中全部頂點，但只有足以構(gòu)成若干棵不相交的有向樹的弧。EDT1BCAEDT2BCAEBT3ACEEDT4BCAEDT5BCAEDT6BCAT1,T2,T3,T4是有向樹有向樹T5,T6不是有向樹有向樹 有向圖的生成樹/生成森林。EDGBCAEBFADFFC三、圖的基本操作（1） Creat

10、eGraph(&G, V, VR); DestroyGraph(&G); LocateVex(G, u); GetVex(G, v); PutVex(&G, v, value); FirstAdjVex(G, v); NextAdjVex(G, v, w);圖的基本操作（2） InsertVex(&G, v); DeleteVex(&G, v); InsertArc(&G, v, w); DeleteArc(&G, v, w); DFSTraverse(G, v, Visit(); BFSTraverse(G, v, Visit();圖的

11、存儲結(jié)構(gòu)考慮 比樹更加復(fù)雜的非線性結(jié)構(gòu) 無法直接用順序結(jié)構(gòu)表示結(jié)點之間的關(guān)系（但是可以間接表示） 自然的鏈?zhǔn)浇Y(jié)構(gòu)：需要一個良好的鏈?zhǔn)浇Y(jié)構(gòu)7.2 圖的存儲結(jié)構(gòu)一、 數(shù)組表示法/鄰接矩陣頂點數(shù)組頂點數(shù)組-用一維數(shù)組存儲頂點(元素)鄰接矩陣鄰接矩陣-用二維數(shù)組存儲頂點(元素)之間的關(guān)系(邊或弧) 143G2 1 2 3 41 0 0 1 12 0 0 0 03 1 0 0 14 1 0 1 0 M=例1鄰接矩陣鄰接矩陣 1 2 3 41 2 3 4頂點數(shù)組頂點數(shù)組V1.41.1 1.1 鄰接矩陣鄰接矩陣1、不帶權(quán)值設(shè)圖中有n個頂點：Ann aij 1 E 0或 否則對稱123411110110111

12、10000非0元素個數(shù)12341 2 3 444不對稱12341110000010100000第i非0元素個數(shù)=對應(yīng)頂點的度第i非0元素個數(shù)=對應(yīng)頂點的度12341 2 3 4442、帶權(quán)值 aij Vij E 0或 否則123453650230462400002536412341 2 3 4441.2 圖的數(shù)組表示法數(shù)據(jù)結(jié)構(gòu)定義/圖的類型和弧的定義#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最大頂點數(shù)typedef enum DG, DN, AG, AN GraphKind;/有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef s

13、truct ArcCellVRType adj; /頂點關(guān)系，無權(quán)圖0或1，帶權(quán)圖為權(quán)InfoType *info; /該弧相關(guān)信息的指針ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/圖的數(shù)組定義typedef structVertexType vexsMAX_VERTEX_NUM; /頂點向量AdjMatrix arcs; /鄰接矩陣int vexnum, arcnum; /圖的當(dāng)前頂點數(shù)和弧數(shù)GraphKind kind; /圖的種類標(biāo)志MGraph;圖的數(shù)組表示的應(yīng)用 鄰接矩陣中的含義 無向圖與對稱性 頂點的度 權(quán) 建立在鄰接矩陣上的算法舉

14、例： P162的算法7.1和算法7.2，用于構(gòu)造圖和構(gòu)造無向網(wǎng)二、鄰接表二、鄰接表12341234data firstadj逆鄰接表：1234data firstadj圖的鄰接表存儲數(shù)據(jù)結(jié)構(gòu)定義#define MAX_VERTEX_NUM 20 typedef struct ArcNodeint adjvex; /該弧所指向的頂點的位置struct ArcNode *nextarc; /指向下一條弧的指針I(yè)nfoType *info; /該弧相關(guān)信息的指針ArcNode;typedef struct VNodeVertexType data; /頂點信息ArcNode *firstarc; /

15、指向第一條依附該頂點的弧的指針VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum; /圖的當(dāng)前頂點數(shù)和弧數(shù)int kind; /圖的種類標(biāo)志ALGraph;有向圖的十字鏈表十字鏈表- 將鄰接表和逆鄰接表合并而成的鏈接表。 CBADABCD 1 2 3 41 GG的逆逆鄰接表鄰接表134 ABCD 1 2 3 44 3 G的鄰接表鄰接表2 2ABCD1234G的十字鏈表十字鏈表3 21 24 2 14 4 3 24 4 1 1 4 三、有向圖的十字鏈表三、有向圖的十字鏈表四、 無向圖的鄰接多

16、重表鄰接多重表-另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)EDFBACGABCDEF012023013024034056序號序號 data firstedgedata firstedge(A,B)(A,C)(B,C)(B,D)(C,D)(E,F)隱含的鏈接表：隱含的鏈接表： A (1,2) (1,3) B (1,2) (2,3) (2,4) C (1,3) (2,3) (3,4) D (2,4) (3,4) E (5,6) F (5,6)ma vi vj vil vjlma vi vj vil vjl123456 圖的一條邊或弧用一個“頭結(jié)點頭結(jié)點”表示，其中： markmark-標(biāo)志域，可用以標(biāo)記該條邊是否被搜索過

17、； vivi和和vjvj-該條邊依附的兩個頂點在圖中的位置； vilvilinkink-指向下一條依附于頂點vi的邊； vjlvjlinkink-指向下一條依附于頂點vj的邊。 0 1 2mark vi vj vilink vjlinkmark vi vj vilink vjlinkdata firstedgedata firstedgeA表示頂點A的頭結(jié)點頭結(jié)點表示邊或弧(v1,v2)的表表結(jié)點結(jié)點 圖的一個頂點用一個“頭結(jié)點頭結(jié)點”表示，其中： datadata域域存儲和該頂點相關(guān)的信息， firstedgefirstedge域域存儲第一條依附于該頂點的邊。表表結(jié)點結(jié)點7.3 圖的遍歷一、

18、定義：從圖的某頂點出發(fā)，訪問圖中每個頂點一次且僅一次。 圖的遍歷算法：l深度優(yōu)先搜索（ Depth-First Search ）DFSl廣度優(yōu)先搜索（ Breadth-First Search ）BFS一、深度優(yōu)先搜索遍歷（一、深度優(yōu)先搜索遍歷（dfsdfs） DFS（Depth-First Search）算法是圖論中最重要的算法之一，它的思路可以用來表述。下圖是1690年獨裁者威廉王修筑的迷宮示意圖，現(xiàn)遺址在奧地利。xbdefclghijak迷宮法則 任務(wù)是從事先未知結(jié)構(gòu)的迷宮入口出發(fā)，每個走廊都要搜索，再從入口退出。為了不兜圈子盡快退出，要記住哪些走廊已經(jīng)走過，沿著未走過的走廊盡可能地走下

19、去，走到已無未走過的走廊可走時，沿來路返回，到某一路口，發(fā)現(xiàn)可通往一條未走過的走廊時，沿此走廊搜索，依次類推，直至完成任務(wù)。迷宮法則一直往前走碰壁就回頭換條路走沿途要記錄走過的路線老鼠走迷宮dfs1、基本遍歷算法的描述： 1973年，用上述迷宮思想，Hopcroft和Tarjan設(shè)計了下面有效的DFS算法。 dfs(v0)從v0出發(fā)深度遍歷1、訪問v0visit(v0)；2、依次從v0未被訪問未被訪問的鄰接點出發(fā)深度遍歷。深度優(yōu)先搜索過程：v0v1v3v5v4v2v6v7搜索回溯dfs(v0)v0v1v3v5v4v2v7v6序列：序列：v0- v1 -v3- v5 -v4- v2 v6- v7

20、dfs(v1)dfs(v3)dfs(v5)dfs(v4)dfs(v6)dfs(v7)dfs(v2)DFS生成樹搜索過程形成DFS生成樹，如下圖：v0v1v3v5v4v2v7v62、DFS算法的實現(xiàn)： dfs(v0)從v0出發(fā)深度遍歷1、訪問v0visit(v0)；2、依次從v0未被訪問未被訪問的鄰接點出發(fā)深度遍歷。 未被訪問：visitedi=1（訪問）/0（未訪問）； 求鄰接點：firstadj，nextadj； nodes(G)返回圖G的結(jié)點數(shù)。 求鄰接點： firstadj(i)返回頂點i的第一個鄰接點，找不到返回0；如：w=firstadj(1);/w2; nextadj(i,j)返回

21、頂點i位于結(jié)點j后的鄰接點，找不到返回0；如：w=nextadj(1,2);/w=3;1234基于以上討論，得dfs算法如下：void dfs(Graph G,int v0) visit(v0); visitedv0=ture; w=firstadj(G, v0); while(w!=0) if(visitedw=false) dfs(G,w); w=nextadj(G,v0,w); 123458679遍歷整個圖的算法如下：void dfs-travel(Graph G) for (i=1;i=nodes(G);i+) visiedi=false; for (i=1;i=nodes(G);i+

22、) if(visitedi=false) dfs(G,i);1234586793、DFS算法的應(yīng)用：1、設(shè)計算法判斷圖G是否連通。2、設(shè)計算法求圖G的連通分量數(shù)。思考題：設(shè)計算法求圖G的dfs生成樹；相鄰數(shù)相加質(zhì)數(shù)問題；求路徑問題； 可以看出，用dfs對迷宮進(jìn)行搜索，可以找出穿過迷宮的路，但是不一定是最短的。如果要找出最短的，則對迷宮進(jìn)行bfs搜索。二、廣度優(yōu)先搜索（BFS） BFS（Breadth-First Search）算法的描述bfs(v0)從v0出發(fā)廣度遍歷1、訪問v0visit(v0)；2、依次訪問v0的鄰接點；3、假設(shè)最近一層訪問的結(jié)點次序為vk1，vk2，vkm，依次訪問vk1

23、，vk2，vkm的鄰接點；廣度優(yōu)先搜索過程：v0v1v3v5v4v2v6v7bfs(v0)v0v1v3v5v4v2v7v6序列：序列：v0-v1-v2-v3-v4- v6- v7-v5搜索BFS生成樹搜索過程形成BFS生成樹，如下圖：v0v1v3v5v4v2v7v6BFS算法的一個顯著特點是：層次性。所以可以用來求兩點間最短路徑。01入口出口0117.4 圖的連通性 深度優(yōu)先遍歷（DFS)生成樹 廣度優(yōu)先遍歷（BFS）生成樹 DFS生成森林 BFS生成森林一、DFS生成樹：假定從A A出發(fā)DFSDFS遍歷圖G：FDBCAGHEI圖GABABABADCDFDBCAFDBCAIFDBCAIGDFS

24、生成樹T1FDBCAGHEI圖GFDBCAIGHFDBCAIGHEFDBCAIGHEDFS生成樹T2ECBDAIGFH二、 BFSBFS生成樹生成樹FDBCAGHEI圖G假定從A A出發(fā)BFSBFS遍歷圖G：AABABFABEFABEFCABEFCDABEFCDIFDBCAGHEI圖GABEFCDIHGABEFCDIHABEFCDIHGABEFCDIHGBFS生成樹T1BFS生成樹T2三、 DFSDFS生成森林生成森林CKIJADEBFGH從A A出發(fā)，得樹T1：T2CADEBF圖GT3T1從G G出發(fā),得樹T2：CADEBFT1GHT2CADEBFT1GHKIJ從I I出發(fā),得樹T3：四、

25、BFSBFS生成森林生成森林CKIJADEBFGH從A A出發(fā)，得樹T1：T2圖GT3T1從G G出發(fā),得樹T2：AT1GHT2T1GHKIJ從I I出發(fā),得樹T3：CDEBFACDEBFACDEBF7.5 有向無環(huán)圖及其應(yīng)用 最小生成樹 拓?fù)渑判?最短路徑 關(guān)鍵路徑一、 最小生成樹最小生成樹 假設(shè)在n個城市之間建立一個通信網(wǎng)絡(luò)，最少需要n-1條邊（最多為n(n-1)/2）。 邊上賦予相應(yīng)的代價。 可以有多棵生成樹，那么選擇一棵代價最小的生成樹！ 要在 n 個小區(qū)間建立能源網(wǎng)，現(xiàn)在要考慮的問題如何在保證 n 個小區(qū)連通的前提下最節(jié)省經(jīng)費?上述問題即要使得生成樹各邊權(quán)值之和，即：)(),()(T

26、EvuuvwTW12354435323136 問題描述： 在有n個頂點的帶權(quán)連通圖G中，選取條邊以構(gòu)成一棵樹，要求所選邊權(quán)值之和最小。這樣的樹稱為圖G的。最小生成樹的性質(zhì) 假設(shè)N=（V，E）是一個連通網(wǎng)，U是V的一個非空子集。若（u,v）是一條具有最小權(quán)值的邊，那么必存在一棵包含邊（u,v）的最小生成樹，其中u是U中的一個頂點，v是V-U中的一個頂點。( (一一)prim)prim算法算法( (普里姆普里姆) )1、基本思想： 在滿足如下條件選擇權(quán)值最小權(quán)值最小的邊一端已入選，另一端未入選。 N=（V，E），TE是N上最小生成樹的邊的集合。（1）初始化：U=u0, TE=；（2）在所有uU,

27、vV-U的邊（u,v）E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U；（3）重復(fù)（2），直至U=V。2、求解實例求下圖的最小生成樹：123541235443532313612354最小生成樹不唯一，但權(quán)值之和相同。 例：求例：求G G的最小生成樹的最小生成樹 CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點為主以選頂點為主DTCD5TCAD15CADB3156CADEB3156TTT圖G的最小生成樹 CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點為主以選頂點為主6CADEB3156TF4另一

28、最小生成樹CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點為主以選頂點為主DTDT6TTTB5ADB35ADB35C1ADB35C1E6另一最小生成樹 CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點為主以選頂點為主6CADEB316TF45Prim算法的關(guān)鍵 按照最小生成樹的性質(zhì)進(jìn)行頂點擴(kuò)張。 每擴(kuò)展一個頂點，在兩個頂點集合中都要更新當(dāng)前的最小邊。 以鄰接矩陣為存儲結(jié)構(gòu)，時間復(fù)雜度為O（n2），與邊數(shù)無關(guān)！( (二二)Kruskal)Kruskal算法算法( (克魯斯卡爾克魯斯卡爾) )1、基本思想： 在滿足

29、如下條件選擇權(quán)值最小權(quán)值最小的邊和已選邊不構(gòu)成回路。 N=（V，E），TE是N上最小生成樹的邊的集合。（1）初始化：T=（V，），即TE=；（2）在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到TE中，否則選擇下一條代價最小的邊；（3）重復(fù)（2），直至所有頂點都在同一連通分量上為止。2、求解實例求下圖的最小生成樹：1235443532313612354最小生成樹不唯一，但權(quán)值之和相同?？唆斔箍枺唆斔箍枺↘ruskaiKruskai) )算法，以選邊為主以選邊為主CADEBF圖G371874556TT6TTTCACAB113CAB13EF4CAB13EF4D

30、5CADEBF31456克魯斯卡爾（克魯斯卡爾（KruskaiKruskai) )算法，以選邊為主以選邊為主CADEBF圖G371874556TT6TTTCACAB113CAB13EF4CAB13EF4DCADEBF314655刪除權(quán)最大的邊，保留刪除權(quán)最大的邊，保留n-1n-1條條CADEBF圖G3718745566CADEBF371745566CADEBF37145566圖G圖GCADEBF圖G3718745566刪除權(quán)最大的邊，保留刪除權(quán)最大的邊，保留n-1n-1條條CADEBF圖G3718745566CADEBF314556TCADEBF31456圖GCADEBF3145566圖GKr

31、uskal算法的特征 按照最小生成樹的性質(zhì)進(jìn)行邊的擴(kuò)展 每擴(kuò)展一條邊，都需要判斷有無形成回路 以鄰接矩陣為存儲結(jié)構(gòu)時，時間復(fù)雜度可以達(dá)到O（eloge)，與頂點數(shù)無關(guān)！二、 拓?fù)渑判蛲負(fù)渑判蛲負(fù)渑判?偏序關(guān)系的一個序列 拓?fù)渑判虻膽?yīng)用：選課次序 工程施工流程圖：AOV網(wǎng)（一）問題描述：（一）問題描述：由多項子工程（活動）組成，子工程（活動）之間存在制約關(guān)系。用圖表示工程，頂點表示子工程（活動），弧表示活動間的制約關(guān)系。(1)工程是否能順利完成？ 圖中是否存在回路？(2)工程需要多少時間完成？(3)哪些是關(guān)鍵性工程？（二）拓?fù)渑判蚍椒皩崿F(xiàn)（二）拓?fù)渑判蚍椒皩崿F(xiàn)(AOV(AOV網(wǎng)網(wǎng)) )1、如

32、何判斷AOV網(wǎng)中是否存在有向回路？解決方法：(1)用深度遍歷要做許多試探性工作；(2)用產(chǎn)生頂點序列的方法拓?fù)渑判颍蝗绻墚a(chǎn)生包含的拓?fù)湫蛄袆t說明AOV網(wǎng)中無回路，否則有回路。2、拓?fù)渑判虿襟E： (1)選擇一個沒有前驅(qū)的頂點(入度為0)的頂點v；(2)此頂點排序后即刪除之，并刪除所有以它為尾的?。▽⒋嘶〉念^的頂點的入度減1）；(3)重復(fù)(1)、(2)，直到重復(fù)上述過程，直至所有頂點都被排序(找不到入度為0的頂點)為止。123456求下圖的拓?fù)湫蛄校?、求解實例12345653124563465123456312345612354624565123456465312345612345664512345646245653123456123456三、 最短路徑問題引入：問題引入： 兩類問題：(1)從單點到其余頂點的最短路徑；(2)各點間的最短路徑。123456