Kruskal算法

来自计算思维百科
跳转至: 导航搜索
Kruskal算法1.png

如果我们有一个图,我们需要在这个图中寻找一棵树,这棵树包含原图中的所有n 个结点,并且有保持图连通的最少的边。Kruskal算法是可以在加权连通图里搜索最小生成树的算法。

基本概念

该算法由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是,Kruskal算法在图中存在相同权值的边时也有效。它与Prim算法的不同之处在于,它在找最小生成树结点之前,需要对所有权重边做从小到大排序。将排序好的权重边依次加入到最小生成树中,如果加入时产生回路就跳过这条边,加入下一条边。当所有结点都加入到最小生成树中之后,就找出了最小生成树。

应用范围

其应用范围与Prim算法相似,常用于线路铺设的成本控制中。

使用方法及步骤

在给定含n个顶点的带权值的连通图表示为G=(V,E)(注:V指顶点集,E指边集),寻找一条路径使得权值和最小。设VT为点集表示最小生成树中的顶点集,ET表示最小生成树的边集。

1. 排序:将E中所有边按权值大小从小到大排序;

2. 将每个顶点加入一个集合,即n个点n个集合;

3. 按顺序访问每条边,若该边的两端点属于不同集合,则合并两个集合并将边加入ET中;

4最后得到的GT=(VT,ET)即为最小生成树。

应用案例

应用1-城市铺路造价问题

案例:现有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权代表公路造价。在分析了这张图后发现,任一对城市都是连通的。现在要求用公路把所有城市联系起来,如何设计可使工程的总造价最少?

Kruskal算法2.png

解决步骤:在介绍Prim算法里也介绍过此案例,这里以Kruskal算法来解决同样的问题

1. 排序:对图中的边按权值排序;

2. 具体过程如下表:

Kruskal算法3.png

3. 上面为利用Kruskal算法解决问题的具体过程,故根据最后的生成树,我们可以使公路造价成本最低。

可以体现的计算思维

从上面的分析中容易看出在Kruskal算法与Prim算法类似,都是在解决问题的每一步尽可能地得到当前最优的解,希望通过一系列的最优选择,能够产生一个整个问题的最优解。同样也体现了计算思维的优化特点。