第6章 圖

1、2024年3月21日,東華理工大學(xué)信工學(xué)院,主講：王強(qiáng),數(shù)據(jù)結(jié)構(gòu),2024年3月21日,東華理工大學(xué)信工學(xué)院,線性結(jié)構(gòu)——一個對一個，如線性表、棧、隊列,樹形結(jié)構(gòu)——一個對多個，如樹,集合——數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系,圖形結(jié)構(gòu)——多個對多個，如圖,邏輯結(jié)構(gòu),2024年3月21日,東華理工大學(xué)信工學(xué)院,第6章　圖,,6.1　圖的定義和基本術(shù)語6.2　圖的存儲結(jié)構(gòu)6.3　圖的遍歷6.4　圖的應(yīng)用,教學(xué)內(nèi)容,2024

2、年3月21日,東華理工大學(xué)信工學(xué)院,1.掌握：圖的基本概念及相關(guān)術(shù)語和性質(zhì)2.熟練掌握：圖的鄰接矩陣和鄰接表兩種存儲表示方法3.熟練掌握：圖的兩種遍歷方法DFS和BFS4.熟練掌握：最短路算法（Dijkstra算法）5.掌握：最小生成樹的兩種算法及拓?fù)渑判蛩惴ǖ乃枷?教學(xué)目標(biāo),2024年3月21日,東華理工大學(xué)信工學(xué)院,6.1 圖的定義和術(shù)語,,圖：Graph=(V,E) V：頂點(數(shù)據(jù)元素)的有窮非空集合； E：邊的有

3、窮集合。,無向圖：有向圖：,每條邊都是無方向的每條邊都是有方向的,2024年3月21日,東華理工大學(xué)信工學(xué)院,完全圖：任意兩個點都有一條邊相連,無向完全圖,有向完全圖,n(n-1)/2 條邊,n(n-1) 條邊,2024年3月21日,東華理工大學(xué)信工學(xué)院,稀疏圖：有很少邊或弧的圖。稠密圖：有較多邊或弧的圖。網(wǎng)：邊/弧帶權(quán)的圖。鄰接：有邊/弧相連的兩個頂點之間的關(guān)系。 存在(vi, vj)，則稱vi和vj

4、互為鄰接點； 存在，則稱vi鄰接到vj， vj鄰接于vi 關(guān)聯(lián)(依附)：邊/弧與頂點之間的關(guān)系。 存在(vi, vj)/ ， 則稱該邊/弧關(guān)聯(lián)于vi和vj,2024年3月21日,東華理工大學(xué)信工學(xué)院,頂點的度：與該頂點相關(guān)聯(lián)的邊的數(shù)目，記為TD(v),在有向圖中, 頂點的度等于該頂點的入度與出度之和。頂點 v 的入度是以 v 為終點的有向邊的條數(shù), 記作 ID(v) 頂點 v 的

5、出度是以 v 為始點的有向邊的條數(shù), 記作OD(v),問：當(dāng)有向圖中僅1個頂點的入度為0,其余頂點的入度均為1，此時是何形狀？,答：是樹！而且是一棵有向樹！,2024年3月21日,東華理工大學(xué)信工學(xué)院,路徑：接續(xù)的邊構(gòu)成的頂點序列。路徑長度：路徑上邊或弧的數(shù)目/權(quán)值之和?；芈?環(huán))：第一個頂點和最后一個頂點相同的路徑。簡單路徑：除路徑起點和終點可以相同外，其余頂點均不相同的路徑。簡單回路(簡單環(huán))：除路徑起點和終點相同外，其余頂

6、點均不相同的路徑。,2024年3月21日,東華理工大學(xué)信工學(xué)院,非連通圖,連通圖,強(qiáng)連通圖,非強(qiáng)連通圖,連通圖（強(qiáng)連通圖）,在無（有）向圖G=( V, {E} )中，若對任何兩個頂點 v、u 都存在從v 到 u 的路徑，則稱G是連通圖（強(qiáng)連通圖）。,2024年3月21日,東華理工大學(xué)信工學(xué)院,(a),(b),(c),子圖,設(shè)有兩個圖G=（V，{E}）、G1=（V1，{E1}），若V1? V，E1 ? E，則稱 G1是G的子圖。例:(

7、b)、(c) 是 (a) 的子圖,權(quán)與網(wǎng),圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個頂點到另一個頂點的距離或耗費。帶權(quán)的圖稱為網(wǎng)。,2024年3月21日,東華理工大學(xué)信工學(xué)院,連通分量（強(qiáng)連通分量）,非連通圖,,無向圖G 的極大連通子圖稱為G的連通分量。極大連通子圖意思是：該子圖是 G 連通子圖，將G 的任何不在該子圖中的頂點加入，子圖不再連通。,2024年3月21日,東華理工大學(xué)信工學(xué)院,有向圖G 的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量

