1、數(shù)據(jù)結(jié)構(gòu)教師教師：楊云 班級(jí)班級(jí)：24020803/04 學(xué)院學(xué)院：長安大學(xué)信息工程學(xué)院 地址地址：WM1506 Email：數(shù)據(jù)結(jié)構(gòu) -學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的方法邏輯結(jié)構(gòu)運(yùn)算定義存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)運(yùn)算分析 第七章 圖7.1 圖的定義和基本概念7.2 圖的存儲(chǔ)結(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 從某個(gè)源點(diǎn)到

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

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

4、二、基本概念A(yù)BCEDG1 圖中若頂點(diǎn)之間的關(guān)系有則必，即為無序?qū)Γ╝,c）； 則無序?qū)Γ╝,c）表示a和c之間的一條邊， 此時(shí)的圖G稱為無向圖。 例 G2=V2,E2, V2=A,B,C,D ABCDE2=（A,B）,（A,C）,（A,D）,（B,D）G2 若無向圖G中任意兩點(diǎn)間都有一條邊，則稱此圖G為無向完全圖無向完全圖。即n個(gè)頂點(diǎ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中任意一個(gè)

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

6、是G的子圖2相鄰相鄰：若無向圖中（i，j）E i，j相鄰，若有向圖中 E i，j相鄰； i與j互為鄰接點(diǎn)，或者稱i與j相關(guān)聯(lián)。123456度度與頂點(diǎn)x相關(guān)聯(lián)的邊(x,y)的數(shù)目,稱為x的度度，記作TD(x) 或D(x)；25413G1 TD(1)=1 TD(2)=3 TD(3)=0出度出度以頂點(diǎn)x為弧尾的弧的數(shù)目,稱為x的出出度度，記作OD(x)。入度入度以頂點(diǎn)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é)點(diǎn)的度入度出度。路徑路徑：圖中從頂點(diǎn)x到達(dá)頂點(diǎn)y的頂點(diǎn)序列稱為路徑；有向圖中路徑也是有向的，路徑上的邊或弧的數(shù)目稱為路徑的長度； （1）序列中頂點(diǎn)無重復(fù)出現(xiàn)簡單路徑； （2）若首尾頂點(diǎn)相同回路； （3）若首尾相同且序列中間頂點(diǎn)無重復(fù)出現(xiàn)簡單回路 ；12341234 對(duì)無向圖G： 若從頂點(diǎn)vi到vj有路徑,則稱vi和vj是連通連通的。 若圖G中任意兩頂點(diǎn)是連通的,則稱G是連通圖連通圖。123456GAFECBGDAFECBG1DG2G3 連通分量連通分量- -是無向圖中的是無向圖中的極大連通子圖極大連通子圖。G

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

9、則G是G的一棵生成樹生成樹。 注：生成樹包含圖中全部頂點(diǎn)，但只有足以構(gòu)成一顆樹的n-1條邊。EDGBCAEDT1BCAEDT4BCAEDT3BCAEDT2BCAG的多棵生成樹 若有向圖G有且僅有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度為1,則G是一棵有向樹有向樹。 注意：一個(gè)有向圖的有向森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(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、存儲(chǔ)結(jié)構(gòu)考慮 比樹更加復(fù)雜的非線性結(jié)構(gòu) 無法直接用順序結(jié)構(gòu)表示結(jié)點(diǎn)之間的關(guān)系（但是可以間接表示） 自然的鏈?zhǔn)浇Y(jié)構(gòu)：需要一個(gè)良好的鏈?zhǔn)浇Y(jié)構(gòu)7.2 圖的存儲(chǔ)結(jié)構(gòu)一、 數(shù)組表示法/鄰接矩陣頂點(diǎn)數(shù)組頂點(diǎn)數(shù)組-用一維數(shù)組存儲(chǔ)頂點(diǎn)(元素)鄰接矩陣鄰接矩陣-用二維數(shù)組存儲(chǔ)頂點(diǎn)(元素)之間的關(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頂點(diǎn)數(shù)組頂點(diǎn)數(shù)組V1.41.1 1.1 鄰接矩陣鄰接矩陣1、不帶權(quán)值設(shè)圖中有n個(gè)頂點(diǎn)：Ann aij 1 E 0或 否則對(duì)稱123411110110111

12、10000非0元素個(gè)數(shù)12341 2 3 444不對(duì)稱12341110000010100000第i非0元素個(gè)數(shù)=對(duì)應(yīng)頂點(diǎn)的度第i非0元素個(gè)數(shù)=對(duì)應(yīng)頂點(diǎn)的度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 /最大頂點(diǎn)數(shù)typedef enum DG, DN, AG, AN GraphKind;/有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef s

13、truct ArcCellVRType adj; /頂點(diǎn)關(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; /頂點(diǎn)向量AdjMatrix arcs; /鄰接矩陣int vexnum, arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKind kind; /圖的種類標(biāo)志MGraph;圖的數(shù)組表示的應(yīng)用 鄰接矩陣中的含義 無向圖與對(duì)稱性 頂點(diǎn)的度 權(quán) 建立在鄰接矩陣上的算法舉

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

15、指向第一條依附該頂點(diǎn)的弧的指針VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum, arcnum; /圖的當(dāng)前頂點(diǎn)數(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)酱鎯?chǔ)結(jié)構(gòu)EDFBACGABCDEF012023013024034056序號(hào)序號(hào) 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 圖的一條邊或弧用一個(gè)“頭結(jié)點(diǎn)頭結(jié)點(diǎn)”表示，其中： markmark-標(biāo)志域，可用以標(biāo)記該條邊是否被搜索過

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

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

19、去，走到已無未走過的走廊可走時(shí)，沿來路返回，到某一路口，發(fā)現(xiàn)可通往一條未走過的走廊時(shí)，沿此走廊搜索，依次類推，直至完成任務(wù)。迷宮法則一直往前走碰壁就回頭換條路走沿途要記錄走過的路線老鼠走迷宮dfs1、基本遍歷算法的描述： 1973年，用上述迷宮思想，Hopcroft和Tarjan設(shè)計(jì)了下面有效的DFS算法。 dfs(v0)從v0出發(fā)深度遍歷1、訪問v0visit(v0)；2、依次從v0未被訪問未被訪問的鄰接點(diǎn)出發(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算法的實(shí)現(xiàn)： dfs(v0)從v0出發(fā)深度遍歷1、訪問v0visit(v0)；2、依次從v0未被訪問未被訪問的鄰接點(diǎn)出發(fā)深度遍歷。 未被訪問：visitedi=1（訪問）/0（未訪問）； 求鄰接點(diǎn)：firstadj，nextadj； nodes(G)返回圖G的結(jié)點(diǎn)數(shù)。 求鄰接點(diǎn)： firstadj(i)返回頂點(diǎn)i的第一個(gè)鄰接點(diǎn)，找不到返回0；如：w=firstadj(1);/w2; nextadj(i,j)返回

21、頂點(diǎn)i位于結(jié)點(diǎn)j后的鄰接點(diǎn)，找不到返回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遍歷整個(gè)圖的算法如下：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è)計(jì)算法判斷圖G是否連通。2、設(shè)計(jì)算法求圖G的連通分量數(shù)。思考題：設(shè)計(jì)算法求圖G的dfs生成樹；相鄰數(shù)相加質(zhì)數(shù)問題；求路徑問題； 可以看出，用dfs對(duì)迷宮進(jìn)行搜索，可以找出穿過迷宮的路，但是不一定是最短的。如果要找出最短的，則對(duì)迷宮進(jìn)行bfs搜索。二、廣度優(yōu)先搜索（BFS） BFS（Breadth-First Search）算法的描述bfs(v0)從v0出發(fā)廣度遍歷1、訪問v0visit(v0)；2、依次訪問v0的鄰接點(diǎn)；3、假設(shè)最近一層訪問的結(jié)點(diǎn)次序?yàn)関k1，vk2，vkm，依次訪問vk1

