2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題(含答案詳解+作文范文)_第1頁(yè)
已閱讀1頁(yè),還剩82頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

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

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

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

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

6、點(diǎn)均不相同的路徑。,2024年3月21日,東華理工大學(xué)信工學(xué)院,非連通圖,連通圖,強(qiáng)連通圖,非強(qiáng)連通圖,連通圖(強(qiáng)連通圖),在無(wú)(有)向圖G=( V, {E} )中,若對(duì)任何兩個(gè)頂點(diǎn) v、u 都存在從v 到 u 的路徑,則稱G是連通圖(強(qiáng)連通圖)。,2024年3月21日,東華理工大學(xué)信工學(xué)院,(a),(b),(c),子圖,設(shè)有兩個(gè)圖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)。表明從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。帶權(quán)的圖稱為網(wǎng)。,2024年3月21日,東華理工大學(xué)信工學(xué)院,連通分量(強(qiáng)連通分量),非連通圖,,無(wú)向圖G 的極大連通子圖稱為G的連通分量。極大連通子圖意思是:該子圖是 G 連通子圖,將G 的任何不在該子圖中的頂點(diǎn)加入,子圖不再連通。,2024年3月21日,東華理工大學(xué)信工學(xué)院,有向圖G 的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量

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

9、重表十字鏈表,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):,順序存儲(chǔ)結(jié)構(gòu):,數(shù)組表示法(鄰接矩陣),多重鏈表,,重點(diǎn)介紹:,鄰接矩陣(數(shù)組)表示法鄰接表(鏈?zhǔn)?表示法,2024年3月21日,東華理工大學(xué)信工學(xué)院,建立一個(gè)頂點(diǎn)表(記錄各個(gè)頂點(diǎn)信息)和一個(gè)鄰接矩陣(表示各個(gè)頂點(diǎn)之間關(guān)系)。設(shè)圖 A = (V, E) 有 n 個(gè)頂點(diǎn),則圖的鄰接矩陣是一個(gè)二維數(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:無(wú)向圖的鄰接矩陣是對(duì)稱的;分析2:頂點(diǎn)i 的度=第 i 行 (列) 中1 的個(gè)數(shù);特別:完全圖的鄰接矩陣中,對(duì)角元素為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,頂點(diǎn)表:,無(wú)向圖的鄰接矩陣表示法,2024年3月21日,東華理工

12、大學(xué)信工學(xué)院,分析1:有向圖的鄰接矩陣可能是不對(duì)稱的。分析2:頂點(diǎn)的出度=第i行元素之和 頂點(diǎn)的入度=第i列元素之和 頂點(diǎn)的度=第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é)點(diǎn)vi為尾的弧(即出度邊); 第i列含義:以結(jié)點(diǎn)vi為頭的弧(即入度邊)。,頂點(diǎn)表:,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 ),頂點(diǎn)表:,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)點(diǎn):容易實(shí)現(xiàn)圖的操作,如:求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊、找頂點(diǎn)的鄰接點(diǎn)等等。,缺點(diǎn):n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊;空間效率為O(n2)。 對(duì)稀疏圖而言尤其浪費(fèi)空間。,鄰接矩陣表示法的特點(diǎn),2024年3月21日,東華理工大學(xué)信工學(xué)院,//用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#de

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

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

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

20、.vexs[i]; //依次輸入點(diǎn)的信息 for(i = 0; i>v1>>v2>>w; //輸入一條邊依附的頂點(diǎn)及權(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]; //置的對(duì)稱邊的權(quán)值為w }//for return OK; }//CreateUDN,【算法描述】,2024年3月21日,東華理工大學(xué)信工學(xué)院,int LocateVex(MGraph G,VertexType u) { /* 初始條件:圖G存在,u和G

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40、接點(diǎn),如果w未訪問(wèn),則遞歸調(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 ]!,起點(diǎn),0123,,,,,,,,,,,,,2024年3月21日,東華理工大學(xué)信工學(xué)院,,討論4:鄰接表的DFS算法如何編程?,v

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

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

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

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

45、。 ② 依次檢查u的所有鄰接點(diǎn)w,如果visited[w]的值為false,則訪問(wèn)w,并置visited[w]的值為true,然后將w進(jìn)隊(duì)。,【算法思想】,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的尚未訪問(wèn)的鄰接頂點(diǎn) cout<<w; visited[w] = true;EnQueue(Q, w); //w進(jìn)隊(duì) }//if }//while }//BFS,【算法描述】,2024年3月21日,東華理工大學(xué)信工學(xué)院,如果使用鄰接矩陣,則BFS對(duì)于每一個(gè)被訪問(wèn)到的頂點(diǎn),都要循環(huán)檢測(cè)矩陣中的整整一行( n 個(gè)元素),總的時(shí)間代價(jià)為O

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

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

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

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

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

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

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

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

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

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

57、學(xué),程序設(shè)計(jì)基礎(chǔ),對(duì)學(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 為頂點(diǎn)個(gè)數(shù)。 在AOV網(wǎng)絡(luò)中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn), 并輸出之; 從圖中刪去該頂點(diǎn), 同時(shí)刪去所有它發(fā)出的

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

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

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

61、上的權(quán)值大于或等于0。,源點(diǎn),從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的最短路徑是哪條?,,單源最短路徑問(wèn)題(Dijkstra算法),2024年3月21日,東華理工大學(xué)信工學(xué)院,10,30,100,,例2:,,60,01234,50,90,70,討論:計(jì)算機(jī)

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

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

64、 ?1。② 選擇下一條最短路徑的終點(diǎn)vk,使得:D[k] = Min{D[i]|vi∈V ? S},【算法思想】,2024年3月21日,東華理工大學(xué)信工學(xué)院,③ 將vk加到S中,即S[vk] = true。④ 更新從v0出發(fā)到集合V ? S上任一頂點(diǎn)的最短路徑的長(zhǎng)度,同時(shí)更改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次,即可按照路徑長(zhǎng)度的遞增順序,逐個(gè)求得從v0到圖上其余各頂點(diǎn)的最短路徑。,【算法思想】,2024年3月21日,東華理工大學(xué)信工學(xué)院,2024年3月21日,東華理工大學(xué)信工學(xué)院,,(v0,v2)+ (v2,v3)<(v0,v3),S之外的當(dāng)前最短路徑之頂點(diǎn),{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 中頂點(diǎn)的Dist,求最短路徑長(zhǎng)度Dist,算法流

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論