首页 > 代码库 > 贪心算法(Greedy Algorithm)之最小生成树 克鲁斯卡尔算法(Kruskal's algorithm)

贪心算法(Greedy Algorithm)之最小生成树 克鲁斯卡尔算法(Kruskal's algorithm)

克鲁斯卡尔算法(Kruskal‘s algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。大致的流程能够用一个图来表示。这里的图的选择借用了Wikipedia上的那个。很清晰且直观。

 

首先第一步,我们有一张图,有若干点和边

例如以下图所看到的:

graph

第一步我们要做的事情就是将全部的边的长度排序,用排序的结果作为我们选择边的根据。这里再次体现了贪心算法的思想。资源排序,对局部最优的资源进行选择。

排序完毕后,我们领先选择了边AD。 这样我们的图就变成了

图1

第二步,在剩下的变中寻找。我们找到了CE。这里边的权重也是5

图二

依次类推我们找到了6,7,7。完毕之后,图变成了这个样子。

图三

下一步就是关键了。以下选择那条边呢? BC或者EF吗?都不是,虽然如今长度为8的边是最小的未选择的边。可是如今他们已经连通了(对于BC能够通过CE,EB来连接,相似的EF能够通过EB, BA, AD, DF来接连)。所以我们不须要选择他们。相似的BD也已经连通了(这里的连通线用红色表示了)。所以最后就剩下EG和FG了。当然我们选择了EG。 最后成功的图就是下图:

图四

到这里全部的边点都已经连通了,一个最小生成树构建完毕。

假设要简要得描写叙述这个算法的话就是,首先边的权重排序。(从小到大)循环的推断是否须要选择这里的边。推断的根据则是边的两个顶点是否已经连通,假设连通则继续下一条。不连通就选择使其连通。这个流程还是很清晰明了。

 

可是在实现的时候,困难的地方在于怎样描写叙述2个点已然连通? 这里用到了并查集做辅助,至于并查集能够到这里去看看。

这里贴出并查集的代码和Kruscal的C++实现:

 

贪心算法(Greedy Algorithm)之最小生成树 克鲁斯卡尔算法(Kruskal's algorithm)