最小生成树and最短路径.pdf

《最小生成树and最短路径.pdf》由会员分享，可在线阅读，更多相关《最小生成树and最短路径.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最小生成树最小生成树 andand 最短路径最短路径无独有偶，在两个学期的期末中两门不同的科目离散数学和数据结构中都谈到了图及其衍生的最小生成树、最短路径问题，并给出了相应的算法克鲁斯卡尔、普林、迪杰斯特拉、沃舍尔算法。这无疑是释放了一个很大的信号这些内容很重要。由于之前学离散数学时只要求在思想上理解，并没要求程序实现，所以学起来也挺吃力的。而现在来到了数据结构的课程上，我觉得还是有必要写写理解与体会，好让以后用起来没那么难。最小生成树最小生成树Minimum Spanning Tree,MSTMinimum Spanning Tree,MST 一个有 n 个结点的连通图的生成树是原图的极小极

2、小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。即是在原图上删除边，直到剩余n-1 条边，保证n 个结点连通且边的权值加起来最小。简单图示：简单图示：112325434MSTMST1122344克鲁斯卡尔克鲁斯卡尔KruskalKruskal算法算法克鲁斯卡尔算法从边的角度来解决问题，即在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。然而，图的存贮结构采用边集数组，且权值相等的边在数组中排列次序可以是任意的，该方法对于边数相比照较多的图不是很实用，浪费时间。可以说克鲁斯卡尔算法是很直观的算法，适合人的直观思考方式，但是因为上面论述的缘故

3、，克鲁斯卡尔算法比较适用在稀疏图边的数目不是很多的图上。边集数组：边集数组：从图变为程序需要的数据，需要采用合适的数据结构。由算法的核心思想上看，我们需要存储的数据为边边，而边的要素包括三点：连接的两个结点连接的两个结点、边的权值边的权值。然而边并不需要具有什么操作来改变自身或者做些什么，所以用struct 来自定义就合适不过了。struct edgeint node_1;int node_2;int value;另外，文中提及了最小边最小边、次小边次小边，这就暗示了应该对所有的边进行排序sort。比较函数应以 value 作衡量。bool cmp(edge a,edge b)return a

4、.value b.value;现在剩余最后的问题回路的防止。其实这个也很容易防止，我们可以定义一个数组usedmax，它记录了每一个结点是否被应用的情况，当要加入的一条边中useda.node_1和useda.node_2都已被应用，那么加入的这条边必然造成回路，否则不会。假设造成回路，则舍弃这条边，转而观察加入次小边。排序后的情况edge 数组01234node_112232node_224443value12345用红线将舍弃的边删除后，剩余的就成为了最小生成树了。时间复杂度时间复杂度假设 e 表示图的边数，那么，排序过程将有 O(eloge)，生成过程则是 O(e)，故总的来说，时间复杂

5、度为 O(eloge)O(eloge)。普林普林PrimPrim算法算法克鲁斯卡尔算法以边为出发点，相应地，普林算法则以点为出发点。从指定顶点指定顶点开始将它加入集合中，然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边，并将集合外的那个顶点加入到集合中，表示该顶点已连通。再用集合内的顶点与集合外的顶点构成的边中找最小的边，并将相应的顶点加入集合中。如此下去直到全部顶点都加入到集合中，即得最小生成树。以点作为出发点很好地解决了克鲁斯卡尔算法解决边数很多的图的可怕时间复杂度的问题。边数不是制约普林算法的因素，结点才是。普林算法的简单演算步骤：普林算法的简单演算步骤

6、：1初始化集合 A()，表示没有点以加入到生成结点中，初始化集合B，使 B 包含所有结点；2从 B 中选择一个点作为始加入到A 中并从 B 中剔除；3 选择 A 中所有的点中能到达 B 的最小权值边，将这条边的另一个点加入到A 中并从 B中剔除；4重复3操作直至 B 为 NULL，则为最小生成树。邻接矩阵邻接矩阵如果说克鲁斯卡尔算法使用自定义的边集数组边集数组存储图是直观的，那么普林算法采用自定义的点集数组也是合适的？如果以某一点作为单独的数据结构，那么这一数据结构应当包含有与这个点有关的边的所有信息权值权值和对应点对应点。但事前我们并不知道这个图的点的最大度数为多少，带着这种未知来定义str

