2022年最小生成树and最短路径 .docx

精选学习资料 - - - - - - - - - 最小生成树 and 最短路径无独有偶,在两个学期的期末中两门不同的科目离散数学和数据结构中都谈到了图及其衍生的最小生成树、最短路径问题,并给出了相应的算法克鲁斯卡尔、普林、迪杰斯特拉、 沃舍尔算法； 这无疑是释放了一个很大的信号这些内容很重要；由于之前学离散数学时只要求在思想上懂得,并没要求程序实现,所以学起来也挺吃力的；而现在来到了数据结构的课程上,我觉得仍是有必要写写懂得与体会,好让以后用起来没那么难；最小生成树 Minimum Spanning Tree,MST 一个有 n 个结点的连通图的生成树是原图的 微小 连通子图, 且包含原图中的全部 n 个结点,并且有保持图连通的最少的边；即是在原图上删除边,直到剩余 n-1 条边,保证 n 个结点连通且边的权值加起来最小；简洁图示：1 3 1 2 2 MST1 1 2 2 5 3 4 4 3 4 4 克鲁斯卡尔 Kruskal 算法克鲁斯卡尔算法从边的角度来解决问题,即在剩下的全部未选取的边中,找最小边, 如果和已选取的边构成回路,就舍弃,选取次小边；然而,图的存贮结构采纳边集数组,且权值相等的边在数组中排列次序可以是任意的,该方法对于边数相比照较多的图不是很有用,铺张时间； 可以说克鲁斯卡尔算法是很直观的算法,适合人的直观摸索方式,但是由于上面论述的缘故,克鲁斯卡尔算法比较适用在稀疏图边的数目不是许多的图上；边集数组：从图变为程序需要的数据,需要采纳合适的数据结构；由算法的核心思想上看,我们需要储备的数据为 边 ,而边的要素包括三点：连接的两个结点、边的权值 ；然而边并不需要具有什么操作来转变自身或者做些什么,所以用struct edge int node_1; int node_2; int value ; ; struct 来自定义就合适不过了；名师归纳总结 - - - - - - -第 1 页,共 5 页精选学习资料 - - - - - - - - - 另外,文中提及了最小边 、次小边 ,这就示意了应当对全部的边进行排序sort；比较函数应以 value 作衡量；bool cmpedge a , edge b return a.value < b.value ; 现在剩余最终的问题回路的防止；其实这个也很简洁防止,我们可以定义一个数组usedmax,它记录了每一个结点是否被应用的情形,当要加入的一条边中 useda.node_1和useda.node_2都已被应用,那么加入的这条边必定造成回路,否就不会；假设造成回路,就舍弃这条边,转而观看加入次小边；排序后的情形edge数组node_1 node_2 value 0 1 2 1 1 2 4 2 2 2 4 3 3 3 4 4 4 2 3 5 用红线将舍弃的边删除后,剩余的就成为了最小生成树了；时间复杂度假设 e 表示图的边数, 那么,排序过程将有Oeloge,生成过程就是Oe,故总的来说,时间复杂度为Oeloge ；普林 Prim 算法克鲁斯卡尔算法以边为动身点,相应地, 普林算法就以点为动身点；从指定顶点 开头将它加入集合中, 然后将集合内的顶点与集合外的顶点所构成的全部边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加入到集合中,表示该顶点已连通；再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将相应的顶点加入集合中；如此下去直到全部顶点都加入到集合中,即得最小生成树； 以点作为动身点很好地解决了克鲁斯卡尔算法解决边数许多的图的可怕时间复杂度的问题；边数不是制约普林算法的因素,结点才是；普林算法的简洁演算步骤：1初始化集合A ,表示没有点以加入到生成结点中,初始化集合B,使 B 包含全部结点；2从 B 中挑选一个点作为始加入到 A 中并从 B 中剔除；3挑选 A 中全部的点中能到达 B 的最小权值边, 将这条边的另一个点加入到 A 中并从 B中剔除；4重复 3操作直至B 为 NULL ,就为最小生成树；名师归纳总结 - - - - - - -第 2 页,共 5 页精选学习资料 - - - - - - - - - 邻接矩阵假如说克鲁斯卡尔算法使用自定义的边集数组 储备图是直观的, 那么普林算法采纳自定义的点集数组也是合适的？假如以某一点作为单独的数据结构,那么这一数据结构应当包含有与这个点有关的边的全部信息权值 和对应点 ；但事前我们并不知道这个图的点的最大度数为多少,带着这种未知来定义 struct 是危急的,所以我们应当采纳 邻接矩阵 一个存放顶点间关系边或弧的数据的二维矩阵,即有一个二维矩阵 data,dataab=c 表示 a结点和 b 结点有一条长为 c 的边,相应地,databa=c ；当 a,b 之间没有边的时候,应当使dataab = INF INF 表示无穷；集合由演算步骤中得知我们需要抽象出一个集合的概念,用以分开集合 A 和集合 B；对于这种简洁的区分,大可不必抽象出对象出来；运用克鲁斯卡尔中used 数组的概念也可模拟出这种集合,当 usedi 等于特定值代表结点 i 在哪个集合中即可；初始化 used 状态等于 0 代表在 B 中memsetused,0,sizeofused; 然后选取第一结点来实现2操作used0 = 1 ; 优化 3（3）挑选 A 中全部的点中能到达B 的最小权值边,将这条边的另一个点加入到A 中并从 B 中剔除；如何查找最小权值边？假如直观地去做,从A 中各点遍历,那么每加入一个点到A 所费的时间也是惊人的,所以也引入两个数组来作优化；lowcost 数组： lowcosti 表示 A 集合中到结点 iI 必定在集合 B 中的 权值 ；closest 数组：对应与 lowcost,表示结点 i 到集合 A 的用最小权值边连通的 点；所以当 2中采纳了第一结点,那么这个数组应当被初始化为forint kn = 1; kn < n ; +kn lowcostkn = data0kn; closestkn = 0 ; 当进行 3时只需这样查找forint i = 0 ; i < n ;+i if .usedi && lowcosti < min min = lowcosti ; min_site = i ; 名师归纳总结 - - - - - - -第 3 页,共 5 页精选学习资料 - - - - - - - - - 每执行一次 3都需要对着两个数组进行更新for int ks = 0 ; ks < n ; ks+ if .usedks && datamin_siteks < lowcostks owcostks = datamin_siteks; closestks = min_site ; 时间复杂度假设 n 表示图的结点数,那么初始化需要On,找出最小边On,更新为On,需要找出与更新n 次,总的为On*2n+n ,即 On*n ；最短路径最短路径问题是图论讨论中的一个经典算法问题,中两结点之间的最短路径；18 旨在查找图 由结点和路径组成的1 7 1 2 5 4 从 1 到 4 最短路径1 1 5 4 10 30 103 5 9 9 3 迪杰斯特拉 Dijkstra 算法Dijkstra 迪杰斯特拉 算法是典型的最短路径路由算法,用于运算一个节点到其他节点的最短路径；主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止；Dijkstra 算法能得出最短路径的最优解；但是,由于它遍历运算的节点许多,所以效率低；基本思想设置顶点集合S 并不断地作贪心挑选来扩充这个集合；一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知；初始时, S 中仅含有源；设u 是 G 的某一个顶点,把从源到u 且中间只经过S 中顶点的路 称为从源到 u 的特别路径, 并用数组 dist 记录当前每个顶点所对应的最短特别路径长度；迪杰斯特拉算法每次从全部特别路径中取出最短特别路径及其顶点u,将 u 添加到 S 中,同时对数组 dist 作必要的修改 ；一旦 S 包含了全部 V 中顶点, dist 就记录了从源到全部其它顶点之间的最短路径长度；名师归纳总结 - - - - - - -第 4 页,共 5 页精选学习资料 - - - - - - - - - 简洁模拟沿用克鲁斯卡尔算法used 数组来模拟集合S；1-3 初始化：结点1 作为源点,此时的特别路径有1-2 、1-3、1-4 ,最短特别路径为1 10 3 明显结点 3 到源点的最短路径已定,就结点3 也在 S 集合中, dist3 被赋值为 10；S 加入结点 3 后,特别路径有1-2 、1-3、1-4、1-3-2、 1-3-5 ,最短特别路径为1-3-5 1 10 3 1 5 明显结点 5 到源点的最短路径已定,就结点5 也在 S 集合中, dist5 被赋值为 11；以此类推,直到全部的点的 dist 被运算出来；难点无论是边集数组仍是邻接矩阵来储备图,对迪杰斯特拉算法来说影响不大,或者说各有各的优劣, 视问题分析而定；由上面的分析可以看出,迪杰斯特拉算法的难点在于在特别路径中找出最短的那条并最终将它删除；对于这种情形, 其实我们可以构造一个类来储备最短特别路径,并使它对特别路径具有 push、pop、sort 等的功能；不过 STL 也供应了类似的类 priority_queue；弗洛伊德沃舍尔 Warshall 算法沃舍尔算法只需要使用 传递闭包2n3 次位运算就可以求出传递闭包；在数学中,在集合X 上的二元关系 R 的传递闭包是包含R 的 X 上的最小的传递关系；当图中点边关系以邻接矩阵给出时,利用沃舍尔算法能够在 点的最短路径,并以邻接矩阵形式给出；五行代码之美On3 内算出每点到各个共有 num_pl 个结点, placeij 表示结点i 到结点 j 的边权值为placeij ,不存在边时就赋值 INF 标志；forint med = 1 ; med <= num_pl ; +med 假如结点 i 与 j 之间能通forint i = 1 ; i <= num_pl ; +i 过介质点med 来获得更forint j = 1 ; j <= num_pl ; +j 短 路 径 , 就 更 新名师归纳总结 ifplaceij > placeimed + placemedj placeij 的值第 5 页,共 5 页placeij = placeimed + placemedj ; - - - - - - -