简介
求最小生成树一共有两种算法,一个是就是本文所说的Kruskal算法,另一个就是Prime算法。在详细讲解Kruskal最小生成树算法之前,让我们先回顾一下什么是最小生成树。
我们有一个带权值的图,我们要求找到一个所有生成树中具有最小权值的生成树。如下图所示,T是图G的生成树。但不是具有最小权值的生成树。
我们可以把他们想象成一组岛屿和连接它们的可能的桥梁。当然修桥是非常昂贵和费时的,所以我们必须要知道建设什么样的桥梁去连接各个岛。不过有一个重要的问题,建设这样一组连接所有岛屿的桥梁的最低价格是多少。
我们实际上需要构建一棵最小生成树,顶点表示岛屿,而边表示它们之间可能要修建的桥梁。每一个可能修建的桥梁都有相应的权值(表示我们建造它所花费的时间和金钱等)。
在实践中,我们只可能使用一个最小生成树的可能用例。(This scenario is only one of possible use cases of where minimum spanning trees can be used in practice.)
概要
Kruskal算法开始由初始化一组集合,并建立| V|棵树,每棵树都只包含了图的一个顶点。
在建设最后生成树的过程中,我们维护一个森林。很显然,我们由|V|棵树组成的森林开始,其中每个树都只有是一个节点。
在某些时候,我们有“K”棵树组成的森林,这几棵树都最小生成树的子树。
构建最终的最小生成树最后一个步骤之前,我们有两个树(如上图的3),我们用剩下的最小权值边来连接这两棵树。
构建树的过程中,我们按照权值的升序,对边进行排序。
然后,获取边,检查每条边(u,v),其端点u和v是否是属于同一棵树。如果是,把(u,v)加入森林中就会形成一个回路,所以放弃这条边(u,v)。否则,说明两个顶点分属不同的树。
关于Kruskal算法一个很大的特点是,它也可以用在非连同图中。
原文
Computer Algorithms: Kruskal’s Minimum Spanning Tree
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树...
对给定的图结构,实现求解最小生成树的Kruskal算法。每次在满足和已选边不构成回路的条件下选择一条权植最小的边,添加到新的生成数中。Kruskal算法的实现类似于计算连通枝的算法。它使用了分离集合数据结构以保持数...
Prim算法与Kruskal算法 求最小生成树 源代码 实验报告 完整
最小生成树kruskal算法 最小生成树kruskal算法
利用matlab 编写的kruskal 最小生成树的算法。
建立一个图,其存储方式采用邻接矩阵形式,利用普里姆算法和克鲁斯卡尔算法求网的最小生成树,按顺序输出生成树中各条边以及它们的权值。
prim算法 Kruskal算法分别实现最小生成树
代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal...
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
头歌数据结构图的最小生成树算法 第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)...
prim和kruskal算法求最小生成树
编程实现Kruskal算法,生成最小代价生成树,其中利用最小堆算法实现。 (随机生成n个点,且随机生成k条边,形成连通图)
该程序是我写的博客“一起talk C栗子吧(第五十回:C语言实例--最小生成树二)”的配套程序,共享给大家使用
Prim与Kruskal算法的最小生成树matlab实现
实现了kruskal的算法,测试可行。
数据结构课程设计报告最小生成树Kruskal算法
kruskal算法,最小生成树算法,内有示例,也可改成函数(在示例状态下被注释,要改成函数,取消那个注释,改下函数名或者文件名就行)
(1)、实验题目:给定一个地区的n 个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并得到的最小生成树的代价。 (2)、实验要求: 1、城市间的距离网采用的邻接矩阵表示,邻接矩阵的存储结构定义采用...
kruskal算法求最小生成树 java代码