數(shù)據(jù)結(jié)構(gòu)圖PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)圖數(shù)據(jù)結(jié)構(gòu)圖2哥尼斯堡七橋問題 德國古城哥尼斯堡普雷格爾河七橋問題：從任一橋頭出發(fā)，依次走過每座橋，每座橋只走一次，最后回到出發(fā)點(diǎn)。 一筆畫問題第1頁/共104頁3第2頁/共104頁4第3頁/共104頁5第4頁/共104頁6 其中：V 是G 的頂點(diǎn)集合，是有窮非空集； E 是G 的邊集合，是有窮集。問：當(dāng)E(G)為空時(shí)，圖G存在否？答：還存在！但此時(shí)圖G只有頂點(diǎn)而沒有邊。有向圖：無向圖：完全圖：圖G中的每條邊都是有方向的；圖G中的每條邊都是無方向的；圖G任意兩個(gè)頂點(diǎn)都有一條邊相連接；v若 n 個(gè)頂點(diǎn)的無向圖有 n(n-1)/2 條邊, 稱為無向完全圖v若 n 個(gè)頂點(diǎn)的有向圖有n

2、(n-1) 條邊, 稱為有向完全圖V=vertex E=edge圖：記為 G( V, E )v1v2v3v5v4v4v1v2v3v4有向邊(u, v)稱為弧，邊的始點(diǎn)u 叫弧尾，終點(diǎn)v 叫弧頭。第5頁/共104頁7無向無向圖(樹)有向圖有向G1的頂點(diǎn)集合為V(G1)=0,1,2,3邊集合為E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全圖完全圖第6頁/共104頁8證明：若是完全有向圖，則n個(gè)頂點(diǎn)中的每個(gè)頂點(diǎn)都有一條弧指向其它n-1個(gè)頂點(diǎn), 因此總邊數(shù)=n(n-1)證明：從可以直接推論出無向完全圖的邊數(shù)因?yàn)闊o方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為n(n

3、-1)/2。12341234第7頁/共104頁9設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。若 V V 且 E E, 則稱 圖G 是 圖G 的子圖。子 圖：邊較少的圖。通常邊數(shù)遠(yuǎn)少于邊很多的圖。無向圖中，邊數(shù)接近有向圖中，邊數(shù)接近第8頁/共104頁10即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義的數(shù)值（即與邊相關(guān)的數(shù)）。連通圖：在無向圖中, 若從頂點(diǎn)v1到頂點(diǎn)v2有路徑, 則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。帶權(quán)圖在有向圖中, 若對(duì)于每一對(duì)頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的路徑,

4、則稱此圖是強(qiáng)連通圖。強(qiáng)連通圖：網(wǎng) ：DEABCFJLMGHIK非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。第9頁/共104頁11生成樹：有兩類圖形不在本章討論之列：v1v2v3v4v如果在生成樹上添加1條邊，必定構(gòu)成一個(gè)環(huán)。v若圖中有n個(gè)頂點(diǎn)，卻少于n-1條邊，必為非連通圖。生成森林：第10頁/共104頁12有向邊(u, v)稱為弧，邊的始點(diǎn)u 叫弧尾，終點(diǎn)v 叫弧頭。頂點(diǎn) v 的入度是以 v 為終點(diǎn)的有向邊的條數(shù), 記作 ID(v); 頂點(diǎn) v 的出度是以 v 為始點(diǎn)的有向邊的條數(shù), 記作 OD(v)。若 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點(diǎn)?；☆^和弧尾：入度

5、和出度：?jiǎn)枺寒?dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何形狀？uv度：頂點(diǎn)v 的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中, 頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。答：是樹！而且是一棵有向樹！第11頁/共104頁13路徑上各頂點(diǎn) v1,v2,.,vm 均不互相重復(fù)?；芈罚?若路徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂點(diǎn)vm 重合，則稱這樣的路徑為回路或環(huán)。路徑：路徑長(zhǎng)度：圖的術(shù)語（續(xù)）第12頁/共104頁14ADT Graph 數(shù)據(jù)對(duì)象V：數(shù)據(jù)關(guān)系 R：基本操作P：ADT Graph V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。R=VR；VR=|v,wV 且 P(v,w)

