2022年最小生成树and最短路径 .docx
《2022年最小生成树and最短路径 .docx》由会员分享,可在线阅读,更多相关《2022年最小生成树and最短路径 .docx(8页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选学习资料 - - - - - - - - - 最小生成树 and 最短路径无独有偶,在两个学期的期末中两门不同的科目离散数学和数据结构中都谈到了图及其衍生的最小生成树、最短路径问题,并给出了相应的算法克鲁斯卡尔、普林、迪杰斯特拉、 沃舍尔算法; 这无疑是释放了一个很大的信号这些内容很重要;由于之前学离散数学时只要求在思想上懂得,并没要求程序实现,所以学起来也挺吃力的;而现在来到了数据结构的课程上,我觉得仍是有必要写写懂得与体会,好让以后用起来没那么难;最小生成树 Minimum Spanning Tree,MST 一个有 n 个结点的连通图的生成树是原图的 微小 连通子图, 且包含原图中的
2、全部 n 个结点,并且有保持图连通的最少的边;即是在原图上删除边,直到剩余 n-1 条边,保证 n 个结点连通且边的权值加起来最小;简洁图示:1 3 1 2 2 MST1 1 2 2 5 3 4 4 3 4 4 克鲁斯卡尔 Kruskal 算法克鲁斯卡尔算法从边的角度来解决问题,即在剩下的全部未选取的边中,找最小边, 如果和已选取的边构成回路,就舍弃,选取次小边;然而,图的存贮结构采纳边集数组,且权值相等的边在数组中排列次序可以是任意的,该方法对于边数相比照较多的图不是很有用,铺张时间; 可以说克鲁斯卡尔算法是很直观的算法,适合人的直观摸索方式,但是由于上面论述的缘故,克鲁斯卡尔算法比较适用在
3、稀疏图边的数目不是许多的图上;边集数组:从图变为程序需要的数据,需要采纳合适的数据结构;由算法的核心思想上看,我们需要储备的数据为 边 ,而边的要素包括三点:连接的两个结点、边的权值 ;然而边并不需要具有什么操作来转变自身或者做些什么,所以用struct edge int node_1; int node_2; int value ; ; struct 来自定义就合适不过了;名师归纳总结 - - - - - - -第 1 页,共 5 页精选学习资料 - - - - - - - - - 另外,文中提及了最小边 、次小边 ,这就示意了应当对全部的边进行排序sort;比较函数应以 value 作衡量
4、;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 用红线将舍弃的边删除后,剩余的就成为了最小生成树了;时间复杂度
5、假设 e 表示图的边数, 那么,排序过程将有Oeloge,生成过程就是Oe,故总的来说,时间复杂度为Oeloge ;普林 Prim 算法克鲁斯卡尔算法以边为动身点,相应地, 普林算法就以点为动身点;从指定顶点 开头将它加入集合中, 然后将集合内的顶点与集合外的顶点所构成的全部边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加入到集合中,表示该顶点已连通;再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将相应的顶点加入集合中;如此下去直到全部顶点都加入到集合中,即得最小生成树; 以点作为动身点很好地解决了克鲁斯卡尔算法解决边数许多的图的可怕时间复杂度的问题;边数不是制约普林算法
6、的因素,结点才是;普林算法的简洁演算步骤:1初始化集合A ,表示没有点以加入到生成结点中,初始化集合B,使 B 包含全部结点;2从 B 中挑选一个点作为始加入到 A 中并从 B 中剔除;3挑选 A 中全部的点中能到达 B 的最小权值边, 将这条边的另一个点加入到 A 中并从 B中剔除;4重复 3操作直至B 为 NULL ,就为最小生成树;名师归纳总结 - - - - - - -第 2 页,共 5 页精选学习资料 - - - - - - - - - 邻接矩阵假如说克鲁斯卡尔算法使用自定义的边集数组 储备图是直观的, 那么普林算法采纳自定义的点集数组也是合适的?假如以某一点作为单独的数据结构,那么
7、这一数据结构应当包含有与这个点有关的边的全部信息权值 和对应点 ;但事前我们并不知道这个图的点的最大度数为多少,带着这种未知来定义 struct 是危急的,所以我们应当采纳 邻接矩阵 一个存放顶点间关系边或弧的数据的二维矩阵,即有一个二维矩阵 data,dataab=c 表示 a结点和 b 结点有一条长为 c 的边,相应地,databa=c ;当 a,b 之间没有边的时候,应当使dataab = INF INF 表示无穷;集合由演算步骤中得知我们需要抽象出一个集合的概念,用以分开集合 A 和集合 B;对于这种简洁的区分,大可不必抽象出对象出来;运用克鲁斯卡尔中used 数组的概念也可模拟出这种
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年最小生成树and最短路径 2022 最小 生成 and 路径
限制150内