數(shù)據(jù)結(jié)構(gòu)圖總結(jié)PPT課件

1、圖 圖的基本概念 圖的存儲(chǔ)表示 圖的遍歷與連通性 最小生成樹(shù) 最短路徑 活動(dòng)網(wǎng)絡(luò) 第1頁(yè)/共116頁(yè)(vertex)： 第2頁(yè)/共116頁(yè)00001111222265433 第3頁(yè)/共116頁(yè)。0123子圖子圖0130123023第4頁(yè)/共116頁(yè)第5頁(yè)/共116頁(yè)012301230123第6頁(yè)/共116頁(yè)圖，在圖，在n個(gè)頂點(diǎn)的情形下，有個(gè)頂點(diǎn)的情形下，有n-1條邊。條邊。第7頁(yè)/共116頁(yè)class Graph public: Graph ( ); void InsertVertex ( Type & vertex ); void InsertEdge ( int v1, int v

2、2, 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頁(yè)/共116頁(yè), , ( , ) . , 1A0i jEi jEEdge i jiforiforotherwiseotherwise第9頁(yè)/共116頁(yè)第10頁(yè)/共116頁(yè)10( ).

3、njOD iAEdge ij10( ). nkID jAEdge kj第11頁(yè)/共116頁(yè)( , ),() ,(), WEEA.edgeEE0i jiji, ji, jijiji, ji, jij若若且且或或若若且且或或若若63129542031014092A.edge3508608第12頁(yè)/共116頁(yè)ABCDdata adjABCD0123dest linkdest link 130210 第13頁(yè)/共116頁(yè)ABCdata adjABC012dest linkdest link data adjABC012dest link102 011 第14頁(yè)/共116頁(yè)BACD9528data ad

4、jABCD0123dest cost link 1 53 62 83 21 96第15頁(yè)/共116頁(yè)第16頁(yè)/共116頁(yè) mark vertex1 vertex2 path1 path2 第17頁(yè)/共116頁(yè) 第18頁(yè)/共116頁(yè) 第19頁(yè)/共116頁(yè) mark vertex1 vertex2 path1 path2第20頁(yè)/共116頁(yè) data Firstin Firstout第21頁(yè)/共116頁(yè)mark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE第2

5、2頁(yè)/共116頁(yè) 在有向圖的十字鏈表中，從頂點(diǎn)結(jié)點(diǎn)的firstout指針域出發(fā)，沿邊結(jié)點(diǎn)中的path1域的鏈一直走到底正好是原來(lái)的鄰接表結(jié)構(gòu)。統(tǒng)計(jì)鏈中邊結(jié)點(diǎn)的個(gè)數(shù)可求得該頂點(diǎn)的出度。 從頂點(diǎn)結(jié)點(diǎn)的firstin指針域出發(fā)，沿邊結(jié)點(diǎn)中的path2域的鏈一直走到底正好是原來(lái)的逆鄰接表結(jié)構(gòu)。統(tǒng)計(jì)鏈中邊結(jié)點(diǎn)的個(gè)數(shù)可求得該頂點(diǎn)的入度。第23頁(yè)/共116頁(yè)第24頁(yè)/共116頁(yè)第25頁(yè)/共116頁(yè)第26頁(yè)/共116頁(yè)ACDEGBFIHACDEGBFIH123456789123456789前進(jìn)回退深度優(yōu)先搜索過(guò)程深度優(yōu)先搜索過(guò)程 深度優(yōu)先生成樹(shù)深度優(yōu)先生成樹(shù)第27頁(yè)/共116頁(yè)template void Gr

6、aph :DFS ( ) int * visited = new int NumVertices; for ( int i = 0; i NumVertices; i+ ) visited i = 0; /訪問(wèn)數(shù)組 visited 初始化 DFS (0, visited ); /從頂點(diǎn)0出發(fā)開(kāi)始搜索 delete visited; /釋放 visited 第28頁(yè)/共116頁(yè)template void Graph :DFS ( const int v, int visited ) cout GetValue (v) ; /訪問(wèn)頂點(diǎn) v visitedv = 1; /頂點(diǎn) v 作訪問(wèn)標(biāo)記 int

7、 w = GetFirstNeighbor (v); /取 v 的第一個(gè)鄰接頂點(diǎn) w while ( w != -1 ) /若鄰接頂點(diǎn) w 存在 if ( !visitedw ) DFS ( w, visited ); /若頂點(diǎn) w 未訪問(wèn)過(guò), 遞歸訪問(wèn)頂點(diǎn) w w = GetNextNeighbor ( v, w ); /取頂點(diǎn) v 排在 w 后的下一個(gè)鄰接頂點(diǎn) 第29頁(yè)/共116頁(yè)Avisited0=1w=1DFS(1,visited)w=3DFS(3,visited)w=-1Bvisited1=1w=0w=2DFS(2,visited)w=-1Cvisited2=1w=1w=-1Dvis

8、ited3=1w=0w=-1DFS（0，visited）ABCD0123第30頁(yè)/共116頁(yè)ACDEGBFIHACDEGBFH123456789123456789廣度優(yōu)先搜索過(guò)程廣度優(yōu)先搜索過(guò)程 廣度優(yōu)先生成樹(shù)廣度優(yōu)先生成樹(shù)I第31頁(yè)/共116頁(yè)第32頁(yè)/共116頁(yè)第33頁(yè)/共116頁(yè)template void Graph :BFS ( int v ) int * visited = new intNumVertices; for ( int i = 0; i NumVertices; i+ ) visitedi = 0; /visited初始化 cout GetValue (v) ; vis

9、itedv = 1; Queue q; q.EnQueue (v); /進(jìn)隊(duì)列 while ( !q.IsEmpty ( ) ) /隊(duì)空搜索結(jié)束 v = q.DeQueue ( ); int w = GetFirstNeighbor (v); while ( w != -1 ) /若鄰接頂點(diǎn) w 存在 if ( !visitedw ) /未訪問(wèn)過(guò) cout GetValue (w) ; visitedw = 1; q.EnQueue (w); w = GetNextNeighbor (v, w); /內(nèi)層內(nèi)層whilewhile循環(huán)循環(huán)重復(fù)檢測(cè) v v 的所有鄰接頂點(diǎn) /外層while循環(huán)，判

10、隊(duì)列空否 delete visited; 第34頁(yè)/共116頁(yè)例子 給出下圖從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先搜索得到的深度優(yōu)先生成樹(shù) 給出下圖從頂點(diǎn)2出發(fā)進(jìn)行廣度優(yōu)先搜索得到的廣度優(yōu)先生成樹(shù)第35頁(yè)/共116頁(yè)第36頁(yè)/共116頁(yè)第37頁(yè)/共116頁(yè)ACDEIBFOGHJNMLK非連通無(wú)向圖AHKCDEIBFOGJNML非連通圖的連通分量第38頁(yè)/共116頁(yè)ABCDEFGHIJKLMNO01234567891011121314432150065064154989787131211141014101012110ACDEBFGIHJONMLK非連通無(wú)向圖的鄰接表表示第39頁(yè)/共116頁(yè)template v

11、oid Graph :Components ( ) int *visited = new intNumVertices; for ( int i = 0; i NumVertices; i+ ) visitedi = 0; /visited 初始化 for ( i = 0; i NumVertices; i+ ) if ( !visitedi ) /檢測(cè)頂點(diǎn)是否訪問(wèn)過(guò) DFS ( i, visited ); /未訪問(wèn), 出發(fā)訪問(wèn) OutputNewComponent ( ); /連通分量 delete visited; 第40頁(yè)/共116頁(yè)第41頁(yè)/共116頁(yè)第42頁(yè)/共116頁(yè)1050461

12、3228102514242216181250461325046132原圖 (a) (b)第43頁(yè)/共116頁(yè)1012504613228102514242216181250461325046132101412原圖 (c) (d)504613210141612(e) (f) (g)504613210142216125046121025142216123第44頁(yè)/共116頁(yè) tail head cost 邊的兩個(gè)頂點(diǎn)位置 邊的權(quán)值第45頁(yè)/共116頁(yè)第46頁(yè)/共116頁(yè)const int MAXNUM = 機(jī)器可表示的機(jī)器可表示的, 問(wèn)題問(wèn)題中中 不可能出現(xiàn)的大數(shù)不可能出現(xiàn)的大數(shù)class MinS

13、panTree;/最小生成樹(shù)的前視類(lèi)最小生成樹(shù)的前視類(lèi)聲明聲明class MSTEdgeNode /生成樹(shù)邊結(jié)點(diǎn)類(lèi)friend class MinSpanTree;private: int tail, head; /生成樹(shù)各邊的兩頂點(diǎn) float cost; /生成樹(shù)各邊的權(quán)值public: MSTEdgeNode ( ) /構(gòu)造函數(shù) : tail ( -1 ), head ( -1 ), cost ( 0 ) ；第47頁(yè)/共116頁(yè)class MinSpanTree protected: MSTEdgeNode * edgevalue;/邊值數(shù)組 int MaxSize, n;public:

14、 MinSpanTree ( int sz = NumVertices-1 ) : MaxSize(sz), n (0) /數(shù)組最大元素個(gè)數(shù)和當(dāng)前個(gè)數(shù) edgevalue = new MSTEdgeNodeMaxSize; int Insert ( MSTEdgeNode& item );第48頁(yè)/共116頁(yè)void Graph :Kruskal ( MinSpanTree& T ) MSTEdgeNode e; /邊結(jié)點(diǎn)輔助單元 MinHeap H( NumEdges ); int NumVertices = VerticesList.last; /頂點(diǎn)數(shù) UFSets F

15、( 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頁(yè)/共116頁(yè)int count = 1; /最小生成樹(shù)加入邊數(shù)計(jì)數(shù) while ( count NumVertices ) H.RemoveMin ( e ); /從堆中退出一條邊 u = F.Find ( e.tail );

16、 /檢測(cè)兩端點(diǎn)的根 v = F.Find ( e.head ); if ( u != v ) /根不在同一連通分量 F.Union ( u, v ); /合并 T.Insert ( e ); /該邊存入最小生成樹(shù) count+; 第50頁(yè)/共116頁(yè)并查集鄰接矩陣表示-2-2-2-2-1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1-102-1-1-10-2200000 1 2 3 4 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

17、25 24 410 25 0 5 14 18 24 0 65046132281025142422161812第51頁(yè)/共116頁(yè)Kruskal的算法復(fù)雜度 建立最小堆檢測(cè)鄰接矩陣O(n2) e次堆插入操作O(elog2e) e次出堆操作O(elog2e) 2e次并查集find操作O(elog2n) n-1次union操作O(n) 復(fù)雜度為O(elog2e+elog2n+n2+n)第52頁(yè)/共116頁(yè)例子 采用kruskal算法求下圖的最小生成樹(shù)，并給出求解過(guò)程中堆，并查集和最小生成樹(shù)的變化1234567111095786第53頁(yè)/共116頁(yè)1234567111095786建最小堆建最小堆第54

18、頁(yè)/共116頁(yè)1234567111095786建最小堆建最小堆第55頁(yè)/共116頁(yè)并查集并查集第56頁(yè)/共116頁(yè)并查集并查集第57頁(yè)/共116頁(yè)31-6335123456并查集并查集第58頁(yè)/共116頁(yè)1234567957631-63350123456第59頁(yè)/共116頁(yè)第60頁(yè)/共116頁(yè)252510504613228102514242216185046132504613210原圖 (a) (b)504613210(c) (d) (e) (f)50461321022125046121025142216123252212第61頁(yè)/共116頁(yè)50461322810251424221618120

19、281028016141601212022182202524102501418240第62頁(yè)/共116頁(yè)0 28 10 - -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 602810280161416012120221822025241025014182405046132281025142422161812第63頁(yè)/共116頁(yè)第64頁(yè)/共116頁(yè)0 28 10 - -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 6選選 v=5選邊選邊 (0,5)0281028016141601212022182202524102501418

20、240第65頁(yè)/共116頁(yè)頂點(diǎn)頂點(diǎn)v=5加入生成樹(shù)頂點(diǎn)集合：加入生成樹(shù)頂點(diǎn)集合：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) 加入生成樹(shù)1204613210255第66頁(yè)/共116頁(yè)0 1 2 3 4 5 6頂點(diǎn)頂點(diǎn)v=4加入生成樹(shù)頂點(diǎn)集合：加入生成樹(shù)頂點(diǎn)集合：0 28 22 25 10 24 - -1 0 0 4 - -1 - -1 4 lowcostnearvex選選 v=3選邊選邊 (4,3)50461322810

21、251424221618原圖 邊 (5,4,25) 加入生成樹(shù)125046132102522第67頁(yè)/共116頁(yè)頂點(diǎn)頂點(diǎn)v=3加入生成樹(shù)頂點(diǎn)集合：加入生成樹(shù)頂點(diǎn)集合：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) 加入生成樹(shù)12504613210252212第68頁(yè)/共116頁(yè)lowcostnearvex0 1 2 3 4 5 6頂點(diǎn)頂點(diǎn)v=2加入生成樹(shù)頂點(diǎn)集合：加入生成樹(shù)頂點(diǎn)集合：0 16

