C++如何实现一个最小生成树算法_C++图论之Prim与Kruskal算法详解-C++-PHP中文网

C++如何实现一个最小生成树算法_C++图论之Prim与Kruskal算法详解

下次还敢

发布： 2025-11-21 20:00:06

原创

651人浏览过

Prim算法从点出发，每次选最近顶点加入生成树，适合稠密图；Kruskal按边权排序贪心选取，用并查集判环，适合稀疏图；两者时间复杂度分别为O(V²)和O(E log E)，应根据图的密度选择。

c++如何实现一个最小生成树算法_c++图论之prim与kruskal算法详解

在图论中，最小生成树（Minimum Spanning Tree, MST）是连接无向连通图中所有顶点的一棵树，且边的权值总和最小。C++中常用的两种求解MST的算法是Prim算法和Kruskal算法。下面详细介绍它们的原理与实现方式。

Prim算法：从点出发构建最小生成树

Prim算法的核心思想是从一个起始顶点开始，逐步扩展生成树，每次选择与当前生成树相连且权值最小的边所连接的新顶点，直到覆盖所有顶点。

适用场景：稠密图（边数接近顶点数平方），使用邻接矩阵存储更高效。

Prim算法步骤：

立即学习“C++免费学习笔记（深入）”；

初始化一个布尔数组visited标记顶点是否已加入生成树，距离数组dist记录各顶点到生成树的最短距离
从任意起点（如0号顶点）开始，更新其邻接点的距离
每次从未访问顶点中选出dist最小的顶点u，将其加入生成树
用u更新其所有邻接点的距离
重复上述过程直到所有顶点都被访问

代码实现（邻接矩阵）：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
<p>const int INF = INT_MAX;</p><p>int prim(vector<vector<int>>& graph, int n) {
vector<int> dist(n, INF);
vector<bool> visited(n, false);
dist[0] = 0;
int totalWeight = 0;</p><pre class='brush:php;toolbar:false;'>for (int i = 0; i < n; i++) {
    int u = -1;
    for (int j = 0; j < n; j++) {
        if (!visited[j] && (u == -1 || dist[j] < dist[u]))
            u = j;
    }

    if (dist[u] == INF) return -1; // 图不连通
    visited[u] = true;
    totalWeight += dist[u];

    for (int v = 0; v < n; v++) {
        if (graph[u][v] != 0 && !visited[v] && graph[u][v] < dist[v]) {
            dist[v] = graph[u][v];
        }
    }
}
return totalWeight;

登录后复制

}

Kruskal算法：按边排序贪心选取

Kruskal算法基于贪心策略，将所有边按权值从小到大排序，依次尝试加入生成树，若加入后不形成环，则保留该边，否则跳过。

适用场景：稀疏图（边较少），使用边列表存储效率更高。

AssemblyAI

转录和理解语音的AI模型

查看详情

Kruskal算法关键点：

需要对边进行排序
使用并查集（Union-Find）判断是否形成环
当加入n-1条边时，生成树完成

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
<p>struct Edge {
int u, v, weight;
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};</p><p>class UnionFind {
vector<int> parent;
public:
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
}</p><pre class='brush:php;toolbar:false;'>int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    parent[find(x)] = find(y);
}

bool connected(int x, int y) {
    return find(x) == find(y);
}

登录后复制

};

int kruskal(vector<Edge>& edges, int n) { sort(edges.begin(), edges.end()); UnionFind uf(n); int totalWeight = 0; int edgesAdded = 0;

for (const Edge& e : edges) {
    if (!uf.connected(e.u, e.v)) {
        uf.unite(e.u, e.v);
        totalWeight += e.weight;
        edgesAdded++;
        if (edgesAdded == n - 1) break;
    }
}
return edgesAdded == n - 1 ? totalWeight : -1; // 不连通返回-1

登录后复制

}