最小生成树c++代码

最小生成树（Minimum Spanning Tree，简称M）是一种在连通图中找到最小权重生成树的算法。其中，常用的算法有Prim算法和Kruskal算法。下面是Prim算法和Kruskal算法的C++代码示例：

1. Prim算法实现最小生成树：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;

// 边的结构体
struct Edge {
    int to;     // 边的终点
    int weight; // 边的权重
};

// Prim算法实现最小生成树
int prim(vector<vector<Edge>>& graph) {
    int n = graph.size(); // 图的节点数
    vector<int> dist(n, INF); // 存储节点到最小生成树的最短距离
    vector<bool> visited(n, false); // 记录节点是否已经加入最小生成树
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小顶堆

    int totalWeight = 0; // 最小生成树的总权重

    // 从节点0开始构建最小生成树
    dist = 0;
    pq.push(make_pair(0, 0));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) {
            continue;
        }
        visited[u] = true;

        for (const auto& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;
            if (!visited[v] && weight < dist[v]) {
                dist[v] = weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    // 计算最小生成树的总权重
    for (int i = 0; i < n; ++i) {
        totalWeight += dist[i];
    }

    return totalWeight;
}

int main() {
    int n, m; // 节点数和边数
    cin >> n >> m;

    vector<vector<Edge>> graph(n); // 图的邻接表表示

    // 读入边的信息
    for (int i = 0; i < m; ++i) {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph[u].push_back({v, weight});
        graph[v].push_back({u, weight});
    }

    int totalWeight = prim(graph);
    cout << "最小生成树的总权重为：" << totalWeight << endl;

    return 0;
}

2. Kruskal算法实现最小生成树：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 边的结构体
struct Edge {
    int from;   // 边的起点
    int to;     // 边的终点
    int 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 x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

private:
    vector<int> parent; // 存储节点的父节点
    vector<int> rank;   // 存储节点的秩
};

// Kruskal算法实现最小生成树
int kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    UnionFind uf(n); // 并查集
    int totalWeight = 0; // 最小生成树的总权重

    for (const auto& edge : edges) {
        int from = edge.from;
        int to = edge.to;
        int weight = edge.weight;

        if (uf.find(from) != uf.find(to)) {
            uf.unite(from, to);
            totalWeight += weight;
        }
    }

    return totalWeight;
}

int main() {
    int n, m; // 节点数和边数
    cin >> n >> m;

    vector<Edge> edges(m); // 存储边的信息

    // 读入边的信息
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].from >> edges[i].to >> edges[i].weight;
    }

    int totalWeight = kruskal(edges, n);
    cout << "最小生成树的总权重为：" << totalWeight << endl;

    return 0;
}

希望对你有帮助！如果有任何问题，请随时提问。