最小生成树:Prim 算法和Kruskal 算法

在 C++ 中，实现最小生成树（MST）的常用算法有两种：Prim 算法和Kruskal 算法。这两种算法适用于加权无向图，用于寻找包含所有顶点的边的集合，使得边的总权重最小，且没有环路。

1. Prim 算法

Prim 算法通过贪心策略来构建 MST，从任意起始顶点开始，每次选择权重最小的边扩展 MST。

实现步骤

初始化一个集合 MST，包含图中的任意一个顶点。
找到从集合 MST 到剩余顶点中权重最小的边，并将该边加入 MST。
重复步骤 2，直到所有顶点都包含在 MST 中。

C++ 实现示例（使用优先队列）

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 定义一个结构体来表示边
struct Edge {
    int to, weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

// 使用 Prim 算法计算最小生成树的总权重
int primMST(const vector<vector<Edge>>& graph, int start) {
    int n = graph.size();  // 顶点数
    vector<bool> inMST(n, false);  // 标记顶点是否在 MST 中
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  // 最小堆

    int totalWeight = 0;
    pq.push({0, start});  // 起始顶点的权重为0

    while (!pq.empty()) {
        auto [weight, u] = pq.top();  // 获取权重最小的边
        pq.pop();

        if (inMST[u]) continue;  // 如果已经在 MST 中，跳过

        inMST[u] = true;  // 标记顶点 u 在 MST 中
        totalWeight += weight;  // 累加边的权重

        // 遍历 u 的所有邻接边
        for (const auto& edge : graph[u]) {
            int v = edge.to;
            int w = edge.weight;

            if (!inMST[v]) {
                pq.push({w, v});  // 将未加入 MST 的顶点及其权重放入优先队列
            }
        }
    }

    return totalWeight;
}

int main() {
    // 创建一个无向加权图
    int n = 5;  // 图中顶点数
    vector<vector<Edge>> graph(n);

    // 添加边
    graph[0].push_back(Edge(1, 2));
    graph[1].push_back(Edge(0, 2));

    graph[0].push_back(Edge(3, 6));
    graph[3].push_back(Edge(0, 6));

    graph[1].push_back(Edge(2, 3));
    graph[2].push_back(Edge(1, 3));

    graph[1].push_back(Edge(3, 8));
    graph[3].push_back(Edge(1, 8));

    graph[1].push_back(Edge(4, 5));
    graph[4].push_back(Edge(1, 5));

    graph[2].push_back(Edge(4, 7));
    graph[4].push_back(Edge(2, 7));

    // 从顶点 0 开始计算最小生成树的总权重
    int totalWeight = primMST(graph, 0);
    cout << "Minimum Spanning Tree Total Weight: " << totalWeight << endl;

    return 0;
}

代码解释

graph 是一个邻接表，每个顶点的邻接边存储在一个 vector 中。
priority_queue 用于选择当前权重最小的边。
inMST 数组用于标记哪些顶点已经在 MST 中。
算法的时间复杂度为 (O(E \log V))，其中 (E) 是边数，(V) 是顶点数。

2. Kruskal 算法

Kruskal 算法通过贪心策略来构建 MST，每次选择权重最小的边，添加到 MST 中，前提是不会形成环。

实现步骤

将图中的所有边按权重从小到大排序。
初始化一个并查集，用于判断是否会形成环。
依次选择权重最小的边，如果该边连接的两个顶点属于不同的集合，则将其加入 MST。
重复步骤 3，直到 MST 包含 (V-1) 条边。

C++ 实现示例（使用并查集）

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

using namespace std;

// 定义一个结构体来表示边
struct Edge {
    int from, to, weight;
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

// 并查集数据结构
struct UnionFind {
    vector<int> parent, rank;

    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int u) {
        if (u != parent[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;  // u 和 v 在同一个集合中

        // 联合集合，按秩合并
        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;
    }
};

// 使用 Kruskal 算法计算最小生成树的总权重
int kruskalMST(int n, vector<Edge>& edges) {
    // 将边按权重从小到大排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    UnionFind uf(n);  // 初始化并查集
    int totalWeight = 0;
    int edgesUsed = 0;

    // 遍历所有边
    for (const auto& edge : edges) {
        if (uf.unionSets(edge.from, edge.to)) {
            totalWeight += edge.weight;
            edgesUsed++;
            if (edgesUsed == n - 1) break;  // 当使用的边数达到 n-1 时，停止
        }
    }

    return totalWeight;
}

int main() {
    int n = 5;  // 图中顶点数
    vector<Edge> edges;

    // 添加边
    edges.push_back(Edge(0, 1, 2));
    edges.push_back(Edge(0, 3, 6));
    edges.push_back(Edge(1, 2, 3));
    edges.push_back(Edge(1, 3, 8));
    edges.push_back(Edge(1, 4, 5));
    edges.push_back(Edge(2, 4, 7));

    // 计算最小生成树的总权重
    int totalWeight = kruskalMST(n, edges);
    cout << "Minimum Spanning Tree Total Weight: " << totalWeight << endl;

    return 0;
}