數(shù)據(jù)結(jié)構(gòu)圖總結(jié)實用教案

1、圖 圖的基本概念 圖的存儲表示 圖的遍歷與連通性 最小生成樹 最短路徑 活動(hu dng)網(wǎng)絡(luò) 第1頁/共116頁第一頁，共116頁。第2頁/共116頁第二頁，共116頁。00001111222265433 第3頁/共116頁第三頁，共116頁。0123子圖子圖0130123023第4頁/共116頁第四頁，共116頁。第5頁/共116頁第五頁，共116頁。012301230123第6頁/共116頁第六頁，共116頁。第7頁/共116頁第七頁，共116頁。class Graph public: Graph ( ); void InsertVertex ( Type & vertex )

2、; void InsertEdge ( int v1, int v2, int weight ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 ); int IsEmpty ( ); Type GetWeight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); 第8頁/共116頁第八頁，共116頁。, , ( , ) . , 1A0i jEi jEEdge i jiforiforo

3、therwiseotherwise第9頁/共116頁第九頁，共116頁。第10頁/共116頁第十頁，共116頁。10( ). njOD iAEdge ij10( ). nkID jAEdge kj第11頁/共116頁第十一頁，共116頁。( , ),() ,(), WEEA.edgeEE0i jiji, ji, jijiji, ji, jij若若且且或或若若且且或或若若63129542031014092A.edge3508608第12頁/共116頁第十二頁，共116頁。ABCDdata adjABCD0123dest linkdest link 130210 第13頁/共116頁第十三頁，共1

4、16頁。ABCdata adjABC012dest linkdest link data adjABC012dest link102 011 第14頁/共116頁第十四頁，共116頁。BACD9528data adjABCD0123dest cost link 1 53 62 83 21 96第15頁/共116頁第十五頁，共116頁。第16頁/共116頁第十六頁，共116頁。 mark vertex1 vertex2 path1 path2 第17頁/共116頁第十七頁，共116頁。 第18頁/共116頁第十八頁，共116頁。 第19頁/共116頁第十九頁，共116頁。 mark vertex

5、1 vertex2 path1 path2第20頁/共116頁第二十頁，共116頁。 data Firstin Firstout第21頁/共116頁第二十一頁，共116頁。mark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE第22頁/共116頁第二十二頁，共116頁。 在有向圖的十字鏈表中，從頂點結(jié)點( ji din)的firstout指針域出發(fā)，沿邊結(jié)點( ji din)中的path1域的鏈一直走到底正好是原來的鄰接表結(jié)構(gòu)。統(tǒng)計鏈中邊結(jié)點( ji di

6、n)的個數(shù)可求得該頂點的出度。 從頂點結(jié)點( ji din)的firstin指針域出發(fā)，沿邊結(jié)點( ji din)中的path2域的鏈一直走到底正好是原來的逆鄰接表結(jié)構(gòu)。統(tǒng)計鏈中邊結(jié)點( ji din)的個數(shù)可求得該頂點的入度。第23頁/共116頁第二十三頁，共116頁。第24頁/共116頁第二十四頁，共116頁。第25頁/共116頁第二十五頁，共116頁。第26頁/共116頁第二十六頁，共116頁。ACDEGBFIHACDEGBFIH123456789123456789前進(qinjn)回退深度優(yōu)先搜索過程深度優(yōu)先搜索過程 深度優(yōu)先生成樹深度優(yōu)先生成樹第27頁/共116頁第二十七頁，共116

7、頁。template void Graph :DFS ( ) int * visited = new int NumVertices; for ( int i = 0; i NumVertices; i+ ) visited i = 0; /訪問數(shù)組訪問數(shù)組 visited 初始化初始化 DFS (0, visited ); /從頂點從頂點(dngdin)0出發(fā)開始搜索出發(fā)開始搜索 delete visited; /釋放釋放 visited 第28頁/共116頁第二十八頁，共116頁。template void Graph :DFS ( const int v, int visited ) c

