數(shù)據(jù)結構課件第七章圖無答案

1、警 示2011年9月 2013年11月 2014年6月就要畢業(yè)了?；仡^看自己所謂的大學生活，我想哭，不是因為離別，而是因為什么都沒學到。我不知，簡歷該怎么寫，若是以往我會讓它空白。最大的收獲也許是對什么都沒有的忍耐和適應第 七 章 圖第七章 圖圖的定義和術語圖的存儲結構圖的基本操作-遍歷應用最小生成樹 拓撲排序 關鍵路徑 最短路7.1圖的定義和術語線性表、樹和圖：從關系、結構兩個角度區(qū)分 AB E C D B CA D F E圖Graph;頂點Vertex;序偶;弧Arc;弧頭B/弧尾ADigraph;Undigraph;無序對(A,B):;Edge網NetWork:弧或邊含權的圖,分有向網D

2、N、無向網UDN(無向)完全圖:邊數(shù)最大的無向簡單圖,滿足e=n*(n-1)/2有向完全圖:弧數(shù)最大的有向簡單圖, e=n*(n-1)稀疏圖(如enlogn) 稠密圖ABECF1597211132BECBBC子圖Subgraph 鄰接點:無向圖如A與B互為鄰接點,有向圖如A鄰接到B無向圖頂點的度,如TD(A)=2；有向圖分入/出度,度為兩者之和 ID(A)=1,OD(A)=2,TD(A)=3路徑、簡單路徑、回路(環(huán))、路徑長度術語 B CA D F EABECF若無向圖G中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖。如能找到一條含全部頂點的路徑則說明是連通圖無向圖中的極大連通子圖稱作此圖的

3、連通分量。極大指頂點盡量多,頂點連同其關聯(lián)的邊構成連通分量.圖本身連通則連通分量唯一,是自身BACDFEBACDFE連通圖,連通分量 (無向圖)若任意兩頂點間都存在一條有向路徑，則稱此有向圖為強連通圖。ABECFABECF有向圖的極大強連通子圖稱作它的強連通分量。強連通圖、強連通分量(有向圖)連通圖的一個含有全部頂點的子圖,如果連通且極小，則它必是一顆樹(邊數(shù)為n-1)，稱該樹為原連通圖的生成樹。破圈法可得生成樹 對非連通圖，由各個連通分量的生成樹組成的集合稱為此非連通圖的生成森林。BACDFE生成樹與生成森林（無向圖）注:樹是含邊數(shù)最小的連通圖(n-1);圖中若邊少于n-1則必不連通；若圖連

