首页 > 代码库 > 算法8-2:最小生成树贪婪算法
算法8-2:最小生成树贪婪算法
为了简化问题,我们需要作出一些假设。假设图中每条边的权重都是不一样的,假设整个图是连通的。这样假设的目的就是让最小生成树的计算结果是唯一的。
图的切割
介绍算法之前,需要先了解图的切割。图的切割就是将顶点分割成两部分,切到的边称之为交叉边。下图红色的先就是交叉边。
在最小生成树中,无论如何切割,最小生成树总是从交叉边中选择最小的一条边。下图中红色的粗边就是最小生成树上的边。
算法步骤
贪婪算法的步骤如下:
所有的边在一开始都是灰色的,最小生成树的边是黑色的。
任意选择一种切割方法,只要不切割到黑色的边即可。从被切割到的边中选择最短的一条边标记成黑色,表示这条边属于最小生成树
重复步骤2,直到黑色的边连接所有的顶点为止
贪婪算法的性能比较差,后续将会介绍kruskai算法、prim算法和boruvka,因此这里就不编写代码了。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。