6、, 表示從v到w的弧， 謂詞P(v,w)定義了弧的意義或信息CreatGraph ( &G, V,VR); 初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。 操作結(jié)果：按V和VR的定義構(gòu)造圖G。注意：V 的大小寫含義不同！InsertVex ( &G, v); 初始條件：圖G存在，v 和圖中頂點(diǎn)有相同特征。 操作結(jié)果：在圖G中添加新頂點(diǎn)。 （參見教材P156-257）第13頁/共104頁15鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)： 難！（多個(gè)頂點(diǎn)，無序可言，無法僅以頂點(diǎn)坐標(biāo)表達(dá)相互關(guān)系）可用多重鏈表但可用數(shù)組描述元素間關(guān)系。非線性結(jié)構(gòu)（m :n）鄰接矩陣鄰接表十字鏈表鄰接多重表各種表示法成立

7、的原則：存入電腦后能惟一復(fù)原第14頁/共104頁16 , ),( , ,.否否則則或或者者如如果果01AEjiEjijiEdge鄰接矩陣：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0頂點(diǎn)表：無向圖的鄰接矩陣如何表示？v1v2v3v5v4v4記錄各個(gè)頂點(diǎn)信息表示各個(gè)頂點(diǎn)之間關(guān)系0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0第15頁/共104頁17有

8、向圖的鄰接矩陣可能是不對(duì)稱的。頂點(diǎn)vi的出度=第i行元素之和，OD(vi )= A.Edge i j 頂點(diǎn)vi的入度=第i列元素之和。ID(vi )= A.Edge j i 頂點(diǎn)的度=第i行元素之和+第i列元素之和, 即：TD( vi ) = OD( vi ) + ID( vi )v1v2v3v4鄰接矩陣：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點(diǎn)vi為頭的弧(即入度邊）。頂點(diǎn)表：0 1 1 00 0 0 0 0 0 0 1

9、1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 第16頁/共104頁18 容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。 n個(gè)頂點(diǎn)需要個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n )。定義：A.Edge i j =Wij 或（vi, vj）VR 無邊（?。﹙1v2v3v4Nv5v65489755613以有向網(wǎng)為例：鄰接矩陣： N.Edge =( v1 v2 v3 v4 v5 v6 )鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：頂點(diǎn)表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 v1v2v3v4v5v6對(duì)稀疏圖

10、而言尤其浪費(fèi)空間。第17頁/共104頁19注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù)Typedef enum DG, DN, AG, AN GraphKind; /有向/無向圖，有向/無向網(wǎng)對(duì)于n個(gè)頂點(diǎn)的圖或網(wǎng)，空間效率=O(n2)Typedef struct ArcCell /?。ㄟ叄┙Y(jié)點(diǎn)的定義 VRType adj; /頂點(diǎn)間關(guān)系，無權(quán)圖取1或0；有權(quán)圖取權(quán)值類型 InfoType *info; /該弧相關(guān)信息的指針ArcCell, AdjMatrix MAX_VER

11、TEX_NUM MAX_VERTEX_NUM ;Typedef struct /圖的定義VertexType vexs MAX_VERTEX_NUM ; /頂點(diǎn)表，用一維向量即可(n)AdjMatrix arcs; /鄰接矩陣n*nInt Vernum, arcnum; /頂點(diǎn)總數(shù)n，?。ㄟ叄┛倲?shù)eGraphKind kind; /圖的種類標(biāo)志Mgraph; 第18頁/共104頁20Status CreateUDN(Mgraph &G) /無向網(wǎng)的構(gòu)造，用鄰接矩陣表示scanf(&G.vexnum, &G.arcnum, &IncInfo); /輸入總頂點(diǎn)數(shù)n、

