数据结构图总结学习教案

1、数据结构数据结构(sh j ji u)图总结图总结第一页，共116页。 第1页/共116页第二页，共116页。y)表示从表示从 x 到到 y 的一条单向通路的一条单向通路, 它是有方向的。它是有方向的。第2页/共116页第三页，共116页。00001111222265433 第3页/共116页第四页，共116页。0123子图子图0130123023第4页/共116页第五页，共116页。vp2, , vpm，到达顶点，到达顶点(dngdin)vj。则称顶点。则称顶点(dngdin)序列序列 (vi vp1 vp2 . vpm vj) 为从为从顶点顶点(dngdin)vi 到顶点到顶点(dngdi

2、n) vj 的路径。它经过的的路径。它经过的边边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 应是属于应是属于E的边。的边。第5页/共116页第六页，共116页。012301230123第6页/共116页第七页，共116页。第7页/共116页第八页，共116页。class Graph public: Graph ( ); void InsertVertex ( Type & vertex ); void InsertEdge ( int v1, int v2, int weight ); void RemoveVertex ( int v ); void Remov

3、eEdge ( 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 jiforiforotherwiseotherwise第9页/共116页第十页，共116页。第10页/共116页第十一页，共116页。10( ). njOD iAEdge ij10( ). nkID

4、 jAEdge kj第11页/共116页第十二页，共116页。( , ),() ,(), WEEA.edgeEE0i jiji, ji, jijiji, ji, jij若若且且或或若若且且或或若若63129542031014092A.edge3508608第12页/共116页第十三页，共116页。ABCDdata adjABCD0123dest linkdest link 130210 第13页/共116页第十四页，共116页。ABCdata adjABC012dest linkdest link data adjABC012dest link102 011 第14页/共116页第十五页，共1

5、16页。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 vertex1 vertex2 path1 path2第20页/共116页第二十一页，共116页。 data Firstin Firstout第21页/共116页第二十二页，共116页。m

6、ark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE第22页/共116页第二十三页，共116页。的个数可求得该顶点的入度。第23页/共116页第二十四页，共116页。第24页/共116页第二十五页，共116页。第25页/共116页第二十六页，共116页。第26页/共116页第二十七页，共116页。ACDEGBFIHACDEGBFIH123456789123456789前进(qinjn)回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树第27

7、页/共116页第二十八页，共116页。发开始搜索发开始搜索(su su) delete visited; /释放释放visited 第28页/共116页第二十九页，共116页。第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页。ACDEGBFIHACDEGBFH1234567891

8、23456789广度优先广度优先(yuxin)搜索过程搜索过程 广度优先广度优先(yuxin)生成树生成树I第31页/共116页第三十二页，共116页。第32页/共116页第三十三页，共116页。第33页/共116页第三十四页，共116页。第34页/共116页第三十五页，共116页。第35页/共116页第三十六页，共116页。第36页/共116页第三十七页，共116页。第37页/共116页第三十八页，共116页。ACDEIBFOGHJNMLK非连通(lintng)无向图AHKCDEIBFOGJNML非连通(lintng)图的连通(lintng)分量第38页/共116页第三十九页，共116页。A

9、BCDEFGHIJKLMNO01234567891011121314432150065064154989787131211141014101012110ACDEBFGIHJONMLK非连通无向图的邻接(ln ji)表表示第39页/共116页第四十页，共116页。第40页/共116页第四十一页，共116页。络络(wnglu)中的中的 n 个顶点；个顶点；n不能使用产生回路的边；不能使用产生回路的边；n各边上的权值的总和达到最小。各边上的权值的总和达到最小。第41页/共116页第四十二页，共116页。条权值最小的边。如此重复下去条权值最小的边。如此重复下去, 直到所有顶点在同一个连通分量直到所有顶

10、点在同一个连通分量上为止上为止第42页/共116页第四十三页，共116页。10504613228102514242216181250461325046132原图(yun t) (a) (b)第43页/共116页第四十四页，共116页。1012504613228102514242216181250461325046132101412原图(yun t) (c) (d)504613210141612(e) (f) (g)504613210142216125046121025142216123第44页/共116页第四十五页，共116页。 tail head cost 边的两个顶点位置 边的权值第45页

11、/共116页第四十六页，共116页。第46页/共116页第四十七页，共116页。第47页/共116页第四十八页，共116页。第48页/共116页第四十九页，共116页。第49页/共116页第五十页，共116页。第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 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

12、 25 24 410 25 0 5 14 18 24 0 65046132281025142422161812第51页/共116页第五十二页，共116页。第52页/共116页第五十三页，共116页。1234567111095786第53页/共116页第五十四页，共116页。1234567111095786建最小堆建最小堆第54页/共116页第五十五页，共116页。1234567111095786建最小堆建最小堆第55页/共116页第五十六页，共116页。并查集并查集第56页/共116页第五十七页，共116页。并查集并查集第57页/共116页第五十八页，共116页。31-6335123456并查

13、集并查集第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页。504613228102514242216181202810280161416012120221822025241025

14、01418240第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)02810280161416012120221822025241025014