8、out GetValue (v) ; /訪問頂點訪問頂點(dngdin) v visitedv = 1; /頂點頂點(dngdin) v 作作訪問標記訪問標記 int w = GetFirstNeighbor (v); /取取 v 的第一個鄰接頂點的第一個鄰接頂點(dngdin) w while ( w != -1 ) /若鄰接頂點若鄰接頂點(dngdin) w 存在存在 if ( !visitedw ) DFS ( w, visited ); /若頂點若頂點(dngdin) w 未訪問過未訪問過, 遞歸訪問頂點遞歸訪問頂點(dngdin) w w = GetNextNeighbor ( v,

9、 w ); /取頂點取頂點(dngdin) v 排在排在 w 后的下一個鄰接頂后的下一個鄰接頂點點(dngdin) 第29頁/共116頁第二十九頁，共116頁。Avisited0=1w=1DFS(1,visited)w=3DFS(3,visited)w=-1Bvisited1=1w=0w=2DFS(2,visited)w=-1Cvisited2=1w=1w=-1Dvisited3=1w=0w=-1DFS（0，visited）ABCD0123第30頁/共116頁第三十頁，共116頁。ACDEGBFIHACDEGBFH123456789123456789廣度優(yōu)先搜索過程廣度優(yōu)先搜索過程(guchn

10、g) 廣度優(yōu)先生成樹廣度優(yōu)先生成樹I第31頁/共116頁第三十一頁，共116頁。第32頁/共116頁第三十二頁，共116頁。第33頁/共116頁第三十三頁，共116頁。template void Graph :BFS ( int v ) int * visited = new intNumVertices; for ( int i = 0; i NumVertices; i+ ) visitedi = 0; /visited初始化初始化 cout GetValue (v) ; visitedv = 1; Queue q; q.EnQueue (v); /進隊列進隊列 while ( !q.Is

11、Empty ( ) ) /隊空搜索結(jié)束隊空搜索結(jié)束 v = q.DeQueue ( ); int w = GetFirstNeighbor (v); while ( w != -1 ) /若鄰接頂點若鄰接頂點 w 存在存在 if ( !visitedw ) /未訪問過未訪問過 cout GetValue (w) ; visitedw = 1; q.EnQueue (w); w = GetNextNeighbor (v, w); /內(nèi)層內(nèi)層(ni cn)while循環(huán)重復(fù)檢測循環(huán)重復(fù)檢測 v 的所有鄰接的所有鄰接頂點頂點 /外層外層while循環(huán)，判隊列空否循環(huán)，判隊列空否 delete vis

12、ited; 第34頁/共116頁第三十四頁，共116頁。例子(l zi) 給出下圖從頂點1出發(fā)進行深度優(yōu)先搜索得到(d do)的深度優(yōu)先生成樹 給出下圖從頂點2出發(fā)進行廣度優(yōu)先搜索得到(d do)的廣度優(yōu)先生成樹第35頁/共116頁第三十五頁，共116頁。第36頁/共116頁第三十六頁，共116頁。第37頁/共116頁第三十七頁，共116頁。ACDEIBFOGHJNMLK非連通(lintng)無向圖AHKCDEIBFOGJNML非連通(lintng)圖的連通(lintng)分量第38頁/共116頁第三十八頁，共116頁。ABCDEFGHIJKLMNO0123456789101112131443

13、2150065064154989787131211141014101012110ACDEBFGIHJONMLK非連通無向(w xin)圖的鄰接表表示第39頁/共116頁第三十九頁，共116頁。template void Graph :Components ( ) int *visited = new intNumVertices; for ( int i = 0; i NumVertices; i+ ) visitedi = 0; /visited 初始初始化化 for ( i = 0; i NumVertices; i+ ) if ( !visitedi ) /檢測頂點是否檢測頂點是否(sh

14、 fu)訪問過訪問過 DFS ( i, visited ); /未訪問未訪問, 出發(fā)訪問出發(fā)訪問 OutputNewComponent ( ); /連通分量連通分量 delete visited; 第40頁/共116頁第四十頁，共116頁。第41頁/共116頁第四十一頁，共116頁。第42頁/共116頁第四十二頁，共116頁。10504613228102514242216181250461325046132原圖(yun t) (a) (b)第43頁/共116頁第四十三頁，共116頁。1012504613228102514242216181250461325046132101412原圖(yun

15、t) (c) (d)504613210141612(e) (f) (g)504613210142216125046121025142216123第44頁/共116頁第四十四頁，共116頁。 tail head cost 邊的兩個頂點位置 邊的權(quán)值第45頁/共116頁第四十五頁，共116頁。第46頁/共116頁第四十六頁，共116頁。const int MAXNUM = 機器可表示的機器可表示的, 問題問題中中 不可能不可能(knng)出現(xiàn)的大數(shù)出現(xiàn)的大數(shù)class MinSpanTree;/最小生成樹的前視類最小生成樹的前視類聲明聲明class MSTEdgeNode /生成樹邊結(jié)點生成樹邊結(jié)