12、總弧數(shù)e和信息for(i=0;iG.vexnum,;+i) scanf(&G.vexsi );/輸入n個(gè)頂點(diǎn)值，存入一維向量對(duì)于n個(gè)頂點(diǎn)e條弧的網(wǎng)，建網(wǎng)時(shí)間效率 = O(n+n2+e*n)for(i=0; iG.vexnum; +i) /對(duì)鄰接矩陣n*n個(gè)單元初始化，adj=,info=NULLfor(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL; for(k=0;knum;+k) /給鄰接矩陣有關(guān)單元賦初值(循環(huán)次數(shù)弧數(shù)e scanf(&v1, &v2, &w); /輸入弧的兩頂點(diǎn)以及對(duì)應(yīng)權(quán)值 i=LocateVex(G,

13、v1); j=LocateVex(G,v2); /找到兩頂點(diǎn)在矩陣中的位置(n次) G.arcsij.adj=w; /輸入對(duì)應(yīng)權(quán)值 If(IncInfo) Input(*G.); /如果弧有信息則填入 G.arcsij = G.arcs j i； /無向網(wǎng)是對(duì)稱矩陣 return OK; / CreateUDN 第19頁/共104頁21adjvex nextarcinfodatafirstarc鄰接點(diǎn)域，表示vi 鄰接點(diǎn)的位置鏈域，指向下一個(gè)邊或弧的結(jié)點(diǎn)數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi 信息鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn)第20頁/共104頁22v1v2v3

14、v5v4v4鄰接表0123413341420例2：有向圖的鄰接表如何表示？v1v2v3v4V4V3V2V12301鄰接表(出邊)V4V3V2V13020逆鄰接表(入邊)請(qǐng)注意：鄰接表不惟一！因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。v1v2v3v4v5231420v1鄰接點(diǎn)v4的位置此無權(quán)圖未開第3分量第21頁/共104頁238064125當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！第22頁/共104頁24分析1: 對(duì)于n個(gè)頂點(diǎn)e條邊的無向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有2e個(gè)表結(jié)點(diǎn),空間效率為O(n+2e)。若是稀疏圖(en2)，則比鄰接矩陣表示法O(n2)省空間。分析2:在有向圖中，鄰接表中除了n個(gè)頭

15、結(jié)點(diǎn)外，只有e個(gè)表結(jié)點(diǎn),空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。它其實(shí)是對(duì)鄰接矩陣法的一種改進(jìn)怎樣計(jì)算無向圖頂點(diǎn)的度？鄰接表的缺點(diǎn)：怎樣計(jì)算有向圖頂點(diǎn)的出度？怎樣計(jì)算有向圖頂點(diǎn)的入度？怎樣計(jì)算有向圖頂點(diǎn)Vi的度：需遍歷全表鄰接表的優(yōu)點(diǎn)：TD(Vi)=單鏈表中鏈接的結(jié)點(diǎn)個(gè)數(shù)OD(Vi)單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù)I D( Vi ) 鄰接點(diǎn)為Vi的弧個(gè)數(shù)TD(Vi) = OD( Vi ) + I D( Vi )空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒有鄰接矩陣方便。第23頁/共104頁251. 聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的

16、一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2. 區(qū)別： 對(duì)于任一確定的無向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無關(guān)）。 鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3. 用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（en2)第24頁/共104頁26#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù)空間效率為O(n+2e)或O(n+e)時(shí)間效率為O(n+e*n)Typedef struct VNode /頂點(diǎn)結(jié)構(gòu) VertexType data; /頂點(diǎn)信息 A

17、rcNode * firstarc; /指向依附該頂點(diǎn)的第一條弧的指針VNode, AdjList MAX_VERTEX_NUM ; Typedef struct /圖結(jié)構(gòu) AdjList vertics ; /應(yīng)包含鄰接表 int vexnum, arcnum; /應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù) int kind; /還應(yīng)說明圖的種類（用標(biāo)志）ALGraph; Typedef struct ArcNode /弧結(jié)構(gòu) int adjvex; /該弧所指向的頂點(diǎn)位置 struct ArcNode *nextarcs; /指向下一條弧的指針 InfoArc *info; /該弧相關(guān)信息的指針 ArcNod