22、12 22 25 10 18 - -1 2 - -1 - -1 - -1 - -1 3 選選 v=1選邊選邊 (2,1)50461322810251424221618原圖 邊 (3,2,12) 加入生成樹(shù)125041321025221612第69頁(yè)/共116頁(yè)頂點(diǎn)頂點(diǎn)v=1加入生成樹(shù)頂點(diǎn)集合：加入生成樹(shù)頂點(diǎn)集合：0 16 12 22 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) 加入生成樹(shù)125046

23、132102514221612第70頁(yè)/共116頁(yè)lowcostnearvex0 1 2 3 4 5 6頂點(diǎn)頂點(diǎn)v=6加入生成樹(shù)頂點(diǎn)集合：加入生成樹(shù)頂點(diǎn)集合：0 16 12 22 25 10 14 - -1 - -1 - -1 - -1 - -1 - -1 - -1 50461322810251424221618原圖 邊 (1,6,14) 加入生成樹(shù)125046132102514221612第71頁(yè)/共116頁(yè)(0, 5, 10), (5, 4, 25), (4, 3, 22),(3, 2, 12), (2, 1, 16), (1, 6, 14)第72頁(yè)/共116頁(yè)void Graph :Pr

24、im ( MinSpanTree &T ) int NumVertices = VerticesList.last; /頂點(diǎn)數(shù) float * lowcost = new floatNumVertices; int * nearvex = new intNumVertices; for ( int i = 1; i NumVertices; i+ ) lowcosti = Edge0i; /頂點(diǎn)0到各邊代價(jià) nearvexi = 0; /及最短帶權(quán)路徑 nearvex0 = -1; /加到生成樹(shù)頂點(diǎn)集合 MSTEdgeNode e; /最小生成樹(shù)結(jié)點(diǎn)單元 第73頁(yè)/共116頁(yè)for (

25、 i = 1; i NumVertices; i+ ) /循環(huán)n-1次, 加入n-1條邊 float min = MAXNUM; int v = 0; for ( int j = 0; j NumVertices; j+ ) if ( nearvexj != -1 & lowcostj min ) v = j; min = lowcostj; /1 /求生成樹(shù)外頂點(diǎn)到生成樹(shù)內(nèi)頂點(diǎn)具有最 /小權(quán)值的邊, v是當(dāng)前具最小權(quán)值的邊 if ( v ) /v=0表示再也找不到要求頂點(diǎn) e.tail = nearvexv; e.head = v; e.cost = lowcostv; T.Inse