8、。極大強(qiáng)連通子圖意思是：該子圖是G的強(qiáng)連通子圖，將D的任何不在該子圖中的頂點加入，子圖不再是強(qiáng)連通的。,2024年3月21日,東華理工大學(xué)信工學(xué)院,極小連通子圖：該子圖是G 的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。生成樹：包含無向圖G 所有頂點的極小連通子圖。生成森林：對非連通圖，由各個連通分量的生成樹的集合。,連通圖 G1,G1的生成樹,,2024年3月21日,東華理工大學(xué)信工學(xué)院,6.2 圖的存儲結(jié)構(gòu),,鄰接表鄰接多

9、重表十字鏈表,鏈?zhǔn)酱鎯Y(jié)構(gòu)：,順序存儲結(jié)構(gòu)：,數(shù)組表示法（鄰接矩陣）,多重鏈表,,重點介紹：,鄰接矩陣(數(shù)組)表示法鄰接表(鏈?zhǔn)?表示法,2024年3月21日,東華理工大學(xué)信工學(xué)院,建立一個頂點表（記錄各個頂點信息）和一個鄰接矩陣（表示各個頂點之間關(guān)系）。設(shè)圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組 A.Edge[n][n]，定義為：,數(shù)組（鄰接矩陣）表示法,2024年3月21日,東華理工大學(xué)信工學(xué)院,

10、鄰接矩陣：,,,A.Edge =,（ v1 v2 v3 v4 v5 ）,v1v2v3v4v5,0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0,分析1：無向圖的鄰接矩陣是對稱的；分析2：頂點i 的度＝第 i 行 (列) 中1 的個數(shù)；特別：完全圖的鄰接矩陣中，對角元素為0，其余1。,

11、0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0,0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0,頂點表：,無向圖的鄰接矩陣表示法,2024年3月21日,東華理工

12、大學(xué)信工學(xué)院,分析1：有向圖的鄰接矩陣可能是不對稱的。分析2：頂點的出度=第i行元素之和 頂點的入度=第i列元素之和 頂點的度=第i行元素之和+第i列元素之和,v1,v2,v3,v4,,,,,A,鄰接矩陣：,,,A.Edge =,( v1 v2 v3 v4 ),v1v2v3v4,0 0 0 00 0 0 0 0 0 0 0 0 0 0