23、，vk2，vkm的鄰接點(diǎn)；廣度優(yōu)先搜索過程：v0v1v3v5v4v2v6v7bfs(v0)v0v1v3v5v4v2v7v6序列：序列：v0-v1-v2-v3-v4- v6- v7-v5搜索BFS生成樹搜索過程形成BFS生成樹，如下圖：v0v1v3v5v4v2v7v6BFS算法的一個(gè)顯著特點(diǎn)是：層次性。所以可以用來求兩點(diǎn)間最短路徑。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個(gè)城市之間建立一個(gè)通信網(wǎng)絡(luò)，最少需要n-1條邊（最多為n(n-1)/2）。 邊上賦予相應(yīng)的代價(jià)。 可以有多棵生成樹，那么選擇一棵代價(jià)最小的生成樹！ 要在 n 個(gè)小區(qū)間建立能源網(wǎng)，現(xiàn)在要考慮的問題如何在保證 n 個(gè)小區(qū)連通的前提下最節(jié)省經(jīng)費(fèi)?上述問題即要使得生成樹各邊權(quán)值之和，即：)(),()(T

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

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

28、最小生成樹CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點(diǎn)為主以選頂點(diǎn)為主DTDT6TTTB5ADB35ADB35C1ADB35C1E6另一最小生成樹 CADEBF圖G3718745561.普里姆普里姆( (prim)prim)算法 以選頂點(diǎn)為主以選頂點(diǎn)為主6CADEB316TF45Prim算法的關(guān)鍵 按照最小生成樹的性質(zhì)進(jìn)行頂點(diǎn)擴(kuò)張。 每擴(kuò)展一個(gè)頂點(diǎn)，在兩個(gè)頂點(diǎn)集合中都要更新當(dāng)前的最小邊。 以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)，時(shí)間復(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中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到TE中，否則選擇下一條代價(jià)最小的邊；（3）重復(fù)（2），直至所有頂點(diǎn)都在同一連通分量上為止。2、求解實(shí)例求下圖的最小生成樹：1235443532313612354最小生成樹不唯一，但權(quán)值之和相同。克魯斯卡爾（克魯斯卡爾（KruskaiKruskai) )算法，以選邊為主以選邊為主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ò)展一條邊，都需要判斷有無形成回路 以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)時(shí)，時(shí)間復(fù)雜度可以達(dá)到O（eloge)，與頂點(diǎn)數(shù)無關(guān)！二、 拓?fù)渑判蛲負(fù)渑判蛲負(fù)渑判?偏序關(guān)系的一個(gè)序列 拓?fù)渑判虻膽?yīng)用：選課次序 工程施工流程圖：AOV網(wǎng)（一）問題描述：（一）問題描述：由多項(xiàng)子工程（活動(dòng)）組成，子工程（活動(dòng)）之間存在制約關(guān)系。用圖表示工程，頂點(diǎn)表示子工程（活動(dòng)），弧表示活動(dòng)間的制約關(guān)系。(1)工程是否能順利完成？ 圖中是否存在回路？(2)工程需要多少時(shí)間完成？(3)哪些是關(guān)鍵性工程？（二）拓?fù)渑判蚍椒皩?shí)現(xiàn)（二）拓?fù)渑判蚍椒皩?shí)現(xiàn)(AOV(AOV網(wǎng)網(wǎng)) )1、如

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