26、rt (e); /選出的邊加入生成樹(shù) 2 nearvexv = -1; /該邊加入生成樹(shù)標(biāo)記 第74頁(yè)/共116頁(yè) for ( j = 1; j NumVertices; j+ ) if ( nearvex j != -1 & Edgev j lowcost j ) lowcost j = Edgev j; /需要修改 3 nearvex j = v; /4 /end for循環(huán)n-1次, 加入n-1條邊第75頁(yè)/共116頁(yè)第76頁(yè)/共116頁(yè)第77頁(yè)/共116頁(yè)10432101003050206010v0 v1 (v0,v1) 10 v2 (v0,v1,v2) (v0,v3,v2)

27、,60,50 v3 (v0,v3) 30 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100,90,60 第78頁(yè)/共116頁(yè)第79頁(yè)/共116頁(yè)對(duì)于每一個(gè)對(duì)于每一個(gè)i V- S ; 判斷：若判斷：若S = V, 則算法結(jié)束，否則轉(zhuǎn)則算法結(jié)束，否則轉(zhuǎn) 。第80頁(yè)/共116頁(yè)Demo of Dijkstra algorithm041231050102060301000 10 30 100 0 50 0 10 20 0 60 0第81頁(yè)/共116頁(yè)How to get the path from vertex 0 (source) to i (dest)? path4

