C++中使用STL的Kraskar最小生成树

给定一个无向连通加权图，求 M 最小值 s 淘金 T 使用Kruskal算法得到图的ree（MST）。

Input :   Graph as an array of edges
Output :  Edges of MST are 
          6 - 7
          2 - 8
          5 - 6
          0 - 1
          2 - 5
          2 - 3
          0 - 7
          3 - 4
          
          Weight of MST is 37

Note :  There are two possible MSTs, the other
        MST includes edge 1-2 in place of 0-7. 

下面我们讨论了Kruskal的MST实现。

贪婪算法|集2（Kruskal最小生成树算法）

下面是使用Kruskal算法查找MST的步骤

1. 按其权重的非降序对所有边进行排序。
2. 选择最小的边。检查它是否与到目前为止形成的生成树形成一个循环。如果未形成循环，则包括该边缘。否则，扔掉它。
3. 重复步骤2，直到生成树中有（V-1）条边。

以下是一些关键点，它们将对我们使用STL实现Kruskal算法非常有用。

1. 使用由图中所有边组成的边向量，向量的每一项将包含3个参数：源、目标和源与目标之间边的成本。

           vector<pair<int, pair<int, int> > > edges;

   在外部对中（即pair >），第一个元素对应于边的代价，而第二个元素本身就是一对，它包含边的两个顶点。

2. 使用内置的 排序 按非递减顺序对边缘进行排序；默认情况下，排序函数按非降序排序。
3. 我们使用 联合查找算法 检查当前边是否形成循环，如果它添加到当前MST中。如果是，则丢弃它，否则包括它（联合）。

伪代码：

// Initialize result
mst_weight = 0

// Create V single item sets
for each vertex v
    parent[v] = v;
    rank[v] = 0;

Sort all edges into non decreasing 
order by weight w

for each (u, v) taken from the sorted list  E
    do if FIND-SET(u) != FIND-SET(v)
        print edge(u, v)
        mst_weight += weight of edge(u, v)
        UNION(u, v)

下面是C++实现上述算法。

输出：

 Edges of MST are 
          6 - 7
          2 - 8
          5 - 6
          0 - 1
          2 - 5
          2 - 3
          0 - 7
          3 - 4
          
          Weight of MST is 37

优化： 当选定边的数量变为V-1时，可以优化上述代码以停止Kruskal的主循环。我们知道MST有V-1边，并且在选择V-1边后没有点迭代。我们没有添加这种优化来保持代码简单。

参考资料： Cormen Leiserson Rivest和Stein算法介绍（CLRS）3

本文讨论了时间复杂性和分步演示 关于Kruskal算法的前一篇文章。

本文由 希拉格·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论