最小生成树（Kruskal算法和Prim算法）

在图论中，生成树和最小生成树是非常重要的概念。下面我们会讲解生成树的定义，并介绍两种经典的最小生成树算法：Kruskal算法和Prim算法，并附上C++代码示例。

1. 生成树

• 生成树（Spanning Tree）是一个包含图中所有节点的子图，且是一个无环的连通图。
• 最小生成树（Minimum Spanning Tree，MST）是所有生成树中边权和最小的一棵树。

最小生成树算法

最小生成树问题主要适用于无向加权连通图。常用的两种算法是Kruskal算法和Prim算法。

Kruskal算法

Kruskal算法是贪心算法的一个例子，适合稀疏图。该算法的核心思想是将边按权值从小到大排序，逐一添加边，确保不形成环，直到生成一棵生成树。

算法步骤：

1. 将图中的所有边按权值从小到大排序。
2. 初始化一个并查集（Union-Find）来检测环。
3. 从权值最小的边开始，依次判断该边的两个端点是否在同一集合中：
   • 若不在同一集合，添加该边并合并两个集合；
   • 若在同一集合中，跳过该边（否则会形成环）。
4. 重复步骤3，直到得到的边数等于节点数-1。

C++代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

class UnionFind {
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int u) {
        if (parent[u] != u) parent[u] = find(parent[u]); // 路径压缩
        return parent[u];
    }
    
    bool unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU == rootV) return false;
        if (rank[rootU] > rank[rootV]) parent[rootV] = rootU;
        else if (rank[rootU] < rank[rootV]) parent[rootU] = rootV;
        else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
        return true;
    }
    
private:
    vector<int> parent;
    vector<int> rank;
};

int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end()); // 按权值升序排序边
    UnionFind uf(n);
    int mstWeight = 0;
    int edgesUsed = 0;

    for (const Edge& e : edges) {
        if (uf.unionSets(e.u, e.v)) { // 如果加入该边不会形成环
            mstWeight += e.weight;
            edgesUsed++;
            if (edgesUsed == n - 1) break; // 生成树边数为 n-1
        }
    }

    return mstWeight;
}

说明：

• Edge结构体表示一条边，包含起点、终点和权重，并重载了<运算符以支持排序。
• UnionFind类实现并查集，用于检测是否形成环。
• kruskal函数执行Kruskal算法，并返回最小生成树的总权重。

Prim算法

Prim算法也属于贪心算法，适合密集图。该算法从一个节点开始，逐步扩展最小代价的边，直到所有节点都被包括在生成树中。

算法步骤：

1. 从任意节点开始，将其标记为已访问。
2. 选择一个与生成树连接的最小权重边，将该边的另一个端点加入生成树。
3. 重复步骤2，直到所有节点都被加入生成树。

C++代码：

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

typedef pair<int, int> PII;

int prim(int n, vector<vector<PII>>& adj) {
    vector<bool> visited(n, false); // 记录节点是否已被加入生成树
    priority_queue<PII, vector<PII>, greater<PII>> pq; // 最小堆
    pq.push({0, 0}); // {权重，节点}
    int mstWeight = 0;
    int edgesUsed = 0;

    while (!pq.empty() && edgesUsed < n) {
        auto [weight, u] = pq.top(); pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        mstWeight += weight;
        edgesUsed++;

        for (auto& [v, w] : adj[u]) { // 遍历 u 的邻边
            if (!visited[v]) pq.push({w, v});
        }
    }

    return mstWeight;
}

说明：

• adj是邻接表，adj[u]包含了节点u的所有邻边，以{v, w}表示邻节点和边权。
• 使用最小堆（priority_queue）来选择最小的边，从而保证生成树的总权值最小。

总结

• Kruskal算法适用于稀疏图，需要排序所有边。
• Prim算法适用于密集图，通过最小堆实现贪心选择。

这两种算法都是解决最小生成树问题的经典方法，根据图的特性选择合适的算法可以提高效率。