16、點類類friend class MinSpanTree;private: int tail, head; /生成樹各邊的兩生成樹各邊的兩頂點頂點 float cost; /生成樹各邊的權(quán)值生成樹各邊的權(quán)值public: MSTEdgeNode ( ) /構(gòu)造函數(shù)構(gòu)造函數(shù) : tail ( -1 ), head ( -1 ), cost ( 0 ) ；第47頁/共116頁第四十七頁，共116頁。class MinSpanTree protected: MSTEdgeNode * edgevalue;/邊值數(shù)組 int MaxSize, n;public: MinSpanTree ( int sz

17、 = NumVertices-1 ) : MaxSize(sz), n (0) /數(shù)組最大元素(yun s)個數(shù)和當前個數(shù) edgevalue = new MSTEdgeNodeMaxSize; int Insert ( MSTEdgeNode& item );第48頁/共116頁第四十八頁，共116頁。void Graph :Kruskal ( MinSpanTree& T ) MSTEdgeNode e; /邊結(jié)點輔助單元邊結(jié)點輔助單元 MinHeap H( NumEdges ); int NumVertices = VerticesList.last; /頂點頂點(dng

18、din)數(shù)數(shù) UFSets F ( NumVertices ); /并查集并查集 for ( int u = 0; u NumVertices; u+ ) for ( int v = u +1; v NumVertices; v+ ) if ( Edgeuv != MAXNUM ) e.tail = u; e.head = v; /插入堆插入堆 e.cost = Edgeuv; H.Insert (e); 第49頁/共116頁第四十九頁，共116頁。int count = 1; /最小生成樹加入邊數(shù)計數(shù)最小生成樹加入邊數(shù)計數(shù) while ( count NumVertices ) H.Remo

19、veMin ( e ); /從堆中退出一條邊從堆中退出一條邊 u = F.Find ( e.tail ); /檢測兩端點的根檢測兩端點的根 v = F.Find ( e.head ); if ( u != v ) /根不在同一連通分量根不在同一連通分量(fn ling) F.Union ( u, v ); /合并合并 T.Insert ( e ); /該邊存入最小生成樹該邊存入最小生成樹 count+; 第50頁/共116頁第五十頁，共116頁。并查集鄰接矩陣表示(biosh)-2-2-2-2-1-1-1-1-1 -1-1-1 -1-1-1-102-1-1-10-2200000 1 2 3 4

20、 5 6-21-11-2-1-421-2 -51211-711211F 0 1 2 3 4 5 6 0 28 10 028 0 16 14 1 16 0 12 2 12 0 22 18 3 22 0 25 24 410 25 0 5 14 18 24 0 65046132281025142422161812第51頁/共116頁第五十一頁，共116頁。Kruskal的算法(sun f)復(fù)雜度 建立( jinl)最小堆檢測鄰接矩陣O(n2) e次堆插入操作O(elog2e) e次出堆操作O(elog2e) 2e次并查集find操作O(elog2n) n-1次union操作O(n) 復(fù)雜度為O(el

21、og2e+elog2n+n2+n)第52頁/共116頁第五十二頁，共116頁。例子(l zi) 采用kruskal算法求下圖的最小生成樹，并給出求解(qi ji)過程中堆，并查集和最小生成樹的變化1234567111095786第53頁/共116頁第五十三頁，共116頁。1234567111095786建最小堆建最小堆第54頁/共116頁第五十四頁，共116頁。1234567111095786建最小堆建最小堆第55頁/共116頁第五十五頁，共116頁。并查集并查集第56頁/共116頁第五十六頁，共116頁。并查集并查集第57頁/共116頁第五十七頁，共116頁。31-6335123456并查集

22、并查集第58頁/共116頁第五十八頁，共116頁。1234567957631-63350123456第59頁/共116頁第五十九頁，共116頁。第60頁/共116頁第六十頁，共116頁。252510504613228102514242216185046132504613210原圖(yun t) (a) (b)504613210(c) (d) (e) (f)50461321022125046121025142216123252212第61頁/共116頁第六十一頁，共116頁。5046132281025142422161812028102801614160121202218220252410250

23、1418240第62頁/共116頁第六十二頁，共116頁。0 28 10 - -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 602810280161416012120221822025241025014182405046132281025142422161812第63頁/共116頁第六十三頁，共116頁。第64頁/共116頁第六十四頁，共116頁。0 28 10 - -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 6選選 v=5選邊選邊 (0,5)028102801614160121202218220252410250141