18、e；圖的鄰接表生成算法作為自測(cè)題第25頁/共104頁27 它是有向圖的另一種鏈?zhǔn)浇Y(jié)構(gòu)。 思路：將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表的結(jié)合。1、開設(shè)弧結(jié)點(diǎn)，設(shè)5個(gè)域（每段弧是一個(gè)數(shù)據(jù)元素）2、開設(shè)頂點(diǎn)結(jié)點(diǎn)，設(shè)3個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）tailvexheadvexhlinktlinkinfo data : 頂點(diǎn)信息Firstin : 以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn)Firstout: 以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn)dataFirstinFirstout頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)tailvex: 弧尾頂點(diǎn)位置 headvex: 弧頭頂點(diǎn)位置hlink: 弧頭相同的下一弧位置tlink: 弧尾相同的下一弧位置i

19、nfo: 弧信息n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？仍用順序存儲(chǔ)結(jié)構(gòu)第26頁/共104頁28v1v2v3v420233031十字鏈表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的入度、出度等。FirstoutFirstindata頂點(diǎn)結(jié)點(diǎn)infotlinkhlinkheadvextailvex弧結(jié)點(diǎn)0v11v22v33v401230 102此無權(quán)圖未開第4分量空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同。第27頁/共104頁29#define MAX_VERTEX_NUM 20Typedef struct ArcBox /弧結(jié)點(diǎn)結(jié)構(gòu)，5分量 int tailvex , headvex ; struct ArcBox * hli

20、nk , tlink; InfoType *info; ArcBox;Typedef struct VexNode /頂點(diǎn)結(jié)構(gòu), 3分量 VertexType data; ArcBox * firstin,*firstout;VexNode;Typedef struct /圖結(jié)構(gòu),整體概念 VexNode xlist MAX_VERTEX_NUM ; /表頭向量 int vexnum, arcnum;OLGraph; 第28頁/共104頁30這是無向圖的另一種存儲(chǔ)結(jié)構(gòu)，當(dāng)對(duì)邊操作時(shí)建議采用此種結(jié)構(gòu)存儲(chǔ)。 1、設(shè)立邊結(jié)點(diǎn)， 6個(gè)域（每條邊是一個(gè)數(shù)據(jù)元素）2、設(shè)立頂點(diǎn)結(jié)點(diǎn)， 2個(gè)域（每個(gè)頂點(diǎn)也是一

21、個(gè)數(shù)據(jù)元素）markivexilinkjvexjlinkinfo邊結(jié)點(diǎn) data : 存儲(chǔ)頂點(diǎn)信息Firstedge : 依附頂點(diǎn)的第一條邊結(jié)點(diǎn)dataFirstedge頂點(diǎn)結(jié)點(diǎn)mark：標(biāo)志域ivex， jvex : 邊依附的兩個(gè)頂點(diǎn)位置 ilink: 指向下一條依附頂點(diǎn) i 的邊位置jlink; 指向下一條依附頂點(diǎn) j 的邊位置info: 邊信息n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？仍用順序存儲(chǔ)結(jié)構(gòu)第29頁/共104頁31121 4232 43 4 v1v2v3v5v4v4鄰接多重表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的度等。0v11v22v33v44v501234Firstedgedata頂點(diǎn)結(jié)點(diǎn)markinfo

22、jlinkjvexilinkivex邊結(jié)點(diǎn)空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同。0103此無權(quán)圖未開第6分量第30頁/共104頁32一、深度優(yōu)先搜索二、廣度優(yōu)先搜索 遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊，訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，就叫做它是圖的基本運(yùn)算。遍歷實(shí)質(zhì)：找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過程。圖的特點(diǎn)：圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)解決思路：可設(shè)置一個(gè)輔助數(shù)組 visited n ，用來標(biāo)記每個(gè)被訪問過的頂點(diǎn)。它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個(gè)頂點(diǎn)i 被訪問，就立