15、18240第65页/共116页第六十六页，共116页。顶点顶点(dngdin)v=5加入生成树顶点加入生成树顶点(dngdin)集合：集合：0 28 25 10 - -1 0 0 0 5 - -1 0 lowcostnearvex0 1 2 3 4 5 6选选 v=4选边选边 (5,4)50461322810251424221618原图(yun t) 边 (0,5,10) 加入生成树1204613210255第66页/共116页第六十七页，共116页。0 1 2 3 4 5 6顶点顶点(dngdin)v=4加入生成树顶点加入生成树顶点(dngdin)集合：集合：0 28 22 25 10 24

16、 - -1 0 0 4 - -1 - -1 4 lowcostnearvex选选 v=3选边选边 (4,3)50461322810251424221618原图(yun t) 边 (5,4,25) 加入生成树125046132102522第67页/共116页第六十八页，共116页。顶点顶点v=3加入生成加入生成(shn chn)树顶点集合：树顶点集合：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

17、) 加入(jir)生成树12504613210252212第68页/共116页第六十九页，共116页。lowcostnearvex0 1 2 3 4 5 6顶点顶点v=2加入生成树顶加入生成树顶(sh dn)点集合：点集合：0 16 12 22 25 10 18 - -1 2 - -1 - -1 - -1 - -1 3 选选 v=1选边选边 (2,1)50461322810251424221618原图 边 (3,2,12) 加入(jir)生成树125041321025221612第69页/共116页第七十页，共116页。顶点顶点v=1加入生成树顶加入生成树顶(sh dn)点集合：点集合：0 1

18、6 12 22 25 10 14 - -1 - -1 - -1 - -1 - -1 - -1 1 lowcostnearvex0 1 2 3 4 5 6选选 v=6选边选边 (1,6)50461322810251424221618原图(yun t) 边 (2,1,16) 加入生成树125046132102514221612第70页/共116页第七十一页，共116页。lowcostnearvex0 1 2 3 4 5 6顶点顶点(dngdin)v=6加入生成树顶点加入生成树顶点(dngdin)集合：集合：0 16 12 22 25 10 14 - -1 - -1 - -1 - -1 - -1 -

19、 -1 - -1 50461322810251424221618原图(yun t) 边 (1,6,14) 加入生成树125046132102514221612第71页/共116页第七十二页，共116页。第72页/共116页第七十三页，共116页。第73页/共116页第七十四页，共116页。第74页/共116页第七十五页，共116页。第75页/共116页第七十六页，共116页。nn Floyd算法算法第76页/共116页第七十七页，共116页。止。止。第77页/共116页第七十八页，共116页。10432101003050206010v0 v1 (v0,v1) 10 v2 (v0,v1,v2)

20、(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页。顶点顶点vx (vxV-S )的路径中的一的路径中的一条。条。n每次求得一条最短路径后每次求得一条最短路径后, 其终点其终点vk 加入集合加入集合S，然后对所有的，然后对所有的vi V-S，修改其，修改其 disti值。值。第79页/共116页第八十页，共116页。第80页/共116页第八十一页，共116页。Demo of Dijkstra algorithm041231050102060301

21、000 10 30 100 0 50 0 10 20 0 60 0第81页/共116页第八十二页，共116页。How to get the path from vertex 0 (source) to i (dest)? path4 = 2 path2 = 3 path3 = 0，The path is 0, 3, 2, 4，(from 0 to 4)第82页/共116页第八十三页，共116页。第83页/共116页第八十四页，共116页。第84页/共116页第八十五页，共116页。第85页/共116页第八十六页，共116页。ABCDE101855222第86页/共116页第八十七页，共116页

22、。第87页/共116页第八十八页，共116页。第88页/共116页第八十九页，共116页。例如：原始的从顶点例如：原始的从顶点v2到到v1的距离为边的距离为边上的权值上的权值5，当加入中间顶点当加入中间顶点v0后，边后，边上的权值之和上的权值之和4小于原小于原来边来边上的权值，则以此新路径上的权值，则以此新路径(ljng)的长度的长度顶点顶点v2到到v1的距离，并修改相应的矩阵元素。的距离，并修改相应的矩阵元素。第89页/共116页第九十页，共116页。(ljng)的长度，的长度， A(n-1)ij是从是从顶点顶点vi到到vj的最短路径的最短路径(ljng)长度。长度。第90页/共116页第九

23、十一页，共116页。Example 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页。第96页/共116页第九十七页，共116页。第97页/共116页第九十八页，共116页。第98页/共

24、116页第九十九页，共116页。第99页/共116页第一百页，共116页。学生课程学生课程(kchng)学习工程图学习工程图C8C3C5C4C9C6C7C1C2第100页/共116页第一百零一页，共116页。第101页/共116页第一百零二页，共116页。第102页/共116页第一百零三页，共116页。C8C3C5C4C9C6C7C1C2第103页/共116页第一百零四页，共116页。络中必存在有向环。络中必存在有向环。第104页/共116页第一百零五页，共116页。C0C1C2C3C4C5(a) 有向无环图有向无环图C2C5C1C0C3(b) 输出输出(shch)顶点顶点C4C1C2C5C3C4C0C2C5