13、 0,注：在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點vi為頭的弧(即入度邊）。,頂點表：,0 1 1 00 0 0 0 0 0 0 1 1 0 0 0,0 1 1 00 0 0 0 0 0 0 1 1 0 0 0,有向圖的鄰接矩陣表示法,

14、2024年3月21日,東華理工大學(xué)信工學(xué)院,定義為：,v1,v2,v3,v4,,,,,N,v5,v6,,,,,,,5,4,8,9,7,5,5,6,1,3,鄰接矩陣：,,,∞ ∞ ∞ ∞ ∞ ∞∞ ∞ ∞ ∞ ∞ ∞∞ ∞ ∞ ∞ ∞ ∞∞ ∞ ∞ ∞ ∞ ∞∞ ∞ ∞ ∞ ∞ ∞∞ ∞ ∞ ∞ ∞ ∞,N.Edge =,( v1 v2 v3 v4 v5 v6 ),頂點表：,5 7

15、 4 8 9 5 6 5 3 1,∞ 5 ∞ 7 ∞ ∞∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9∞ ∞ 5 ∞ ∞ 6∞

16、∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞,網(wǎng)（即有權(quán)圖）的鄰接矩陣表示法,2024年3月21日,東華理工大學(xué)信工學(xué)院,優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊、找頂點的鄰接點等等。,缺點：n個頂點需要n*n個單元存儲邊;空間效率為O(n2)。 對稀疏圖而言尤其浪費空間。,鄰接矩陣表示法的特點,2024年3月21日,東華理工大學(xué)信工學(xué)院,//用兩個數(shù)組分別存儲頂點表和鄰接矩陣#de

17、fine MaxInt 32767 //表示極大值，即∞#define MVNum 100 //最大頂點數(shù) typedef char VerTexType; //假設(shè)頂點的數(shù)據(jù)類型為字符型 typedef int ArcType; //假設(shè)邊的權(quán)值類型為整型 typedef str

18、uct{ VerTexType vexs[MVNum]; //頂點表 ArcType arcs[MVNum][MVNum]; //鄰接矩陣 int vexnum,arcnum; //圖的當(dāng)前點數(shù)和邊數(shù) }AMGraph;,鄰接矩陣的存儲表示,2024年3月21日,東華理工大學(xué)信工學(xué)院,（1）輸入總頂點數(shù)和總邊數(shù)。（2）依次輸入點的信息存入頂點

19、表中。（3）初始化鄰接矩陣，使每個權(quán)值初始化為極大值。（4）構(gòu)造鄰接矩陣。,【算法思想】,采用鄰接矩陣表示法創(chuàng)建無向網(wǎng),2024年3月21日,東華理工大學(xué)信工學(xué)院,Status CreateUDN(AMGraph &G){ //采用鄰接矩陣表示法，創(chuàng)建無向網(wǎng)G cin>>G.vexnum>>G.arcnum; //輸入總頂點數(shù)，總邊數(shù) for(i = 0; i>G

20、.vexs[i]; //依次輸入點的信息 for(i = 0; i>v1>>v2>>w; //輸入一條邊依附的頂點及權(quán)值 i = LocateVex(G, v1); j = LocateVex(G, v2); //確定v1和v2在G中的位置

21、 G.arcs[i][j] = w; //邊的權(quán)值置為w G.arcs[j][i] = G.arcs[i][j]; //置的對稱邊的權(quán)值為w }//for return OK; }//CreateUDN,【算法描述】,2024年3月21日,東華理工大學(xué)信工學(xué)院,int LocateVex(MGraph G,VertexType u) { /* 初始條件:圖G存在,u和G

22、中頂點有相同特征 */ /* 操作結(jié)果:若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1 */ int i; for(i=0;i<G.vexnum;++i) if(u==G.vexs[i]) return i; return -1; },2024年3月21日,東華理工大學(xué)信工學(xué)院,對每個頂點vi 建立一個單鏈表，把與vi有關(guān)聯(lián)的邊的信息鏈接起來，每個結(jié)點設(shè)為3個域；,每個單鏈

23、表有一個頭結(jié)點（設(shè)為2個域），存vi信息；,表結(jié)點,頭結(jié)點,鄰接點域，表示vi一個鄰接點的位置,鏈域，指向vi下一個邊或弧的結(jié)點,數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）,數(shù)據(jù)域，存儲頂點vi 信息,鏈域，指向單鏈表的第一個結(jié)點,,每個單鏈表的頭結(jié)點另外用順序存儲結(jié)構(gòu)存儲。,鄰接表（鏈?zhǔn)剑┍硎痉?2024年3月21日,東華理工大學(xué)信工學(xué)院,,,,,,,,,,,,,,,,,,,,,,,,,注：鄰接表不唯一，因各個邊結(jié)點的鏈入順序是任意的,無向圖的鄰

24、接表表示,空間效率為O(n+2e)。若是稀疏圖(e<<n2)，比鄰接矩陣表示法O(n2)省空間。,TD(Vi)=單鏈表中鏈接的結(jié)點個數(shù),2024年3月21日,東華理工大學(xué)信工學(xué)院,v1,v2,v3,v4,,,,,鄰接表(出邊),有向圖的鄰接表表示,空間效率為O(n+e),出度入度度：,OD(Vi)＝單鏈出邊表中鏈接的結(jié)點數(shù)ID(Vi)＝鄰接點域為Vi的弧個數(shù),TD(Vi) = OD( Vi ) + I D( Vi

25、 ),2024年3月21日,東華理工大學(xué)信工學(xué)院,,,,,80,,64,1,2,5,當(dāng)鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！,已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。,2024年3月21日,東華理工大學(xué)信工學(xué)院,#define MVNum 100 //最大頂點數(shù) typedef struct ArcNode{ //邊結(jié)點 int adjvex;

26、 //該邊所指向的頂點的位置 struct ArcNode * nextarc;   //指向下一條邊的指針 OtherInfo info; //和邊相關(guān)的信息 }ArcNode; typedef struct VNode{ VerTexType dat

27、a; //頂點信息 ArcNode * firstarc; //指向第一條依附該頂點的邊的指針 }VNode, AdjList[MVNum]; //AdjList表示鄰接表類型 typedef struct{ AdjList vertices; //鄰接表 int v

28、exnum, arcnum; //圖的當(dāng)前頂點數(shù)和邊數(shù) }ALGraph;,鄰接表的存儲表示,2024年3月21日,東華理工大學(xué)信工學(xué)院,（1）輸入總頂點數(shù)和總邊數(shù)。（2）依次輸入點的信息存入頂點表中，使每個表頭結(jié)點的指針域初始化為NULL。（3）創(chuàng)建鄰接表。,【算法思想】,采用鄰接表表示法創(chuàng)建無向網(wǎng),2024年3月21日,東華理工大學(xué)信工學(xué)院,Status CreateUDG(ALGraph &am

29、p;G){ 　　//采用鄰接表表示法，創(chuàng)建無向圖G 　 cin>>G.vexnum>>G.arcnum; //輸入總頂點數(shù)，總邊數(shù) for(i = 0; i> G.vertices[i].data; //輸入頂點值 G.vertices[i].firstarc=NULL; //初始化表頭結(jié)點的指針域為NULL

30、 }//for for(k = 0; k>v1>>v2; //輸入一條邊依附的兩個頂點 i = LocateVex(G, v1); j = LocateVex(G, v2); p1=new ArcNode; //生成一個新的邊結(jié)點*p1 　　 p1->adjvex=j;