28、 = 2 path2 = 3 path3 = 0，The path is 0, 3, 2, 4，(from 0 to 4)第82頁(yè)/共116頁(yè)const int NumVertices = 6; /圖最大頂點(diǎn)個(gè)數(shù)class Graph /圖的類(lèi)定義 private: float EdgeNumVerticesNumVertices; float distNumVertices; /最短路徑長(zhǎng)度數(shù)組 int pathNumVertices; /最短路徑數(shù)組 int SNumVertices;/最短路徑頂點(diǎn)集public: void ShortestPath ( int, int ); int c

29、hoose ( int ); 第83頁(yè)/共116頁(yè)void Graph : ShortestPath ( int n, int v )/Graph是一個(gè)具有 n 個(gè)頂點(diǎn)的帶權(quán)有向圖, 各/邊上的權(quán)值由Edgeij給出。本算法建立起/一個(gè)數(shù)組: distj, 0 jn, 是當(dāng)前求到的從頂/點(diǎn) v 到頂點(diǎn) j 的最短路徑長(zhǎng)度, 同時(shí)用數(shù)組/pathj, 0 jn, 存放求到的最短路徑。 for ( int i = 0; i n; i+) disti = Edgevi; /dist數(shù)組初始化 Si = 0; if ( i != v & disti MAXNUM) pathi = v; els

