最小生成树 – Kruskal算法

最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起。

图N个节点，E条边，则最小生成树就是从E条边种选取N-1条边的总权重值最小。

Kruskal算法原理是贪心算法，每次都假定最小权值的边为最小生成树的一部分（前提：不让最小生成树形成环）。

Prim算法维护节点集合，Kruskal算法维护边集合。

Kruskal两部曲：

• 1 对全部的边的权值进行排序
• 2 判断最小权重的边的首尾节点是否处于同一集合
  • 属于同一集合，则会形成环，不构成最小生成树，pass该边。
  • 不属于同一集合，构成最小生成树的一部分。

以下为代码随想录的模拟过程：

初始状态：

排序后的边为：[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]

判断（1,2）边是否处于同一集合（并查集）？不属于，则该边为最小生成树的一部分。

判断（4,5）边是否处于同一集合（并查集）？不属于，则该边为最小生成树的一部分。

判断（1,3）边是否处于同一集合（并查集）？不属于，则该边为最小生成树的一部分。

判断（2,6）边是否处于同一集合（并查集）？不属于，则该边为最小生成树的一部分。

判断（3,4）边是否处于同一集合（并查集）？不属于，则该边为最小生成树的一部分。

判断（6,7）边是否处于同一集合（并查集）？不属于，则该边为最小生成树的一部分。

判断（5,7），（1,5），（3,2），（2,4），（5,6）边是否处于同一集合（并查集）？属于，则该边不为最小生成树的一部分。

结束模拟，得到最终最小生成树，如下：

模拟完了之后，我们来上真题吧。

解题思路：

• 1 对边进行权值排序
• 2 使用并查集判断最小权值的边是否处于同一集合。

详细代码如下：