23、即改 visited i為1，防止它被多次訪問。圖常用的遍歷：怎樣避免重復(fù)訪問？第31頁/共104頁33基本思想：仿樹的先序遍歷過程。Depth_First Searchv1v2v3v8v7v6v4v5起點(diǎn)起點(diǎn)遍歷步驟應(yīng)退回到V8，因?yàn)閂2已有標(biāo)記第32頁/共104頁34詳細(xì)歸納：E在訪問圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問它的任一鄰接頂點(diǎn) w1；E再從 w1 出發(fā)，訪問與 w1鄰接但還未被訪問過的頂點(diǎn) w2；E然后再從 w2 出發(fā)，進(jìn)行類似的訪問， E如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。E接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它未被訪問的鄰

24、接頂點(diǎn)。 如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問； 如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。簡(jiǎn)單歸納： 訪問起始點(diǎn) v; 若v的第1個(gè)鄰接點(diǎn)沒訪問過，深度遍歷此鄰接點(diǎn)；若當(dāng)前鄰接點(diǎn)已訪問過，再找v的第2個(gè)鄰接點(diǎn)重新遍歷。第33頁/共104頁351 2345610 000000 0000030 0000040 0000050 0000060 00000000000123456010000100001000010101鄰接矩陣A輔助數(shù)組 visited n 起點(diǎn)開輔助數(shù)組 visited n ！例：1 23 456100000 00

25、300 00400 005000060 0000請(qǐng)注意逐級(jí)回退是遞歸概念第34頁/共104頁36for( j=1; jlink) /當(dāng)存在起點(diǎn)的第一個(gè)鄰接點(diǎn)時(shí) p=p-link; v=p-data; if(!visitedv)DFS(List,v,p); /進(jìn)行遞歸 return; 第37頁/共104頁39（）n如果用鄰接矩陣來表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描該頂點(diǎn)所在行，因此遍歷全部頂點(diǎn)所需的時(shí)間為O(n2)。n如果用鄰接表來表示圖，雖然有 2e 個(gè)表結(jié)點(diǎn)，但只需掃描 e 個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問 n個(gè)頭結(jié)點(diǎn)的時(shí)間，因此遍歷圖的時(shí)間復(fù)雜度為O(n+e)。結(jié) 論：稠密圖適于在鄰接矩陣

26、上進(jìn)行深度遍歷；稀疏圖適于在鄰接表上進(jìn)行深度遍歷。第38頁/共104頁40基本思想：仿樹的層次遍歷過程。Breadth_First Searchv1v2v3v8v7v6v4v5起點(diǎn)遍歷步驟起點(diǎn)第39頁/共104頁41簡(jiǎn)單歸納：在訪問了起始點(diǎn)v之后，依次訪問 v的鄰接點(diǎn)；然后再依次（順序）訪問這些點(diǎn)（下一層）中未被訪問過的鄰接點(diǎn)；直到所有頂點(diǎn)都被訪問過為止。廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。第40頁/共104頁42鄰接表寬度優(yōu)先搜索要借助隊(duì)列！例：起點(diǎn)輔助隊(duì)列v2已訪問過了V