24、8240第65頁/共116頁第六十五頁，共116頁。頂點頂點v=5加入加入(jir)生成樹頂點集合：生成樹頂點集合：0 28 25 10 - -1 0 0 0 5 - -1 0 lowcostnearvex0 1 2 3 4 5 6選選 v=4選邊選邊 (5,4)50461322810251424221618原圖 邊 (0,5,10) 加入(jir)生成樹1204613210255第66頁/共116頁第六十六頁，共116頁。0 1 2 3 4 5 6頂點頂點v=4加入加入(jir)生成樹頂點集合：生成樹頂點集合：0 28 22 25 10 24 - -1 0 0 4 - -1 - -1 4 l

25、owcostnearvex選選 v=3選邊選邊 (4,3)50461322810251424221618原圖(yun t) 邊 (5,4,25) 加入生成樹125046132102522第67頁/共116頁第六十七頁，共116頁。頂點頂點(dngdin)v=3加入生成樹頂點加入生成樹頂點(dngdin)集合：集合：0 28 12 22 25 10 18 - -1 0 3 - -1 - -1 - -1 3 lowcostnearvex0 1 2 3 4 5 6選選 v=2選邊選邊 (3,2)50461322810251424221618原圖 邊 (4,3,22) 加入(jir)生成樹125046

2668頁/共116頁第六十八頁，共116頁。lowcostnearvex0 1 2 3 4 5 6頂點頂點(dngdin)v=2加入生成樹頂點加入生成樹頂點(dngdin)集合：集合：0 16 12 22 25 10 18 - -1 2 - -1 - -1 - -1 - -1 3 選選 v=1選邊選邊 (2,1)50461322810251424221618原圖(yun t) 邊 (3,2,12) 加入生成樹125041321025221612第69頁/共116頁第六十九頁，共116頁。頂點頂點v=1加入加入(jir)生成樹頂點集合：生成樹頂點集合：0 16 12 22

27、25 10 14 - -1 - -1 - -1 - -1 - -1 - -1 1 lowcostnearvex0 1 2 3 4 5 6選選 v=6選邊選邊 (1,6)50461322810251424221618原圖 邊 (2,1,16) 加入(jir)生成樹125046132102514221612第70頁/共116頁第七十頁，共116頁。lowcostnearvex0 1 2 3 4 5 6頂點頂點v=6加入生成樹頂加入生成樹頂(sh dn)點集合：點集合：0 16 12 22 25 10 14 - -1 - -1 - -1 - -1 - -1 - -1 - -1 50461322810

28、251424221618原圖(yun t) 邊 (1,6,14) 加入生成樹125046132102514221612第71頁/共116頁第七十一頁，共116頁。第72頁/共116頁第七十二頁，共116頁。void Graph :Prim ( MinSpanTree &T ) int NumVertices = VerticesList.last; /頂點數(shù)頂點數(shù) float * lowcost = new floatNumVertices; int * nearvex = new intNumVertices; for ( int i = 1; i NumVertices; i+ )

29、 lowcosti = Edge0i; /頂點頂點0到各到各邊代價邊代價 nearvexi = 0; /及最短及最短帶權(quán)路徑帶權(quán)路徑 nearvex0 = -1; /加到生成加到生成(shn chn)樹頂點集合樹頂點集合 MSTEdgeNode e; /最小生成最小生成(shn chn)樹結(jié)點單元樹結(jié)點單元 第73頁/共116頁第七十三頁，共116頁。for ( i = 1; i NumVertices; i+ ) /循環(huán)循環(huán)n-1次次, 加入加入n-1條邊條邊 float min = MAXNUM; int v = 0; for ( int j = 0; j NumVertices; j+

30、) if ( nearvexj != -1 & lowcostj min ) v = j; min = lowcostj; /1 /求生成樹外頂點到生成樹內(nèi)頂點具有求生成樹外頂點到生成樹內(nèi)頂點具有(jyu)最最 /小權(quán)值的邊小權(quán)值的邊, v是當前具最小權(quán)值的邊是當前具最小權(quán)值的邊 if ( v ) /v=0表示再也找不到要表示再也找不到要求頂點求頂點 e.tail = nearvexv; e.head = v; e.cost = lowcostv; T.Insert (e); /選出的邊加入生成樹選出的邊加入生成樹 2 nearvexv = -1; /該邊加入生成該邊加入生成樹標記樹標