31、 //鄰接點序號為j 　 　p1->nextarc= G.vertices[i].firstarc; G.vertices[i].firstarc=p1; //將新結(jié)點*p1插入頂點vi的邊表頭部 p2=new ArcNode; //生成另一個對稱的新的邊結(jié)點*p2 　　 p2->adjvex=i; //鄰接點序號

32、為i 　 　p2->nextarc= G.vertices[j].firstarc; G.vertices[j].firstarc=p2; //將新結(jié)點*p2插入頂點vj的邊表頭部 }//for return OK; }//CreateUDG,【算法描述】,2024年3月21日,東華理工大學(xué)信工學(xué)院,優(yōu)點：空間效率高，容易尋找頂點的鄰接點；,缺點：判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對

33、應(yīng)的單鏈表，沒有鄰接矩陣方便。,鄰接表表示法的特點,2024年3月21日,東華理工大學(xué)信工學(xué)院,鄰接矩陣與鄰接表表示法的關(guān)系,1. 聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。,2024年3月21日,東華理工大學(xué)信工學(xué)院,2. 區(qū)別：① 對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。② 鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空

34、間復(fù)雜度為O(n+e)。3. 用途：鄰接矩陣多用于稠密圖；而鄰接表多用于稀疏圖,鄰接矩陣與鄰接表表示法的關(guān)系,2024年3月21日,東華理工大學(xué)信工學(xué)院,遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。,遍歷實質(zhì)：找每個頂點的鄰接點的過程。圖的特點：圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)

35、訪問過的頂點。,6.3 圖的遍歷,,2024年3月21日,東華理工大學(xué)信工學(xué)院,圖常用的遍歷：深度優(yōu)先搜索廣度優(yōu)先搜索,解決思路：設(shè)置輔助數(shù)組 visited [n ]，用來標(biāo)記每個被訪問過的頂點。初始狀態(tài)為0i 被訪問，改 visited [i]為1，防止被多次訪問,怎樣避免重復(fù)訪問？,2024年3月21日,東華理工大學(xué)信工學(xué)院,基本思想：——仿樹的先序遍歷過程。,v1,DFS 結(jié)果,→,→,→,→,→,→,→,v2,v4,v

36、8,v5,v3,v6,v7,,起點,,深度優(yōu)先搜索( DFS － Depth_First Search),2024年3月21日,東華理工大學(xué)信工學(xué)院,深度優(yōu)先搜索的步驟,簡單歸納：訪問起始點v;若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點；若當(dāng)前鄰接點已訪問過，再找v的第2個鄰接點重新遍歷。,2024年3月21日,東華理工大學(xué)信工學(xué)院,深度優(yōu)先搜索的步驟,詳細(xì)歸納：在訪問圖中某一起始頂點 v 后，由 v 出發(fā)，訪問它的任一鄰接頂