30、e pathi = -1; /path數(shù)組初始化 Sv = 1; distv = 0; /頂點(diǎn)v加入頂點(diǎn)集合 第84頁(yè)/共116頁(yè)/選當(dāng)前不在集合S中具有最短路徑的頂點(diǎn)u for ( i = 0; i n-1; i+ ) float min = MAXNUM; int u = v; for ( int j = 0; j n; j+ ) if ( !Sj & distj min ) u = j; min = distj; Su = 1; /將頂點(diǎn)u加入集合S for ( int w = 0; w n; w+ ) /修改 if ( !Sw & Edgeuw MAXNUM &

31、 distu + Edgeuw distw ) /頂點(diǎn)w未加入S, 且通過(guò)u可以縮短路徑 distw = distu + Edgeuw; pathw = u; /修改到w的最短路徑 第85頁(yè)/共116頁(yè)例子 按Dijkstra算法計(jì)算從頂點(diǎn)A到其他各頂點(diǎn)的最短路徑和最短路徑長(zhǎng)度。ABCDE101855222第86頁(yè)/共116頁(yè)答案： 10 A-B-D 15 A-B-D-C 17 A-B-D-E 17第87頁(yè)/共116頁(yè)所有頂點(diǎn)之間的最短路徑 問(wèn)題：已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有向圖，對(duì)每一對(duì)頂點(diǎn)vi vj，要求求出vi與vj之間的最短路徑和最短路徑長(zhǎng)度。 算法思想： 如果利用一個(gè)二維數(shù)組存放

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