7、uct 是危险的，所以我们应当采用邻接矩阵邻接矩阵一个存放顶点间关系边或弧的数据的二维矩阵，即有一个二维矩阵 data，dataab=c 表示 a结点和 b 结点有一条长为c 的边，相应地，databa=c。当 a,b 之间没有边的时候，应当使dataab=INFINF 表示无穷。集合集合由演算步骤中得知我们需要抽象出一个集合的概念，用以分开集合 A 和集合 B。对于这种简单的区分，大可不必抽象出对象出来。运用克鲁斯卡尔中 used 数组的概念也可模拟出这种集合，当 usedi等于特定值代表结点 i 在哪个集合中即可。初始化 used 状态等于 0 代表在 B 中memset(used,0,s

8、izeof(used);然后选取第一结点来实现2操作used0=1;优化优化3 3（3）选择 A 中所有的点中能到达 B 的最小权值边，将这条边的另一个点加入到A 中并从 B 中剔除；如何寻找最小权值边？如果直观地去做，从A 中各点遍历，那么每加入一个点到A 所费的时间也是惊人的，所以也引入两个数组来作优化。lowcost 数组：lowcosti表示 A 集合中到结点 i(I 必然在集合 B 中)的权值权值；closest 数组：对应与 lowcost，表示结点 i 到集合 A 的用最小权值边连通的点点。所以当2中采用了第一结点，那么这个数组应当被初始化为for(int kn=1;kn n;+

9、kn)lowcostkn=data0kn;closestkn=0;当进行3时只需这样寻找for(int i=0;i n;+i)if(!usedi&lowcosti min)min=lowcosti;min_site=i;每执行一次3都需要对着两个数组进行更新for(int ks=0;ks n;ks+)if(!usedks&(datamin_siteks lowcostks)owcostks=datamin_siteks;closestks=min_site;时间复杂度时间复杂度假设 n 表示图的结点数，那么初始化需要O(n)，找出最小边 O(n)，更新为 O(n)，需要找出与更新 n 次，总的

10、为 O(n*(2n)+n)，即 O(n*n)O(n*n)。最短路径最短路径最短路径问题是图论研究中的一个经典算法问题，旨在寻找图 由结点和路径组成的中两结点之间的最短路径。1815214410730从从 1 1 到到 4 4 最短路径最短路径101031593159迪杰斯特拉迪杰斯特拉DijkstraDijkstra算法算法Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法能得出最短路径的最优解。但是，由于它遍历计算的节点很多，所以效率低。基本思想基本思想设置顶点集合

11、 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。从源到该顶点的最短路径长度已知。初始时，S 中仅含有源。设 u 是 G 的某一个顶点，把从源到u 且中间只经过 S S 中顶点中顶点的路的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。迪杰斯特拉算法每次从所有特殊路径中取出最短特殊路径及其顶点u，将 u 添加到 S 中，同时对数组 distdist 作必要的修改作必要的修改。一旦 S 包含了所有 V 中顶点，dist 就记录了从源到所有其它顶点之间的最短路径长度。简单模拟简单模拟沿用克鲁斯卡尔算法 used

12、数组来模拟集合 S。初始化：结点 1 作为源点，此时的特殊路径有1-2、1-3、1-4，最短特殊路径为 1-31103明显结点 3 到源点的最短路径已定，则结点3 也在 S 集合中，dist3被赋值为 10。S 加入结点 3 后，特殊路径有1-2、1-3、1-4、1-3-2、1-3-5，最短特殊路径为 1-3-5110315明显结点 5 到源点的最短路径已定，则结点5 也在 S 集合中，dist5被赋值为 11。以此类推，直到所有的点的dist 被计算出来。难点难点无论是边集数组还是邻接矩阵来存储图，对迪杰斯特拉算法来说影响不大，或者说各有各的优劣，视问题分析而定。由上面的分析可以看出，迪杰斯

13、特拉算法的难点在于在特殊路径中找出最短的那条并最后将它删除。对于这种情况，其实我们可以构造一个类来存储最短特殊路径，并使它对特殊路径具有push、pop、sort 等的功能。不过STL 也提供了类似的类priority_queuepriority_queue。弗洛伊德沃舍尔弗洛伊德沃舍尔WarshallWarshall 算法算法沃舍尔算法只需要使用 2n3 次位运算就可以求出传递闭包。传递闭包传递闭包在数学中，在集合 X 上的二元关系 R 的传递闭包是包含 R 的 X 上的最小的传递关系。当图中点边关系以邻接矩阵给出时，利用沃舍尔算法能够在O(n3)内算出每点到各个点的最短路径，并以邻接矩阵形式给出。五行代码之美五行代码之美共有 num_pl 个结点，placeij表示结点 i 到结点 j 的边权值为 placeij，不存在边时则赋值 INF 标志。for(int med=1;med=num_pl;+med)for(int i=1;i=num_pl;+i)for(int j=1;j placeimed+placemedj)placeij=placeimed+placemedj;如果结点 i与 j 之间能通过介质点 med 来获得更短 路 径，则 更 新placeij的值