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

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

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

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

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

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

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

7、的原則：存入電腦后能惟一復原第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頂點表：無向圖的鄰接矩陣如何表示？v1v2v3v5v4v4記錄各個頂點信息表示各個頂點之間關(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、向圖的鄰接矩陣可能是不對稱的。頂點vi的出度=第i行元素之和，OD(vi )= A.Edge i j 頂點vi的入度=第i列元素之和。ID(vi )= A.Edge j i 頂點的度=第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é)點vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點vi為頭的弧(即入度邊）。頂點表：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 容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。⒄翼旤c的鄰接點等等。 n個頂點需要個單元存儲邊(弧);空間效率為O(n )。定義：A.Edge i j =Wij 或（vi, vj）VR 無邊（?。﹙1v2v3v4Nv5v65489755613以有向網(wǎng)為例：鄰接矩陣： N.Edge =( v1 v2 v3 v4 v5 v6 )鄰接矩陣法優(yōu)點：鄰接矩陣法缺點：頂點表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 v1v2v3v4v5v6對稀疏圖

10、而言尤其浪費空間。第17頁/共104頁19注：用兩個數(shù)組分別存儲頂點表和鄰接矩陣#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點數(shù)Typedef enum DG, DN, AG, AN GraphKind; /有向/無向圖，有向/無向網(wǎng)對于n個頂點的圖或網(wǎng)，空間效率=O(n2)Typedef struct ArcCell /弧（邊）結(jié)點的定義 VRType adj; /頂點間關(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 ; /頂點表，用一維向量即可(n)AdjMatrix arcs; /鄰接矩陣n*nInt Vernum, arcnum; /頂點總數(shù)n，?。ㄟ叄┛倲?shù)eGraphKind kind; /圖的種類標志Mgraph; 第18頁/共104頁20Status CreateUDN(Mgraph &G) /無向網(wǎng)的構(gòu)造，用鄰接矩陣表示scanf(&G.vexnum, &G.arcnum, &IncInfo); /輸入總頂點數(shù)n、

12、總弧數(shù)e和信息for(i=0;iG.vexnum,;+i) scanf(&G.vexsi );/輸入n個頂點值，存入一維向量對于n個頂點e條弧的網(wǎng)，建網(wǎng)時間效率 = O(n+n2+e*n)for(i=0; iG.vexnum; +i) /對鄰接矩陣n*n個單元初始化，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); /輸入弧的兩頂點以及對應權(quán)值 i=LocateVex(G,

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

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

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

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

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

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

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

20、nk , tlink; InfoType *info; ArcBox;Typedef struct VexNode /頂點結(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這是無向圖的另一種存儲結(jié)構(gòu)，當對邊操作時建議采用此種結(jié)構(gòu)存儲。 1、設(shè)立邊結(jié)點， 6個域（每條邊是一個數(shù)據(jù)元素）2、設(shè)立頂點結(jié)點， 2個域（每個頂點也是一

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

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

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

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

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

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

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

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

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

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

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

32、1首先明確：使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n 個頂點的連通網(wǎng)絡(luò)的生成樹肯定有 n 個頂點和僅僅n-1 條邊。即有權(quán)圖構(gòu)造最小生成樹的準則v 必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；v 必須使用且僅使用n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個頂點；v 不能使用產(chǎn)生回路的邊。目標：在網(wǎng)絡(luò)的多個生成樹中，尋找一個各邊權(quán)值之和最小的生成樹。第50頁/共104頁52欲在n個城市間建立通信網(wǎng)，則n個城市應鋪n-1條線路；但因為每條線路都會有對應的經(jīng)濟成本，而n個城市可能有n(n-1)/2 條線路，那么，如何選擇n1條線路使總費用最少？先建立數(shù)

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

34、（克魯斯卡爾）算法vPrim（普里姆）算法 Kruskal算法特點：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。Prime算法特點: 將頂點歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)。第52頁/共104頁54Kruskal算法效率分析：Kruskal算法的時間效率O（elog2e）Kruskal算法是歸并邊，適用于稀疏圖（用鄰接表）第53頁/共104頁55Prim算法效率分析：Prim算法的時間效率O（n2）Prim算法是歸并頂點，適用于稠密網(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 課程代號 普通物理 計算機原理 程序設(shè)計 離散數(shù)學 數(shù)據(jù)結(jié)構(gòu) 編譯技術(shù) 操作系統(tǒng) 高等數(shù)學 課程代號 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所有頂點都在拓撲排所有頂點都在拓撲排序序列中，則序序列中，則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)路，遇到這種情況，拓撲排序就無法進行種情況，拓撲排序就無法進行了。了。第64頁/共104頁66C1C10C11C6C2C12C4C8C3C7C5C9拓撲有序序列：（C1，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后。這樣得到的一個拓撲排序序列為：v0, v5, v3, v2, v1, v4第67頁/共104頁69第68頁/共104頁70作業(yè)名稱作業(yè)名稱作業(yè)時間（作業(yè)時間（h） 緊前作業(yè)緊前作業(yè)A（型砂準備）（型砂準備）B（造型）（造型）C（砂型烘干）（砂型烘干）D（芯砂準備）（芯砂準備）E（芯骨澆鑄）（芯骨澆鑄）F（芯骨裝配）（芯骨裝配）G（造四個（造四個I號泥芯）號泥芯）H（造四個（造四個II號泥芯）號泥芯）I（II號泥芯干燥號泥芯干燥244

38、44.3 A BED, FD, FH第69頁/共104頁71ABCDEFGHI第70頁/共104頁72兩個事件之間只能畫一條箭線，表示一項作業(yè)。若兩項或兩項以上作業(yè)同時開始或結(jié)束，就要引進虛事件和虛作業(yè)，虛作業(yè)不消耗資源。第71頁/共104頁73第72頁/共104頁74第73頁/共104頁75作業(yè)作業(yè)代號代號計劃完計劃完成時間成時間緊前緊前作業(yè)作業(yè)作業(yè)作業(yè)代號代號計劃完計劃完成時間成時間緊前緊前作業(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)值表示活動持續(xù)的時間。權(quán)值表示活動持續(xù)的時間。第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)鍵活動，以便爭取提高關(guān)鍵是關(guān)鍵活動，以便爭取提高關(guān)鍵活動的效率，縮短整個工期?；顒拥男?，縮短整個工期。第79頁/共104頁81第80頁/共104頁82 Vj ai )(V所需時間活動iLajiL確定關(guān)鍵路徑的方法就是要確定ei=Li的關(guān)鍵活動！第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向匯點的遞推，向源點的遞向匯點的遞推，向源點的遞推按相反的順序進行即可，推按相反的順序進行即可，不必再重新排序。不必再重新排序。第87頁/共104頁89第88頁/共104頁90第89頁/共104頁91v1v3v8v9v7v2v6v4v5a3=5a6=2a9=4a11=4a10=2a8=7a4=1a1=6a2=4a5=1a7=9如何求關(guān)鍵路徑？ 求出各個最早出現(xiàn)時間ve（j）和最遲發(fā)生時 間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)時間v1v3v8v9v7v2v6v4v5a3=5a6=2a9=4a11=4a10=2a8=7a4=1a1=6a2=4a5=1a7=90668101418716從vl(9）=18開始向回推（倒計時）。Ve（i）=Minvl（j）- dut（i,j） (j=n-2,n-3,-,0)第92頁/共104頁94 事件 j evj Lvj 活動 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