简介

欢迎回到图算法系列！最小生成树（MST）用总边权尽可能小的方式连接加权图中的每个顶点，并且不包含环。

Kruskal 算法通过贪心策略构建 MST：它按边权从小到大排序，然后逐条添加边，只要添加后不会形成环即可。要快速检测环，可以使用一种名为并查集（也称为不相交集）的数据结构。

这个图是无向加权图，用 n（顶点编号从 0 到 n - 1）和 edges 表示。edges 是一个由三元组组成的一维数组 [u0, v0, w0, ...]，表示一条权重为 w 的无向边 u - v。

开始吧！