33、v2到到v1的距離，并修改相應(yīng)的矩的距離，并修改相應(yīng)的矩陣元素。陣元素。第89頁(yè)/共116頁(yè)弗洛伊德算法定義一個(gè)n階方陣序列：A(-1), A(0), A(n-1),其中：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是從頂點(diǎn)vi到vj，中間頂點(diǎn)是v0的最短路徑長(zhǎng)度， A(k)ij是從頂點(diǎn)vi到vj，中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長(zhǎng)度， A(n-1)ij是從頂點(diǎn)vi到vj的最短路徑長(zhǎng)度。第90頁(yè)/共116頁(yè)Example of Floyd Algorithm第91頁(yè)/共116頁(yè)Example of Fl

34、oyd Algorithm第92頁(yè)/共116頁(yè)Example of Floyd Algorithm第93頁(yè)/共116頁(yè)Example of Floyd Algorithm第94頁(yè)/共116頁(yè)Example of Floyd Algorithm第95頁(yè)/共116頁(yè)void Graph:AllLengths(int n)/Edgenn是鄰接矩陣，aij是頂點(diǎn)i和j之間的最短路徑長(zhǎng)度/pathij是相應(yīng)路徑上頂點(diǎn)j的前一頂點(diǎn)的頂點(diǎn)號(hào) for(int i=0; in; i+) for(int j=0; jn; j+) aij=Edgeij;/矩陣a初始化 if(ij&aijMAXNUM)pat

35、hij=i;/有路徑 else pathij=0;/i到j(luò)無(wú)路徑 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; /縮短路徑長(zhǎng)度，通過(guò)k到j(luò)第96頁(yè)/共116頁(yè)從A(3)可知，頂點(diǎn)1到頂點(diǎn)0的最短路徑長(zhǎng)度為a10=11，在path(3)中對(duì)應(yīng)的最短路徑首先看path10=2，表示頂點(diǎn)0的前一個(gè)頂點(diǎn)是2，path12=3，表示頂點(diǎn)2的前一個(gè)頂點(diǎn)是3，path13=1，表示頂點(diǎn)3的前一個(gè)頂點(diǎn)是1，最后從頂點(diǎn)1到頂點(diǎn)3

36、的最短路徑為。算法復(fù)雜度為O(n3)第97頁(yè)/共116頁(yè)第98頁(yè)/共116頁(yè)第99頁(yè)/共116頁(yè)學(xué)生課程學(xué)習(xí)工程圖學(xué)生課程學(xué)習(xí)工程圖C8C3C5C4C9C6C7C1C2第100頁(yè)/共116頁(yè)第101頁(yè)/共116頁(yè)第102頁(yè)/共116頁(yè)C8C3C5C4C9C6C7C1C2第103頁(yè)/共116頁(yè) 第104頁(yè)/共116頁(yè)C0C1C2C3C4C5(a) 有向無(wú)環(huán)圖有向無(wú)環(huán)圖C2C5C1C0C3(b) 輸出頂點(diǎn)輸出頂點(diǎn)C4C1C2C5C3C4C0C2C5C1C3(c) 輸出頂點(diǎn)輸出頂點(diǎn)C0(d) 輸出頂點(diǎn)輸出頂點(diǎn)C3第105頁(yè)/共116頁(yè)C1C2C5(e) 輸出頂點(diǎn)輸出頂點(diǎn)C2C5C1(f) 輸出頂點(diǎn)輸出頂點(diǎn)C1C5(g) 輸出頂點(diǎn)輸出頂點(diǎn)C5(h) 拓?fù)渑判蛲瓿赏?/p>