最小生成树 Prim 对比 Kruskal

📖 算法原理：切边定理与并查集合合

最小生成树 (MST) 是指在加权无向连通图中，选择 $N-1$ 条边连接所有 $N$ 个顶点，且边权之和最小的生成树。

📐 Prim 算法 (基于顶点集合 expansion)

思想：从任意一个顶点开始，维护一个“已加入生成树的顶点集合 $S$”。
每步测试：找到一条一端在 $S$ 中，另一端在 $S$ 之外的权值最小的“切边”，将其加入生成树中，并把其外侧端点拉入 $S$ 中。
复杂度：朴素实现为 $O(N^2)$，使用堆优化可达 $O(M \log N)$，适用于稠密图。

📐 Kruskal 算法 (基于边权排序 & 并查集)

思想：将图中的所有边按权值自小到大进行全局排序。
每步测试：按顺序检查排序后的每条边 $(u, v)$。利用 并查集 (Disjoint Set Union, DSU) 判断 $u$ 和 $v$ 是否已经连通：
- 若已连通（在同一个集合内）：加入该边会产生环路，因此必须拒绝丢弃此边。
- 若不连通：将该边加入生成树中，并在并查集中执行 `union` 合并。
复杂度：取决于边排序，为 $O(M \log M)$，由于逻辑简洁且常数小，极其适用于稀疏图。

演示速度：

点击"开始同步演示"观察左侧的 Prim 点集蔓延与右侧的 Kruskal 边排序 DSU 检查。

🔵 左屏：Prim 算法 (顶点点集扩张)

已收录点0 / 6

已加入边0

当前总权值0

🟢 右屏：Kruskal 算法 (边全局排序 & DSU)

并查集联通块6

已加入边0

当前总权值0

// Kruskal's MST Algorithm (并查集合并)
struct Edge {
    int u, v, w;
    bool operator<(const Edge& o) const { return w < o.w; }
};

void kruskal() {
    sort(edges.begin(), edges.end()); // 1. 全局边权排序
    for (int i = 1; i <= n; i++) parent[i] = i; // 初始化并查集
    
    int mst_weight = 0, edge_count = 0;
    for (auto e : edges) {
        int rootU = find(e.u);
        int rootV = find(e.v);
        if (rootU != rootV) { // 2. 若不连通则安全加入，防环！
            unionSet(rootU, rootV);
            mst_weight += e.w;
            edge_count++;
            if (edge_count == n - 1) break;
        }
    }
}

📋 算法执行步骤日志