37、點 w1；再從 w1 出發(fā)，訪問與 w1鄰接但還未被訪問過的頂點 w2；然后再從 w2 出發(fā)，進(jìn)行類似的訪問，… 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點都被訪問過的頂點 u 為止。,起點,,2024年3月21日,東華理工大學(xué)信工學(xué)院,深度優(yōu)先搜索的步驟,詳細(xì)歸納：接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。 如果有，則訪問此頂點，之后再從此頂點出發(fā)，進(jìn)行與前述類似的訪問； 如果沒有

38、，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。,起點,v2→v1→v3→v5→v4→v6,2024年3月21日,東華理工大學(xué)信工學(xué)院,,討論1：計算機(jī)如何實現(xiàn)DFS？,DFS 結(jié)果,鄰接矩陣A,輔助數(shù)組 visited [n ],起點,v2→v1→v3→v5→v4→v6,——開輔助數(shù)組 visited [n ]！,,,,,,,,,,,,2024年3月21日,東華理工大學(xué)信工學(xué)院,void DFS(AMGra

39、ph G, int v){ //圖G為鄰接矩陣類型 cout<<v; visited[v] = true; //訪問第v個頂點 for(w = 0; w< G.vexnum; w++) //依次檢查鄰接矩陣v所在的行 if((G.arcs[v][w]!=0)&& (!visited[w])) DFS(G, w); //w是v的鄰

40、接點，如果w未訪問，則遞歸調(diào)用DFS },討論2：DFS算法如何編程？,——可以用遞歸算法！,2024年3月21日,東華理工大學(xué)信工學(xué)院,,,討論3：在圖的鄰接表中如何進(jìn)行DFS？,v0 → v1 → v2 → v3,DFS 結(jié)果,輔助數(shù)組 visited [n ],—照樣借用visited [n ]！,起點,0123,,,,,,,,,,,,,2024年3月21日,東華理工大學(xué)信工學(xué)院,,討論4：鄰接表的DFS算法如何編程？,v

