最小生成树：Kruskal算法

给定一个带权无向图，希望找到一棵连接所有顶点的子树，即生成树，并使其总权重在所有可能的生成树中最小。总权重是所有边权之和。这棵树称为最小生成树。

左图是一个带权无向图，右图是对应的最小生成树。

带权无向图与对应最小生成树（原文配图）。

本文先讨论最小生成树的几个重要性质，再给出用于寻找最小生成树的Kruskal算法最简单实现。

最小生成树的性质

如果所有边的权重都不同，图的最小生成树唯一；否则可能有多棵最小生成树。具体算法通常输出其中一棵。
如果所有边权均为正，最小生成树也是边权乘积最小的树。可将每条边权替换为其对数证明，因为这一变换保留边权的排序。
最小生成树中权重最大的边，其权重在该图所有可能生成树的最大边权中最小。这由Kruskal算法的正确性得出。
求最大生成树（边权总和最大的生成树）的方法与最小生成树相似：将所有边权取相反数，再应用任意最小生成树算法。

Kruskal算法

该算法由Joseph Bernard Kruskal, Jr.于1956年提出。

开始时，将原图所有节点彼此隔离，形成由单节点树组成的森林。然后逐渐合并这些树，每次使用原图的一条边连接两棵树。算法执行前，先按权重非递减顺序排序所有边。

之后，依次考察排序后的每条边：若当前边的两个端点属于不同子树，就合并这些子树，并把该边加入答案。若图连通，遍历所有边后全部顶点属于同一棵子树，得到最小生成树。若图不连通，同一过程得到的是最小生成森林。

最简单的实现

以下代码直接实现上述算法，时间复杂度为O(M log M + N²)。边排序需要O(M log N)次操作，原文指出这与O(M log M)等价。数组tree_id[]维护顶点所属的子树：对每个顶点v，tree_id[v]存储其所属树的编号。对每条边，可在O(1)时间内判断两端是否属于不同树。

合并两棵树时，简单遍历tree_id[]数组，耗时O(N)。合并操作总数为N−1，因此渐进复杂度为O(M log N + N²)。

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

int n;
vector<Edge> edges;

int cost = 0;
vector<int> tree_id(n);
vector<Edge> result;
for (int i = 0; i < n; i++)
    tree_id[i] = i;

sort(edges.begin(), edges.end());

for (Edge e : edges) {
    if (tree_id[e.u] != tree_id[e.v]) {
        cost += e.weight;
        result.push_back(e);
        int old_id = tree_id[e.u], new_id = tree_id[e.v];
        for (int i = 0; i < n; i++) {
            if (tree_id[i] == old_id)
                tree_id[i] = new_id;
        }
    }
}