27、2入隊(duì)visited n 仍需要第41頁/共104頁43while(rear!=front) /隊(duì)不空時(shí) front=(front+1)%n; v=qfront; /訪問過的頂點(diǎn)出隊(duì) p=Listv.firstarc; /P指向第1個(gè)鄰接點(diǎn) while(!p) if(! Visitedadjvex(p) )/未到表尾，且鄰接域未訪問過， Visit(adjvex(p); Visitedadjvex(p)=1;/則先輸出再改標(biāo)記， rear=(rear+1)%n; qrear= adjvex(p) /最后再入隊(duì) p=nextarc(p); /指向單鏈表中下一個(gè)鄰接點(diǎn) return / BFS1B

28、FS1(List, n, v) /List為鄰接表，v為起點(diǎn)，Qn為輔助隊(duì)列 Visit(v); Visitedv=1; /訪問（例如打?。╉旤c(diǎn)v并修改標(biāo)志 層次遍歷應(yīng)當(dāng)用隊(duì)列?。ń滩纳螧FS算法見P170）front=n-1;rear=0; /隊(duì)列指針初始化qrear=v; /起始點(diǎn)入隊(duì)第42頁/共104頁44空間復(fù)雜度相同，都是O(n)(借用堆?；蜿?duì)列裝n個(gè)頂點(diǎn)）；時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無關(guān)。如果使用鄰接表來表示圖，則如果使用鄰接表來表示圖，則BFS循環(huán)的總時(shí)間代價(jià)循環(huán)的總時(shí)間代價(jià)為為 d0 + d1 + + dn-1 = O(e)，其中的其中的 di

29、 是頂點(diǎn)是頂點(diǎn) i 的度的度。如果使用鄰接矩陣，則如果使用鄰接矩陣，則BFS對(duì)于每一個(gè)被訪問到的頂對(duì)于每一個(gè)被訪問到的頂點(diǎn)，都要循環(huán)檢測(cè)矩陣中的整整一行（點(diǎn)，都要循環(huán)檢測(cè)矩陣中的整整一行（ n 個(gè)元素），個(gè)元素），總的時(shí)間代價(jià)為總的時(shí)間代價(jià)為O(n2)。（）第43頁/共104頁451. 求圖的生成樹2. 求最小生成樹第44頁/共104頁46生成樹：是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有n-1條邊。生成森林：由若干棵生成樹組成，含全部頂點(diǎn)，但構(gòu)成這些樹的邊是最少的。思考1：若對(duì)連通圖進(jìn)行遍歷，得到的是什么？ 得到的將是一個(gè)極小連通子圖，即圖的生成樹！由深度優(yōu)先搜索得到的生成樹，稱為深度優(yōu)

30、先搜索生成樹。由廣度優(yōu)先搜索得到的生成樹，稱為廣度優(yōu)先搜索生成樹。思考2：若對(duì)非連通圖進(jìn)行遍歷，得到的是什么？ 得到的將是各連通分量的生成樹，即圖的生成森林！第45頁/共104頁47DFS生成樹v0v1v2v4v4v3鄰接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生成樹v0v1v3v2v4無向連通圖第46頁/共104頁48其實(shí)由鄰接矩陣或鄰接表也能直接畫出生成森林DEABCFJLMGHIK求解步驟：Step1:先求出鄰接矩陣或鄰接表；Step2:寫出DFS或BFS結(jié)果序列；Step3:畫出對(duì)應(yīng)子圖或生成森林。這是一個(gè)無向非連通圖（參見教材P170-1

31、71例）下面選用鄰接表方式來求深度優(yōu)先搜索生成森林生成森林的定義（對(duì)有向或無向圖均適用）：是若干棵生成樹的集合，含全部頂點(diǎn)，但構(gòu)成這些樹的邊或弧是最少的。第47頁/共104頁49115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DEGHIK子圖1：再寫出DFS結(jié)果ABMJLCFDEGHKIABCFJLM先寫出鄰接表（或鄰接矩陣）：子圖2：子圖3：最小連通！怎樣找3個(gè)根？第48頁/共104頁50DEGHIK子圖(或連通分量)ABCFJLMABCFJLMDEGHIK生成森林第49頁/共104頁5

32、1首先明確：使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹肯定有 n 個(gè)頂點(diǎn)和僅僅n-1 條邊。即有權(quán)圖構(gòu)造最小生成樹的準(zhǔn)則v 必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；v 必須使用且僅使用n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；v 不能使用產(chǎn)生回路的邊。目標(biāo)：在網(wǎng)絡(luò)的多個(gè)生成樹中，尋找一個(gè)各邊權(quán)值之和最小的生成樹。第50頁/共104頁52欲在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 條線路，那么，如何選擇n1條線路使總費(fèi)用最少？先建立數(shù)

33、學(xué)模型：頂點(diǎn)表示城市，有n個(gè)；邊表示線路，有n1條；邊的權(quán)值表示線路的經(jīng)濟(jì)代價(jià)；連通網(wǎng)表示n個(gè)城市間的通信網(wǎng)。顯然此連通網(wǎng)是一棵生成樹！問題抽象： n個(gè)頂點(diǎn)的生成樹很多，需要從中選一棵代價(jià)最小的生成樹，即該樹各邊的代價(jià)之和最小。此樹便稱為最小生成樹MST。Minimum cost Spanning Tree第51頁/共104頁53若U集是V的一個(gè)非空子集，若(u0, v0)是一條最小權(quán)值的邊，其中u0U，v0V-U；則：(u0, v0)必在最小生成樹上。 先把權(quán)值最小的邊歸入生成樹內(nèi)，逐個(gè)遞增，舍去回路邊，則得到的很可能就是最小生成樹！求MST有多種算法，但最常用的是以下兩種：vKruskal

34、（克魯斯卡爾）算法vPrim（普里姆）算法 Kruskal算法特點(diǎn)：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。Prime算法特點(diǎn): 將頂點(diǎn)歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)。第52頁/共104頁54Kruskal算法效率分析：Kruskal算法的時(shí)間效率O（elog2e）Kruskal算法是歸并邊，適用于稀疏圖（用鄰接表）第53頁/共104頁55Prim算法效率分析：Prim算法的時(shí)間效率O（n2）Prim算法是歸并頂點(diǎn)，適用于稠密網(wǎng)。第54頁/共104頁56 圖5-4-5 構(gòu)造最小生成樹過程中輔助數(shù)組中各分量的值圖5-4-5 構(gòu)造最小生成樹過程中輔助數(shù)組中各分量的值第55頁/共104頁57第56頁/共1