41、oid DFS(ALGraph G, int v){ //圖G為鄰接表類型 coutadjvex; //表示w是v的鄰接點 if(!visited[w]) DFS(G, w); //如果w未訪問，則遞歸調(diào)用DFS p=p->nextarc; //p指向下一個邊結(jié)點 } },——仍可用遞歸算法,2024年3月21日,東華理工大

42、學(xué)信工學(xué)院,用鄰接矩陣來表示圖，遍歷圖中每一個頂點都要從頭掃描該頂點所在行，時間復(fù)雜度為O(n2)。用鄰接表來表示圖，雖然有 2e 個表結(jié)點，但只需掃描 e 個結(jié)點即可完成遍歷，加上訪問 n個頭結(jié)點的時間，時間復(fù)雜度為O(n+e)。,結(jié)論：稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷；稀疏圖適于在鄰接表上進(jìn)行深度遍歷。,DFS算法效率分析,2024年3月21日,東華理工大學(xué)信工學(xué)院,基本思想：——仿樹的層次遍歷過程,廣度優(yōu)先搜索( BFS

43、－ Breadth_First Search),v1,BFS 結(jié)果,→,→,→,起點,2024年3月21日,東華理工大學(xué)信工學(xué)院,簡單歸納：在訪問了起始點v之后，依次訪問 v的鄰接點；然后再依次訪問這些頂點中未被訪問過的鄰接點；直到所有頂點都被訪問過為止。,廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。,廣度優(yōu)先搜索的步

44、驟,2024年3月21日,東華理工大學(xué)信工學(xué)院,,,討論1：計算機(jī)如何實現(xiàn)BFS？,鄰接表,—除輔助數(shù)組visited [n ]外，還需再開一輔助隊列,起點,輔助隊列,v2已訪問過了,BFS 遍歷結(jié)果,,入隊！,初始f=n-1,r=0,,,,2024年3月21日,東華理工大學(xué)信工學(xué)院,（1）從圖中某個頂點v出發(fā)，訪問v，并置visited[v]的值為true，然后將v進(jìn)隊。（2）只要隊列不空，則重復(fù)下述處理。 ① 隊頭頂點u出隊

45、。 ② 依次檢查u的所有鄰接點w，如果visited[w]的值為false，則訪問w，并置visited[w]的值為true，然后將w進(jìn)隊。,【算法思想】,2024年3月21日,東華理工大學(xué)信工學(xué)院,void BFS (Graph G, int v){ //按廣度優(yōu)先非遞歸遍歷連通圖G cout=0; w = NextAdjVex(G, u, w)) if(!visited[w]){

46、 //w為u的尚未訪問的鄰接頂點 cout<<w; visited[w] = true;EnQueue(Q, w); //w進(jìn)隊 }//if }//while }//BFS,【算法描述】,2024年3月21日,東華理工大學(xué)信工學(xué)院,如果使用鄰接矩陣，則BFS對于每一個被訪問到的頂點，都要循環(huán)檢測矩陣中的整整一行（ n 個元素），總的時間代價為O

47、(n2)。用鄰接表來表示圖，雖然有 2e 個表結(jié)點，但只需掃描 e 個結(jié)點即可完成遍歷，加上訪問 n個頭結(jié)點的時間，時間復(fù)雜度為O(n+e)。,BFS算法效率分析,2024年3月21日,東華理工大學(xué)信工學(xué)院,空間復(fù)雜度相同，都是O(n)(借用了堆?；蜿犃校粫r間復(fù)雜度只與存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無關(guān)。,DFS與BFS算法效率比較,2024年3月21日,東華理工大學(xué)信工學(xué)院,最小生成樹最短路徑拓?fù)渑判蜿P(guān)鍵

48、路徑,6.4 圖的應(yīng)用,,2024年3月21日,東華理工大學(xué)信工學(xué)院,極小連通子圖：該子圖是G 的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。生成樹：包含圖G所有頂點的極小連通子圖（n-1條邊）。,最小生成樹,2024年3月21日,東華理工大學(xué)信工學(xué)院,DFS生成樹,鄰接表,v0,v2,v1,v4,,v3,,,,,BFS生成樹,v0,無向連通圖,畫出下圖的生成樹,2024年3月21日,東華理工大學(xué)信工學(xué)院,求最小生成樹,首先明確

49、：使用不同的遍歷圖的方法，可以得到不同的生成樹從不同的頂點出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n 個頂點的連通網(wǎng)絡(luò)的生成樹有 n 個頂點、n-1 條邊。,目標(biāo)：在網(wǎng)的多個生成樹中，尋找一個各邊權(quán)值之和最小的生成樹,2024年3月21日,東華理工大學(xué)信工學(xué)院,必須只使用該網(wǎng)中的邊來構(gòu)造最小生成樹；必須使用且僅使用n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個頂點不能使用產(chǎn)生回路的邊,構(gòu)造最小生成樹的準(zhǔn)則,2024年3月21日,東華理

50、工大學(xué)信工學(xué)院,欲在n個城市間建立通信網(wǎng)，則n個城市應(yīng)鋪n-1條線路；但因為每條線路都會有對應(yīng)的經(jīng)濟(jì)成本，而n個城市可能有n(n-1)/2 條線路，那么，如何選擇n–1條線路，使總費用最少？,數(shù)學(xué)模型：頂點———表示城市，有n個；邊————表示線路，有n–1條；邊的權(quán)值—表示線路的經(jīng)濟(jì)代價；連通網(wǎng)——表示n個城市間通信網(wǎng)。,顯然此連通網(wǎng)是一個生成樹！,最小生成樹的典型用途,2024年3月21日,東華理工大學(xué)信工學(xué)院,Prim（普

51、里姆）算法 Kruskal（克魯斯卡爾）算法,Prime算法: 歸并頂點，與邊數(shù)無關(guān)，適于稠密網(wǎng)Kruskal算法：歸并邊，適于稀疏網(wǎng),如何求最小生成樹,2024年3月21日,東華理工大學(xué)信工學(xué)院,設(shè)連通網(wǎng)絡(luò) N = { V, E }1. 從某頂點 u0 出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0, v)，將其頂點加入到生成樹的頂點集合U中2. 每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權(quán)值最小的邊(u, v),

52、把它的頂點加入到U中3. 直到所有頂點都加入到生成樹頂點集合U中為止,普里姆算法的基本思想－－歸并頂點,2024年3月21日,東華理工大學(xué)信工學(xué)院,應(yīng)用普里姆算法構(gòu)造最小生成樹的過程,2024年3月21日,東華理工大學(xué)信工學(xué)院,設(shè)連通網(wǎng)絡(luò) N = { V, E }1. 構(gòu)造一個只有 n 個頂點，沒有邊的非連通圖 T = { V, ? }, 每個頂點自成一個連通分量2. 在 E 中選最小權(quán)值的邊,若該邊的兩個頂點落在不同的連通分量上

53、，則加入 T 中；否則舍去，重新選擇3. 重復(fù)下去，直到所有頂點在同一連通分量上為止,克魯斯卡爾算法的基本思想－歸并邊,2024年3月21日,東華理工大學(xué)信工學(xué)院,應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程,,,,,,,√,√,√,√,×,√,×,√,,2024年3月21日,東華理工大學(xué)信工學(xué)院,用有向圖來描述一個工程或系統(tǒng)的進(jìn)行過程。一個工程可以分為若干個子工程，只要完成了這些子工程（活動），就可以導(dǎo)致整個工程的完

54、成。,① AOV網(wǎng)(Activity On Vertices)—用頂點表示活動的網(wǎng)絡(luò)② AOE網(wǎng)(Activity On Edges)—用邊表示活動的網(wǎng)絡(luò),比如教學(xué)計劃的制定哪些課程是必須先修的，哪些課程是可以并行學(xué)習(xí)的。,有向無環(huán)圖及其應(yīng)用,2024年3月21日,東華理工大學(xué)信工學(xué)院,C1 高等數(shù)學(xué) C2 程序設(shè)計基礎(chǔ) C3

55、 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級語言程序設(shè)計 C2 C6 編譯方法 C5, C4 C

56、7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計算機(jī)原理 C8,課程代號,課程名稱,先修課程,,,,2024年3月21日,東華理工大學(xué)信工學(xué)院,學(xué)生課程學(xué)習(xí)工程圖,數(shù)據(jù)結(jié)構(gòu),離散數(shù)

57、學(xué),程序設(shè)計基礎(chǔ),對學(xué)生選課工程圖進(jìn)行拓?fù)渑判?，得到的拓?fù)溆行蛐蛄袨镃1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6,2024年3月21日,東華理工大學(xué)信工學(xué)院,輸入AOV網(wǎng)絡(luò)。令 n 為頂點個數(shù)。 在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點, 并輸出之; 從圖中刪去該頂點, 同時刪去所有它發(fā)出的