4、通則至少含n-1條邊；若圖中多于n-1條邊則必然含有回路。含n-1條邊的連通圖必然是樹ADT Graph 數(shù)據(jù)對象V：若干頂點組成的集合 數(shù)據(jù)關系R：R=VR VR| v,wV 且 表示從 v 到 w 有一條弧，可代表v認識w 或 v到w有路等) 基本操作圖的抽象數(shù)據(jù)類型定義邏輯結構CreatGraph(&G, V, VR); / 按定義(V, VR) 構造圖GDestroyGraph(&G); / 銷毀圖G結構的建立和銷毀插入或刪除頂點、弧InsertVex(&G, v); /在圖G中增添新頂點v。DeleteVex(&G, v);/ 刪除G中頂點v及其相關的弧。InsertArc(&G,

5、v, w); /在G中增添弧，若G是無向的，則還增添對稱弧DeleteArc(&G, v, w); /在G中刪除弧，若G是無向的，則還刪除對稱弧遍 歷DFSTraverse(G, v, Visit(); /從頂點v起深度優(yōu)先遍歷圖G,對每個頂點執(zhí)行一次VisitBFSTraverse(G, v, Visit(); /從v起廣度優(yōu)先遍歷圖G，每個頂點調用一次函數(shù)Visit規(guī)則:訪問起始頂點v,然后選取與v鄰接的未訪問的第一個頂點w,訪問之，再選取與w鄰接的未訪問的第一個頂點，訪問之。重復進行至當前節(jié)點的所有鄰接點都被訪問過，此時后退到最近訪問過的頂點，找其下一個未訪問的鄰接點訪問,依次類推.如A

6、BE FCD H說明:一次可遍歷所有與v連通的頂點。若尚有頂點未訪問(非連通圖),則從其開始重復上述過程.對應樹的先根遍歷?？傻蒙疃葍?yōu)先生成樹或森林以及連通分量遞歸描述：訪問v, 逐個從v未訪問的鄰接點出發(fā)遞歸遍歷.規(guī)則:訪問v,訪問v的全部未訪問的鄰接點,再逐個從這些鄰接點出發(fā)重復.一次可遍歷所有與v連通的頂點,若尚有頂點未訪問則從其開始重復開始上述過程.如ABEHFCD對應樹層序遍歷,可得廣度優(yōu)先生成樹/森林,可得連通分量,實現(xiàn)? B CA D F EH對頂點的訪問操作LocateVex(G, u); / 若G中存在頂點與u”相等”，則返回該頂點在圖中“位置”(下標或指針)GetVex(G

7、, v); / 返回G中頂點v的值。PutVex(&G, v, value);/為G中頂點v賦值value。對鄰接點的操作FirstAdjVex(G, v); /返回G中頂點v的“第一個鄰接點”。若該頂點/在 G 中沒有鄰接點，則返回“空”。NextAdjVex(G, v, w); / w是v的一個鄰接點,返回v的“下一個鄰接點”。/若w是v的最后一個鄰接點，則返回“-1”。圖的數(shù)組表示(p161)(鄰接矩陣)圖的鄰接表表示(p163)有向圖的十字鏈表表示(p164) 無向圖的鄰接多重表表示(p166)7.2 圖的存儲結構BACDFE鄰接矩陣:行、列各對應一個頂點,若第i行對應的頂點到第j列對

8、應的頂點有弧相連則Aij=1,否則為0。n*n階 A B C D E F ABCDEF1、圖的數(shù)組表示-鄰接矩陣adjacency matrix鄰接矩陣舉例ABECD無向圖的鄰接矩陣必為對稱陣網的鄰接矩陣Aij=wij或/-圖的數(shù)組(鄰接矩陣)存儲表示-typedef char VertexType;#define INFINITY 10000 /最大值 #define MAX_VERTEX_NUM 20 /最大頂點個數(shù)typedef enumDG, DN, UDG, UDN GraphKind;/圖類型 typedef struct ArcCell / 弧的定義 VRType adj; /鄰

9、接數(shù),0/1或w/。VRType為int/double InfoType *info; /弧的附加信息,InfoType可為charArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 圖的定義 VertexType vexsMAX_VERTEX_NUM; /頂點信息 AdjMatrix arcs; / 鄰接矩陣,存儲弧信息,靜態(tài)數(shù)組 int vexnum, arcnum; / 頂點數(shù)，弧數(shù) GraphKind kind; / 圖的類型標記 MGraph; /矩陣圖 A B C D E FABCDEFStatus Crea

10、teGraph(Mgraph &G) /輸入圖的種類及頂點和邊信息構造圖G(鄰接矩陣表示) scanf(“%d”,&G.kind);/枚舉值DG,DN實輸入0 1 switch (G.kind) case DG : return CreateDG(G); case DN : return CreateDN(G); case UDG : return CreateUDG(G); case UDN : return CreateUDN(G); default : return ERROR;圖的創(chuàng)建Status CreateUDN(Mgraph &G) /建立無向網G 輸入G.vexnum,G.ar

11、cnum, IncInfo;/IncInfo為0表各弧無附加信息 for (i=0 ; i G.vexnum; +i) scanf(“%c”,G.vexsi); for (i=0 ; i G.vexnum; +i) for(j=0 ; jvexnum; +j) G.arcsij=INFNITY,NULL; /各弧初始化 for (k=0;k G.arcnum;+k) scanf(“%c %c %lf”,&v1,&v2,&w); /輸入一“邊”及其權值 i=LocateVex(G,v1);j= LocateVex(G,v2) ;/確定頂點下標 G.arcsij.adj = w; if (IncI

12、nfo) 輸入G.; G.arcsji= G.arcsij; /無向網需將對稱弧加入 /ENDABECF1597211132ABCDEFBACDFE ABCDEF鄰接矩陣優(yōu)缺點：易于求頂點度(區(qū)分有/無向圖)、求鄰接點，易判斷兩點間是否有弧或邊相連,但不利于稀疏圖的存儲，因弧不存在時也要存儲相應信息，且要預先分配足夠大空間1 4230 120 1 2 3 4 A B C D EABECDtypedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode;datafirsta

13、rcadjvexnextarcinfotypedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; GraphKind kind; ALGraph; /鄰接表圖2、鄰接表存儲表示Status CreateGraph(ALGraph &G) /建立圖的鄰接表的結構 scanf(“%d”, &G.kind); switch (G.kind) case DG : return Creat

14、eDG(G); case DN : return CreateDN(G); case UDG : return CreateUDG(G); case UDN : return CreateUDN(G); default : return ERROR;鄰接表圖的創(chuàng)建【補充】Status CreateDN(ALGraph &G) /建立有向網 scanf(“%d%d%d”,&G.vexnum,&G.arcnum,&IncInfo); for (i=0 ; i G.vexnum; +i) scanf(G.verticesi.data); G.verticesi.firstarc=NULL; for

15、(k=0;kadjvex=j; if (IncInf) 輸入(arcn-info); arc-nextarc = G.verticesi.firstarc; /插入到開始位置 G.verticesi.firstarc=arcn;/鄰接點與輸入逆序排列P164,正序? /鄰接點順序依賴輸入順序和創(chuàng)建程序，“不給”默認正序 Return OK； /思考無向網的創(chuàng)建有何不同？4 1A0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 1 F 1 2 3 BACDFE頂點數(shù)組(頭結點)鄰接點鏈表無向圖中每條邊出現(xiàn)兩次,n個頂點e條邊需n個頭結點和2e個表結點無向圖的鄰接表存儲表示小

16、結：掌握圖的概念和基本術語掌握圖的鄰接矩陣存儲和鄰接表存儲結構，理解優(yōu)缺點掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的規(guī)則會通過遍歷求圖的連通分量和深度優(yōu)先、廣度優(yōu)先生成樹、生成森林作業(yè)：1 5 B CA D F EH A B C D E FABCDEF/-圖的數(shù)組(鄰接矩陣)存儲表示-typedef char VertexType;#define INFINITY 10000 /最大值 #define MAX_VERTEX_NUM 20 /最大頂點個數(shù)typedef enumDG, DN, UDG, UDN GraphKind;/圖類型 typedef struct ArcCell / 弧的定義 V

17、RType adj; /鄰接數(shù),0/1或w/。VRType為int/double InfoType *info; /弧的附加信息,Info可為charArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 圖的定義 VertexType vexsMAX_VERTEX_NUM; /頂點信息 AdjMatrix arcs; / 鄰接矩陣,存儲弧信息,靜態(tài)數(shù)組 int vexnum, arcnum; / 頂點數(shù)，弧數(shù) GraphKind kind; / 圖的類型標記 MGraph; /矩陣圖1 4230 120 1 2 3 4 A

18、 B C D E鄰接表舉例ABECDtypedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode;datafirstarcadjvexnextarcinfotypedef struct VNode VertexType data; ArcNode *firstarc; VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; GraphKind kind; ALGraph; /鄰接表圖

19、1 4230 120 1 2 3 4 A B C D E鄰接表說明：ABECD稀疏圖用鄰接表存儲相對節(jié)省空間對有向圖易求頂點出度與鄰接點,但求入度難.若只求入度可引入逆鄰接表,也可結合鄰接表與逆鄰接表引入十字鏈表對無向圖易求度,但邊出現(xiàn)兩次,為方便邊操作可借助多重鏈表A B C D E 303420012343、“有向圖”的十字鏈表存儲表示【選】 ABDCE010A1B2C3D4E.tailvheadvhlinktlinkinfodatafirstinfirstout03VexNode:ArcBox:1224324041具體鄰接點順序依賴輸入順序和圖的創(chuàng)建程序，如逆序3、“有向圖”的十字鏈表存

20、儲表示【選】 typedef struct ArcBox int tailvex, headvex; InfoType *info; struct ArcBox *hlink,*tlink;/指向同弧頭/尾的下一弧 ArcBox;typedef struct VexNode / 頂點的結構表示 VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; int vexnum, arcnum; OLGraph;Status CreateDG(OLGraph G)

21、scanf(&G.vexnum, &G.arcnum, &IncInf); for(i=0;i G.vexnum; +i) scanf(&G.xlisti.data); G.xlisti.firstin=NULL;G.xlisti.firstout=NULL; for(k=0;kinfo); /END 4、“無向圖”的鄰接多重表存儲表示【選】無向圖的鄰接表存儲中，一條邊出現(xiàn)兩次，分別在兩個頂點對應的鏈表中，對邊的操作復雜。為此，將每條邊(Vi,Vj)只用一個如下結點表示:頂點表示為：markivexilinkjvexjlinkinfodatafirstedge0 1 2 3 A B C DAB

22、DC01031223e1e2e3 e4 將邊看作有向的，如A-Btypedef struct Ebox VisitIf mark; / 訪問標記 int ivex, jvex; /該邊依附的兩個頂點的位置 struct EBox *ilink,*jlink;/指向對應頂點為i,j的下一邊 InfoType *info; EBox;4、“無向圖”的鄰接多重表存儲表示【選】typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph; / 鄰接多重表typedef struct VexBox VertexT

23、ype data; EBox *firstedge; / 指向第一條依附該頂點的邊 VexBox;7.3圖的遍歷深度優(yōu)先遍歷規(guī)則:訪問v,逐個從v的鄰接點出發(fā)，若其未訪問則從其開始遞歸遍歷，如此可遍歷所有與v連通的頂點.若尚有頂點未訪問(不連通),則從其開始重復上述過程.如ABEFCDH.void DFS(G，v) VisitFunc(v); visitedv=TRUE; for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w) if（!visitedw）DFS(G，w)；/執(zhí)行DFS(G,A)時會遍歷完所有與連通的頂點void DFSTraverse(Gr

24、aph G, Status (*Visit)(int v) VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v);/visited為全局數(shù)組，VisitFunc函數(shù)為全局函數(shù)指針每個頂點調用一次DFS,DFS主要操作是查找鄰接點,當用鄰接矩陣存儲時查找某頂點的鄰接點復雜度為O(n),總復雜度O(n2);當鄰接表存儲時查找鄰接點總復雜度為O(e),總復雜度為O(n+e)DFSTraverse每調用一次DFS所訪問的頂點連通這些頂

25、點關聯(lián)的邊構成一個連通分量.只保留走過的邊得生成樹或生成森林 B CA D F EHabchdekfgachkfedbgabcdefghk2345607070807812385547注意鄰接點的順序作題時若未給出則默認為正序,實際上應依賴創(chuàng)建程序和輸入順序。若給出存儲結構則以存儲結構為準。如上例既非正序也非逆序,如h、k對應的鏈表，畫生成樹時注意求圖的連通分量、深度優(yōu)先生成樹或生成森林P171DFSTraverse每調用一次DFS所訪問的頂點連同這些頂點關聯(lián)的邊構成一個連通分量.只保留走過的邊得生成樹或生成森林7.3 圖的遍歷廣度優(yōu)先遍歷BFSTraverse(G, v, Visit(); 規(guī)

26、則:訪問v, 訪問v的各未訪問的鄰接點,之后逐個從這些鄰接點出發(fā)重復上述操作。待與v連通的頂點訪問畢再從另一頂點出發(fā). 如ABEHFCD實現(xiàn)：對各個頂點v： 若其尚未訪問則訪問v,之后v入隊。 【隊頂元素出隊，逐個訪問其尚未訪問的鄰接點，每訪問完一個便入隊】。重復【】中內容到隊空 B CA D F EHvoid BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v)visitedv = FALSE; InitQueue(Q); for ( v=0; v=0;w=NextAdjVex(G,v,w) if ( ! v

27、isitedw ) /注意NextAdjVex返回值約定 Visit(w); visitedw=TRUE; EnQueue(Q, w); 對各個頂點v： 若其尚未訪問則訪問v,之后v入隊?！娟犿斣爻鲫?，逐個訪問其尚未訪問的鄰接點，每訪問完一個便入隊】。重復【】中內容到隊空每個頂點進一次隊,出隊時主要操作是查找鄰接點,當用鄰接矩陣存儲時查找某頂點的各鄰接點復雜度的為O(n),總復雜度O(n2); 當用鄰接表存儲時查找鄰接點復雜度為O(e),總復雜度為O(n+e)7.4.3 最小生成樹P173假設要在 n 個城市之間建立通訊聯(lián)絡網，不同城市間建立通訊設施的代價不同，如何在最節(jié)省經費的前提下建立這

28、個通訊網？即找權值之和最小的極小連通子網，問題轉換為在連通網中找一顆生成樹，最小生成樹abcdegf195141827168213ae12dcbgf7148531621Kruaskal算法:找權值最小的邊,若并入后構成回路則舍棄Kruskal算法求最小生成樹：設N=(V,E)是連通網,求最小生成樹令T=(V,),各頂點自成一連通分量在E中找代價最小的邊,若該邊的頂點落在不同連通分量上，則將其并入,依次類推至所有頂點到一個連通分量上總O(eloge)，與n無關，適合稀疏圖abcdegf195141827168213ae12dcbgf71485316217121819Kruskal算法是逐條邊并入

29、，檢查是否構成回路；Prim算法是逐個頂點并入，根據(jù)并入頂點找最小邊；普里姆Prim算法求最小生成樹：abcdegf195141827168213ae12dcb7aaa1914180e12ee8160d3dd7210c50e0gd0f0設U代表已并入最小生成樹中的頂點的集合，最初任選一點放入U。之后找U到U最小邊，將對應新頂點并入，共N-1輪即可從頂點u0開始,令U=u0, 初始化u0到其余各頂點距離找最小的邊輸出,并入新頂點,賦0+更新表使U到非U距離更小。如上重復n-1次構造下表對應的數(shù)組,每個元素對應一個頂點,元素取值是U中到當前點最近的點和邊的權值,頂點被并入U后權值置0struct

30、VertexType adjvex; /中到當前點最近的點名稱 VRType lowcost; /中點到當前點的最小代價closedgeMAX_VERTEX_NUM;aaa191418void MiniSpanTree_Prim(MGraph G, VertexType u) /用普里姆算法從u出發(fā)求網G(鄰接矩陣表示) 最小生成樹,輸出各邊 k=LocateVex (G, u); closedgek.lowcost = 0; /將u并入U,賦0 for ( j=0; jG.vexnum;+j ) /據(jù)u更新數(shù)組元素代價 if (j!=k)closedgej = u, G.arcskj.adj

31、 ; for (i=1; ik closedgek.lowcost=0; /將k號結點并入U，賦0 for(j=0;jG.vexnum;+j)/據(jù)k號結點更新數(shù)組元素代價 if (G.arcskj.adjclosedgej.lowcost） closedgej=G.vexsk,G.arcskj.adj; 將初始點u并入U,初始化表;之后找小邊并入,賦0+更新重復復雜度為O(n2),與邊數(shù)無關，適合稠密圖作業(yè)：7.7prim算法注意畫表，多張Kruscal算法，手工執(zhí)行，直接給答案abcdegf195141827168213ae12dcbgf71485316217121819強連通圖,強連通分量

32、 (有向圖) （1）各頂點的入/出度；（2）鄰接矩陣；（3）鄰接表、逆鄰接表、十字鏈表（4）強連通分量；1245361 4230 12 A B C D E鄰接表畫法:頭結點兩成員，是數(shù)組； 弧結點中存在的是下標，此例要減17.5.1 拓撲排序AOV-網:頂點表示活動,弧表示活動間先后(依賴)關系的有向圖.AOV-網用以表示工程或系統(tǒng)的施工計劃，可據(jù)此判斷工程是否可以順利進行AOV-網中應存在一個覆蓋全部頂點的序列(全序),在該序列中頂點出現(xiàn)的順序滿足網中的先后關系(偏序)。一個全序就對應一個合法的完整工序BDACBDAC由某個集合上的一個偏序得到該集合上的一個全序,該操作稱為拓撲排序。若得到一

33、個含全部頂點的拓撲有序序列(全序)則說明工程可順利開展,不存在則說明圖中存在有向回路,不合理何謂拓撲排序BDACABCD或ACBD均是含全部頂點的拓撲有序序列(DAG圖)BDAC不存在含全部頂點的拓撲有序序列, 存在有向回路BCDB從有向圖中選取一沒有前驅的頂點并輸出之；重復上述兩步，至圖空(得一全序)或圖不空但不存在無前驅的頂點(得一有向環(huán))。從圖中“刪除”此頂點及所有從其出發(fā)的弧如何進行拓撲排序abcghdfeabchdgfeBDACA入度0頂點入棧,刪除(出棧并據(jù)此更新入度),零入度者入棧重復至?？?，若彈出的元素個數(shù)小于頂點數(shù)則說明存在回路，計劃不合理3、拓撲排序算法的實現(xiàn)Status

34、TopologicalSort(ALGraph G)/G用鄰接表存儲,若G無回路則輸出拓撲有序序列,返OK, 否則返ERROR. FindInDegree(G,indegree);/求各頂點入度存入數(shù)組indegree InitStack(S); for(i=0;iG.vexnum;+i) if(!indegreei) Push(s,i); count=0; /用以對輸出的頂點進行計數(shù) while (!StackEmpty(S) Pop(S,i); printf(G.verticesi.data); +count; if(countnextarc) k=p-adjvex; - -indegre

35、ek; /更新入度 if(!indegreek) Push(S,w);/新入度為零的頂點入棧 最初求入度O(n+e); 第一波頂點入棧O(n)；若為DAG圖則每個頂點入棧、出棧各一次,O(n);入度減1的操作執(zhí)行e次,故總復雜的度O(n+e)入度0頂點入棧,刪除(出棧并據(jù)此更新入度),零入度者入棧重復至?？眨魪棾龅脑貍€數(shù)小于頂點數(shù)則說明存在回路，計劃不合理作業(yè)：9 執(zhí)行教材中的拓撲排序算法，寫出得到的拓撲有序序列7.5.2 關鍵路徑AOE網：頂點表示狀態(tài)，弧表示活動，弧權表示完成活動所需時間。用以估算工程的完成時間問:最短工期多長？哪些活動是影響工期的“關鍵活動”abcdefghk6452

36、1187244源點匯點174關鍵路徑(長度最長的路徑)決定工期關鍵活動:工程正常開展最早開始時間等于最遲開始時間的活動ee(act) =ve(頭) 與 el(act)=vl(尾) - dur(act)ve(源點)=0.對普通頂點v,設W為其前驅頂點集則ve(v)=max ve(w)+dut(w,v) | wW 如何保證求ve(v)時ve(w)已經求出？關鍵活動求取求各點最早到達時間ve(x)abcdefghk64521187244作法:各頂點ve初始化為0,找無前驅頂點,據(jù)其ve值更新后繼ve值, “刪除”如此重復,至圖空或發(fā)現(xiàn)回路.實際是按拓撲序00000000064571157151418

37、abcdefghk64521187244找無前驅頂點,據(jù)其ve值更新后繼ve, “刪除”重復也可先寫出拓撲序列，后據(jù)序列求:a - d - f - c - b - e - h - g - kStatus TopologicalOrder(ALGraph G，Stack &T)/求個頂點最早到達時間計入全局數(shù)組ve,T按訪問順序存儲各頂點,求vl用 ve0.G.vexnum-1=0; FindInDegree(G,indegree); InitStack(S); InitStack T; for(i=0;inextarc) k=p-adjvex; -indegree(k); if(indegre

38、ek= =0) Push(S, w); if(vej+*(p-info)vek)vek=vej+*(p-info) if(countnextarc) k=p-adjvex; dut=*(p-info); /對應活動的持續(xù)時間 if( vlk-dut vlj ) vlj= vlk-dut; for(j=0;jnextarc) k=p-adjvex; dut=*(p-info); ee=vej; el=vlk-dut/活動的最早/遲開始時間 if(ee=el) printf(j,k,dut,ee,el, ); else printf(j,k,dut,ee,el, ); 06457715141818

39、1416107866000064577715141416023668871002302630266302866302886630278866302107886630216107886630214161078866302ee作業(yè)題1：7.10 求關鍵活動a - d - f - c - b - e - h - g - kabcdefghk6452118724417400000000064571157151418181818181818181818161486610807回顧：06457715141818141610786600006457771514141602366887100230263026

40、6302866302886630278866302107886630216107886630214161078866302ee單源最短路徑每一對頂點之間的最短路徑7.6 最短路徑（P187）集合S存放已找到最短路的頂點將源并入S,初始化源到V-S中各頂點的最短路徑在V-S中找長度最小的頂點并入S,據(jù)此更新再找再更新,共重復n-1輪v0v1v2v4v5100301050510v36020終點路徑長度v0v0-v00v1V2v0-v210V3V4v0-v430V5v0-v5100終點路徑長度v0v0-v00v1V2v0-v210V3v0v2v360V4v0-v430V5v0-v5100終點路徑距離

41、v0v0-v00v1V2v0-v210V304350V4v0-v430V5045907.6.1單源最短路徑-Dijkstra算法迪杰斯特拉算法實現(xiàn)：設輔助數(shù)組D,Dk存儲當前所得從源到頂點k的最短路長度finalk標記k號頂點已并入SPvw標記源到v的最短路上w是否出現(xiàn)for(v=0;vG.vexnum;+v) finalv=FALSE;/最初未得源點v0到v的最短路 for(w=0;wG.vexnum;+w) pvw=FALSE;/最短路最初為空,不含任何頂點 Dv=G.arcsv0v; /根據(jù)v0更新 if(Dvv00v1V2v0-v210V3V4v0-v430V5v0-v5100每次循環(huán)

42、都找距離最小未并入的頂點并入S，更新，重復n-1輪終點路徑距離v0v0-v00v1V2v0-v210V3V4v0-v430V5v0-v5100v0v1v2v4v5100301050510v36020for(i=1;iG.vexnum;+i) min=INFINITY; for(w=0;wG.vexnum;+w) if(!finalw&Dwmin) v=w; min=Dw finalv=TRUE; for(w=0;wG.vexnum;+w) if( !finalw & (min+G.arcsvw)v00v1V2v0-v210V3v0v2v360V4v0-v430V5v0-v5100迪杰斯特拉算法

43、的實現(xiàn) for(i=1;iG.vexnum;+i)/重n-1輪,每輪找最小的,并入更新 min=INFINITY; for(w=0;wG.vexnum;+w) if(!finalw&Dwmin) v=w; min=Dw finalv=TRUE; for(w=0;wG.vexnum;+w) if( !finalw & (min+G.arcsvwDw) ) Dw= min+G.arcsvw; Pw0.G.vexnum=Pv0.G.vexnum;Pww=TRUE; /復雜度O(n2),單源單終點問題也是O(n2)void ShortestPath_DIJ(MGraph G,int v0,PathMa

44、trix &P,ShortPathTable &D) for(v=0;vG.vexnum;+v) /初始化數(shù)組，并入v0并更新 finalv=FALSE; for(w=0;wG.vexnum;+w) pvw=FALSE; Dv=G.arcsv0v; if(DvInFINITY)pvv0=TRUE;pvv=TRUE; Dv0=0; finalv0=0;7.6.2 任意一對頂點間的最短路徑每次以一個頂點為源點調用Dijkstra算法，復雜度O(n3)Floyd算法(復雜度同，但形式簡單):D(k)ij表示從i頂點到j頂點的“某些”路徑中最短路徑的長度，這些路徑中，內部各頂點的標號不超過kD(-1)

45、ij表示i直接到j(內部無頂點)的情況,值G.arcsijD(0)ij意味著i到j中間可含0號頂點;D(2)ij意味著i到j中間可含0、1、2號頂點; D(n-1)ij意味著什么？D(k)ij=minD(k-1)ij , D(k-1)ik+D(k-1)kj ACB461132Floyd算法求任意頂點間的最短路ACB461132D(k)ijk=-1,0,1,2P(k)ijk=-1,0,1,2D(-1)ij=G.arcsijD(k)ij=minD(k-1)ij, D(k-1)ik+D(k-1)kj . k=0,1,n-1Piju表示i到j最短路中u號頂點是否出現(xiàn)765Floyd算法void ShortestPath_FLOYD(MGraph G, PathMatrix &Pnnn,DistancMatrix &D) /初始化D(-1)與P(-1) for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j) Dij=G.arcsij; if(DijG.vexnum-1 for(k=0;kG.vexnum;+k) for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j) if(Dik+