35、04頁58第57頁/共104頁59第58頁/共104頁60 C2 C3 C4 C5 C6 C7 C8 C1 課程代號(hào) 普通物理 計(jì)算機(jī)原理 程序設(shè)計(jì) 離散數(shù)學(xué) 數(shù)據(jù)結(jié)構(gòu) 編譯技術(shù) 操作系統(tǒng) 高等數(shù)學(xué) 課程代號(hào) C1 C2 C1, C4 C4, C5 C4, C6 C3, C6 先行課程 第59頁/共104頁61 C1 C2 C3 C4 C5 C6 C7 C8 第60頁/共104頁62第61頁/共104頁63 第62頁/共104頁64若有向圖若有向圖G所有頂點(diǎn)都在拓?fù)渑潘许旤c(diǎn)都在拓?fù)渑判蛐蛄兄?，則序序列中，則AOV網(wǎng)絡(luò)必定不網(wǎng)絡(luò)必定不包含有有向環(huán)路。包含有有向環(huán)路。第63頁/共104頁65AO

36、V網(wǎng)絡(luò)中存在有向環(huán)路，遇到這網(wǎng)絡(luò)中存在有向環(huán)路，遇到這種情況，拓?fù)渑判蚓蜔o法進(jìn)行種情況，拓?fù)渑判蚓蜔o法進(jìn)行了。了。第64頁/共104頁66C1C10C11C6C2C12C4C8C3C7C5C9拓?fù)溆行蛐蛄校海–1，C2，C3，C4，C5，C7，C9，C10，C11，C6，C12，C8）（C9，C10，C11，C6，C1，C12，C4，C2，C3，C5，C7，C8）第65頁/共104頁6710 c121 c232 c341 c452 c561 c672 c782 c890 c9101 c10111 c11123 c12c2c3c5c5c7c8c10c12c6c3c7c11c4c8c12c1201

37、010211第66頁/共104頁68a b c d e f（a）AOV網(wǎng)；(b)輸出v0后；（c）輸出v5后；（d）輸出v3后；（e）輸出v2后；（f）輸出v1后。這樣得到的一個(gè)拓?fù)渑判蛐蛄袨椋簐0, v5, v3, v2, v1, v4第67頁/共104頁69第68頁/共104頁70作業(yè)名稱作業(yè)名稱作業(yè)時(shí)間（作業(yè)時(shí)間（h） 緊前作業(yè)緊前作業(yè)A（型砂準(zhǔn)備）（型砂準(zhǔn)備）B（造型）（造型）C（砂型烘干）（砂型烘干）D（芯砂準(zhǔn)備）（芯砂準(zhǔn)備）E（芯骨澆鑄）（芯骨澆鑄）F（芯骨裝配）（芯骨裝配）G（造四個(gè)（造四個(gè)I號(hào)泥芯）號(hào)泥芯）H（造四個(gè)（造四個(gè)II號(hào)泥芯）號(hào)泥芯）I（II號(hào)泥芯干燥號(hào)泥芯干燥244