58、有向邊; 重復(fù)以上 2、3 步, 直到：全部頂點均已輸出，拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛲瓿?；或：圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了。這時AOV網(wǎng)絡(luò)中必定存在有向環(huán)。,拓?fù)渑判蛩惴ǖ乃枷耄貜?fù)選擇沒有直接前驅(qū)的頂點,2024年3月21日,東華理工大學(xué)信工學(xué)院,拓?fù)渑判虻倪^程,2024年3月21日,東華理工大學(xué)信工學(xué)院,最后得到拓?fù)湫蛄?C4 , C0 , C3

59、 , C2 , C1 , C5 。滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點，如C4和C2，也排出了先后次序關(guān)系。,2024年3月21日,東華理工大學(xué)信工學(xué)院,典型用途：交通問題。如：城市A到城市B有多條線路，但每條線路的交通費（或所需時間）不同，那么，如何選擇一條線路，使總費用（或總時間）最少？問題抽象：在帶權(quán)有向圖中A點（源點）到達(dá)B點（終點）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。,（注：最短

60、路徑與最小生成樹不同，路徑上不一定包含n個頂點）,最短路徑,2024年3月21日,東華理工大學(xué)信工學(xué)院,一頂點到其余各頂點,兩種常見的最短路徑問題：一、 單源最短路徑—用Dijkstra（迪杰斯特拉）算法二、所有頂點間的最短路徑—用Floyd（弗洛伊德）算法,任意兩頂點之間,2024年3月21日,東華理工大學(xué)信工學(xué)院,目的： 設(shè)一有向圖G=（V, E），已知各邊的權(quán)值，以某指定點v0為源點，求從v0到圖的其余各點的最短路徑。限定各邊

61、上的權(quán)值大于或等于0。,源點,從F→A的路徑有4條：① F→A： 24② F→B→A： 5＋18=23③ F→B→C→A：5+7+9=21④ F→D→C→A：25+12+9=36,又：從F→B的最短路徑是哪條？從F→C的最短路徑是哪條？,,單源最短路徑問題（Dijkstra算法）,2024年3月21日,東華理工大學(xué)信工學(xué)院,10,30,100,,例2：,,60,01234,50,90,70,討論：計算機(jī)