31、記 第74頁/共116頁第七十四頁，共116頁。 for ( j = 1; j NumVertices; j+ ) if ( nearvexj != -1 & Edgevj lowcostj ) lowcostj = Edgevj; /需要修改需要修改 3 nearvexj = v; /4 /end for循環(huán)循環(huán)(xnhun)n-1次次, 加入加入n-1條邊條邊第75頁/共116頁第七十五頁，共116頁。第76頁/共116頁第七十六頁，共116頁。第77頁/共116頁第七十七頁，共116頁。10432101003050206010長度長度v0 v1 (v0,v1) 10 v2 (v0

32、,v1,v2) (v0,v3,v2) ,60,50 v3 (v0,v3) 30 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100,90,60 第78頁/共116頁第七十八頁，共116頁。第79頁/共116頁第七十九頁，共116頁。轉(zhuǎn) 。第80頁/共116頁第八十頁，共116頁。Demo of Dijkstra algorithm041231050102060301000 10 30 100 0 50 0 10 20 0 60 0第81頁/共116頁第八十一頁，共116頁。How to get the path from vertex 0 (source) to

33、i (dest)? path4 = 2 path2 = 3 path3 = 0，The path is 0, 3, 2, 4，(from 0 to 4)第82頁/共116頁第八十二頁，共116頁。const int NumVertices = 6; /圖最大頂點(dngdin)個數(shù)class Graph /圖的類定義 private: float EdgeNumVerticesNumVertices; float distNumVertices; /最短路徑長度數(shù)組 int pathNumVertices; /最短路徑數(shù)組 int SNumVertices;/最短路徑頂點(dngdin)集pu

34、blic: void ShortestPath ( int, int ); int choose ( int ); 第83頁/共116頁第八十三頁，共116頁。void Graph : ShortestPath ( int n, int v )/Graph是一個具有是一個具有 n 個頂點的帶權(quán)有向圖個頂點的帶權(quán)有向圖, 各各/邊上的權(quán)值由邊上的權(quán)值由Edgeij給出。本算法給出。本算法(sun f)建立起建立起/一個數(shù)組一個數(shù)組: distj, 0 jn, 是當前求到的從頂是當前求到的從頂/點點 v 到頂點到頂點 j 的最短路徑長度的最短路徑長度, 同時用數(shù)組同時用數(shù)組/pathj, 0 jn

35、, 存放求到的最短路徑。存放求到的最短路徑。 for ( int i = 0; i n; i+) disti = Edgevi; /dist數(shù)組初始化數(shù)組初始化 Si = 0; if ( i != v & disti MAXNUM) pathi = v; else pathi = -1; /path數(shù)組初始化數(shù)組初始化 Sv = 1; distv = 0; /頂點頂點v加入頂點集合加入頂點集合 第84頁/共116頁第八十四頁，共116頁。/選當前不在集合選當前不在集合(jh)S中具有最短路徑的頂點中具有最短路徑的頂點u for ( i = 0; i n-1; i+ ) float mi

36、n = MAXNUM; int u = v; for ( int j = 0; j n; j+ ) if ( !Sj & distj min ) u = j; min = distj; Su = 1; /將頂點將頂點u加入集合加入集合(jh)S for ( int w = 0; w n; w+ ) /修改修改 if ( !Sw & Edgeuw MAXNUM & distu + Edgeuw distw ) /頂點頂點w未加入未加入S, 且通過且通過u可以縮短路徑可以縮短路徑 distw = distu + Edgeuw; pathw = u; /修改到修改到w的最短路

37、徑的最短路徑 第85頁/共116頁第八十五頁，共116頁。例子(l zi) 按Dijkstra算法計算( j sun)從頂點A到其他各頂點的最短路徑和最短路徑長度。ABCDE101855222第86頁/共116頁第八十六頁，共116頁。答案(d n)： 10 A-B-D 15 A-B-D-C 17 A-B-D-E 17第87頁/共116頁第八十七頁，共116頁。所有頂點(dngdin)之間的最短路徑 問題：已知一個各邊權(quán)值均大于0的帶權(quán)有向圖，對每一對頂點vivj，要求求出vi與vj之間的最短路徑和最短路徑長度。 算法思想： 如果利用一個二維數(shù)組存放頂點之間的最短路徑值，那么這個數(shù)組的最初狀態(tài)