38、44.3 A BED, FD, FH第69頁/共104頁71ABCDEFGHI第70頁/共104頁72兩個(gè)事件之間只能畫一條箭線，表示一項(xiàng)作業(yè)。若兩項(xiàng)或兩項(xiàng)以上作業(yè)同時(shí)開始或結(jié)束，就要引進(jìn)虛事件和虛作業(yè)，虛作業(yè)不消耗資源。第71頁/共104頁73第72頁/共104頁74第73頁/共104頁75作業(yè)作業(yè)代號(hào)代號(hào)計(jì)劃完計(jì)劃完成時(shí)間成時(shí)間緊前緊前作業(yè)作業(yè)作業(yè)作業(yè)代號(hào)代號(hào)計(jì)劃完計(jì)劃完成時(shí)間成時(shí)間緊前緊前作業(yè)作業(yè)ABCDEF510114415BAC,DGHIJK2135251520B,EB,EB,EF,G,IF,G表71第74頁/共104頁76CBEDAX2X1KGIH0FJ0第75

39、頁/共104頁77現(xiàn)后才能開始。現(xiàn)后才能開始。n權(quán)值表示活動(dòng)持續(xù)的時(shí)間。權(quán)值表示活動(dòng)持續(xù)的時(shí)間。第76頁/共104頁78 a1=6 a2=4 a4=1 a3=5 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 第77頁/共104頁79第78頁/共104頁80是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的效率，縮短整個(gè)工期?；顒?dòng)的效率，縮短整個(gè)工期。第79頁/共104頁81第80頁/共104頁82 Vj ai )(V所需時(shí)間活動(dòng)iLajiL確定關(guān)鍵路徑的方法就是要確定ei=Li的關(guān)鍵活動(dòng)！第81頁/共104頁83第82頁/共104頁84)1(),(max

40、,nkkjwjekevpkjv第83頁/共104頁85 Vj Vk p第84頁/共104頁86)1(),(min,njkjwkLjLvskjv第85頁/共104頁87 Vj Vk s第86頁/共104頁88向匯點(diǎn)的遞推，向源點(diǎn)的遞向匯點(diǎn)的遞推，向源點(diǎn)的遞推按相反的順序進(jìn)行即可，推按相反的順序進(jìn)行即可，不必再重新排序。不必再重新排序。第87頁/共104頁89第88頁/共104頁90第89頁/共104頁91v1v3v8v9v7v2v6v4v5a3=5a6=2a9=4a11=4a10=2a8=7a4=1a1=6a2=4a5=1a7=9如何求關(guān)鍵路徑？ 求出各個(gè)最早出現(xiàn)時(shí)間ve（j）和最遲發(fā)生時(shí) 間v

41、l（j）。 再判斷各e（i）是否等于l（i）！第90頁/共104頁92v1v3v8v9v7v2v6v4v5a3=5a6=2a9=4a11=4a10=2a8=7a4=1a1=6a2=4a5=1a7=9064571418716從ve（0）=0開始向后推.Ve（j）=Maxve（i）+dut（i,j） (j=1，2.n-1)第91頁/共104頁931 求事件最遲出現(xiàn)時(shí)間v1v3v8v9v7v2v6v4v5a3=5a6=2a9=4a11=4a10=2a8=7a4=1a1=6a2=4a5=1a7=90668101418716從vl(9）=18開始向回推（倒計(jì)時(shí)）。Ve（i）=Minvl（j）- dut（i,j） (j=n-2,n-3,-,0)第92頁/共104頁94 事件 j evj Lvj 活動(dòng) i ei Li Li-ei 1 0 0 1 0 0 0 2 6 6 2 0 2 2 3 4 6 3 0 3 3 4 5 8 4 6 6 0 5 7 7 5 4 6 2 6 7 10 6 5 8 3 7 16 16 7 7 7 0 11 14 14 0 10 16 16 0 9 18 18 9 7 10 3 8 14 14 8 7 7 0