62、如何自動求出這些最短路徑？,,60,2024年3月21日,東華理工大學(xué)信工學(xué)院,先找出從源點v0到各終點vk的直達(dá)路徑（v0,vk），即通過一條弧到達(dá)的路徑。從這些路徑中找出一條長度最短的路徑（v0,u）,然后對其余各條路徑進(jìn)行適當(dāng)調(diào)整：若在圖中存在?。╱,vk），且（v0,u）+（u,vk）<（v0,vk）,則以路徑（v0,u,vk）代替（v0,vk）。在調(diào)整后的各條路徑中，再找長度最短的路徑，依此類推。,Dijkstr

63、a算法的思想,2024年3月21日,東華理工大學(xué)信工學(xué)院,① 初始化：●將源點v0加到S中，即S[v0] = true；●將v0到各個終點的最短路徑長度初始化為權(quán)值，即D[i] = G.arcs[v0][vi]，(vi∈V ? S)；●如果v0和頂點vi之間有弧，則將vi的前驅(qū)置為v0，即Path[i] = v0，否則Path[i] =

64、 ?1。② 選擇下一條最短路徑的終點vk，使得：D[k] = Min{D[i]|vi∈V ? S},【算法思想】,2024年3月21日,東華理工大學(xué)信工學(xué)院,③ 將vk加到S中，即S[vk] = true。④ 更新從v0出發(fā)到集合V ? S上任一頂點的最短路徑的長度，同時更改vi的前驅(qū)為vk。若D[k]+G.arcs[k][i]<D

65、[i]，則D[i]=D[k]+ G.arcs[k][i]; Path [i]=k;。 ⑤ 重復(fù)②～④ n ? 1次，即可按照路徑長度的遞增順序，逐個求得從v0到圖上其余各頂點的最短路徑。,【算法思想】,2024年3月21日,東華理工大學(xué)信工學(xué)院,2024年3月21日,東華理工大學(xué)信工學(xué)院,,(v0,v2)+ (v2,v3)<(v0,v3),S之外的當(dāng)前最短路徑之頂點,{v0,v2},{v0 ,v2

66、,v4},{v0 ,v2 ,v4 ,v3},{v0 ,v2 ,v4 ,v3 ,v5},∞,∞,∞,,,,,,,,例,,v2,,v4,,,v3,,v5,012345,D[w],0 1 2 3 4 5,10{v0,v2},50{v0,v4,v3},30{v0,v4},2024年3月21日,東華理工大學(xué)信工學(xué)院,,更新v0 到V- S 中頂點的Dist,求最短路徑長度Dist,算法流

67、程圖,2024年3月21日,東華理工大學(xué)信工學(xué)院,void ShortestPath_DIJ(AMGraph G, int v0){ //用Dijkstra算法求有向網(wǎng)G的v0頂點到其余頂點的最短路徑 n=G.vexnum; //n為G中頂點的個數(shù) for(v = 0; v<n; ++v){ //n個頂點依次初始化 S

68、[v] = false; //S初始為空集 D[v] = G.arcs[v0][v]; //將v0到各個終點的最短路徑長度初始化 if(D[v]< MaxInt) Path [v]=v0; //v0和v之間有弧，將v的前驅(qū)置為v0 else Path [v]=-1; //如果v0和v之間無弧，則

69、將v的前驅(qū)置為-1 }//for S[v0]=true; //將v0加入S D[v0]=0; //源點到源點的距離為0,【算法描述】,2024年3月21日,東華理工大學(xué)信工學(xué)院,時間復(fù)雜度：O(n2),/*―開始主循環(huán)，每次求得v0到某個頂點v的最短路徑，將v加到S集―*/ for(i=1;i&l

70、t;n; ++i){ //對其余n?1個頂點，依次進(jìn)行計算 min= MaxInt; for(w=0;w<n; ++w) if(!S[w]&&D[w]<min) {v=w; min=D[w];} //選擇一條當(dāng)前的最短路徑，終點為v S[v]=true;

71、 //將v加入S for(w=0;w<n; ++w) //更新從v0出發(fā)到集合V?S上所有頂點的最短路徑長度 if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){ D[w]=D[v]+G.arcs[v][w]; //更新D[w] Path [w]=v;