第9章图1.ppt

完整的克鲁斯卡尔算法应包括对边按权值递增排序，上述算法假设边已排序的情况下，时间复杂度为O(n2)。 如果给定的带权连通无向图G有e条边,n个顶点，采用堆排序(在第11章中介绍)对边按权值递增排序釆用并查集，那么用克鲁斯卡尔算法构造最小生成树的时间复杂度降为O(elog2e)。 由于它与n无关，只与e有关，所以说克鲁斯卡尔算法适合于稀疏图。 9.5 最短路径 9.5.1 路径的概念 在一个无权的图中,若从一顶点到另一顶点存在着一条路径,则称该路径长度为该路径上所经过的边的数目,它等于该路径上的顶点数减1。 由于从一顶点到另一顶点可能存在着多条路径,每条路径上所经过的边数可能不同,即路径长度不同,我们把路径长度最短(即经过的边数最少)的那条路径叫做最短路径,其路径长度叫做最短路径长度或最短距离。 对于带权的图,考虑路径上各边上的权值,则通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。 从源点到终点可能不止一条路径,把带权路径长度最短的那条路径称为最短路径,其路径长度(权值之和)称为最短路径长度或者最短距离。 9.5.2 从一个顶点到其余各顶点的最短路径 问题：给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径,并限定各边上的权值大于或等于0。 采用狄克斯特拉(Dijkstra)算法求解 基本思想是：设G=(V,E)是一个带权有向图, 把图中顶点集合V分成两组： 第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径v,…vk,就将vk加入到集合S中,直到全部顶点都加入到S中,算法就结束了) 第二组为其余未确定最短路径的顶点集合(用U表示)。 按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。 此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 狄克斯特拉算法的具体步骤如下： (1) 初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,U中顶点u距离为边上的权(若v与u有边v,u)或∞(若u不是v的出边邻接点)。 (2) 从U中选取一个距离v最小的顶点k,把k加入S中(该选定的距离就是v到k的最短路径长度)。 (3) 以k为新考虑的中间点,修改U中各顶点的距离：若从源点v到顶点u(u∈U)的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边k,u上的权。 (4) 重复步骤(2)和(3)直到所有顶点都包含在S中。 V到j的最小距离＝MIN(cvk+wkj,cvj) S U dist[] path[] 0 1 2 3 4 5 6 0 1 2 3 4 5 6 {0} {1,2,3,4,5,6} {0,4,6,6,∞,∞,∞} {0,0,0,0,-1,-1,-1} {0,1} {2,3,4,5,6} {0,4,5,6,11,∞,∞} {0,0,1,0,1,-1,-1} {0,1,2} {3,4,5,6} {0,4,5,6,11,9,∞} {0,0,1,0,1,2,-1} {0,1,2,3} {4,5,6} {0,4,5,6,11,9,15} {0,0,1,0,1,2,-1} {0,1,2,3,5} {4,6} {0,4,5,6,10,9,17} {0,0,1,0,5,2,5} {0,1,2,3,5,4} {6} {0,4,5,6,10,9,16} {0,0,1,0,5,2,4} {0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16} {0,0,1,0,5,2,4} void DFS(ALGraph *G,int v) { ArcNode