38、就是圖的鄰接矩陣。即：Aij是vi與vj之間的最短路徑的長度。 如果存在一個k，且Aik+AkjAij，那么Aik+Akj應(yīng)該成為vi與vj之間的最短路徑的長度。 整個得Floyd算法的基本思想是：在原來(yunli)的鄰接矩陣的基礎(chǔ)上，依次用V0,V1.Vn-1試圖在vi與vj之間插入，減小Aij的值。第88頁/共116頁第八十八頁，共116頁。例如：原始例如：原始(yunsh)的從頂點的從頂點v2到到v1的距離為邊的距離為邊上的權(quán)值上的權(quán)值5，當加入中間頂點，當加入中間頂點v0后，邊后，邊上的權(quán)值之和上的權(quán)值之和4小于原來邊小于原來邊上的權(quán)值，上的權(quán)值，則以此新路徑則以此新路徑的長度頂點的

39、長度頂點v2到到v1的距離，并的距離，并修改相應(yīng)的矩陣元素。修改相應(yīng)的矩陣元素。第89頁/共116頁第八十九頁，共116頁。弗洛伊德算法(sun f)定義一個n階方陣序列：A(-1), A(0), A(n-1),其中(qzhng)：A(-1)ij=Edgeij；A(k)ij=minA(k-1)ij，A(k-1)ik+A(k-1)kj，k=0,1,n-1A(0)ij是從頂點vi到vj，中間頂點是v0的最短路徑長度， A(k)ij是從頂點vi到vj，中間頂點的序號不大于k的最短路徑的長度， A(n-1)ij是從頂點vi到vj的最短路徑長度。第90頁/共116頁第九十頁，共116頁。Example

40、of Floyd Algorithm第91頁/共116頁第九十一頁，共116頁。Example of Floyd Algorithm第92頁/共116頁第九十二頁，共116頁。Example of Floyd Algorithm第93頁/共116頁第九十三頁，共116頁。Example of Floyd Algorithm第94頁/共116頁第九十四頁，共116頁。Example of Floyd Algorithm第95頁/共116頁第九十五頁，共116頁。void Graph:AllLengths(int n)/Edgenn是鄰接矩陣，aij是頂點i和j之間的最短路徑長度(chngd)/p

41、athij是相應(yīng)路徑上頂點j的前一頂點的頂點號 for(int i=0; in; i+) for(int j=0; jn; j+) aij=Edgeij;/矩陣a初始化 if(ij&aijMAXNUM)pathij=i;/有路徑 else pathij=0;/i到j(luò)無路徑 for(int k=0; kn; k+)/產(chǎn)生a(k)及相應(yīng)的path(k) for(i=0; in; i+) for(j=0; jn; j+) if(aik+akjaij) aij=aik+akj; pathij=pathkj; /縮短路徑長度(chngd)，通過k到j(luò)第96頁/共116頁第九十六頁，共116頁。從

42、A(3)可知，頂點1到頂點0的最短路徑長度(chngd)為a10=11，在path(3)中對應(yīng)的最短路徑首先看path10=2，表示頂點0的前一個頂點是2，path12=3，表示頂點2的前一個頂點是3，path13=1，表示頂點3的前一個頂點是1，最后從頂點1到頂點3的最短路徑為。算法復(fù)雜度為O(n3)第97頁/共116頁第九十七頁，共116頁。些則不要求。這樣在有的課程之間有領(lǐng)先些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。關(guān)系，有的課程可以并行地學(xué)習(xí)。第98頁/共116頁第九十八頁，共116頁。第99頁/共116頁第九十九頁，共116頁。學(xué)生課程學(xué)生課程(kchng)學(xué)

43、習(xí)工程圖學(xué)習(xí)工程圖C8C3C5C4C9C6C7C1C2第100頁/共116頁第一百頁，共116頁。第101頁/共116頁第一百零一頁，共116頁。第102頁/共116頁第一百零二頁，共116頁。C8C3C5C4C9C6C7C1C2第103頁/共116頁第一百零三頁，共116頁。第104頁/共116頁第一百零四頁，共116頁。C0C1C2C3C4C5(a) 有向無環(huán)圖有向無環(huán)圖C2C5C1C0C3(b) 輸出輸出(shch)頂點頂點C4C1C2C5C3C4C0C2C5C1C3(c) 輸出輸出(shch)頂點頂點C0(d) 輸出頂點輸出頂點C3第105頁/共116頁第一百零五頁，共116頁。C1C2C5(e) 輸出輸出(shch)頂點頂點C2C5C1(f) 輸出輸出(shch)頂點頂點C1C5(g) 輸出輸出(shch)頂點頂點C5(h) 拓撲排序完成拓撲排序完成第106頁/共116頁第一百零六頁，共116頁。C0C1C2C3C4C5 C0