Prim 算法实现
Prim 算法的堆优化与邻接矩阵实现,含调用示例和实现细节。时间 O((n + m) log n),空间 O(n + m) · 标签 图论 / 最小生成树 / Prim / 实现
本页只放实现;算法思想与正确性见 Prim 算法。
使用约定
- 图用 0-index 的邻接表
vector<vector<pair<int, long long>>>表示。 - 返回 MST 的总权值;图不连通时返回
-1。 - 边权用
long long。
堆优化实现
long long prim(int n, const vector<vector<pair<int, long long>>>& g, int s = 0) {
const long long INF = (1LL << 62);
vector<long long> dist(n, INF);
vector<char> used(n, false);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
dist[s] = 0;
pq.push({0, s});
long long ans = 0;
int cnt = 0;
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (used[u]) continue; // 懒惰删除:跳过过期条目
used[u] = true;
ans += d;
++cnt;
for (auto [v, w] : g[u]) {
if (!used[v] && w < dist[v]) {
dist[v] = w;
pq.push({w, v});
}
}
}
return cnt == n ? ans : -1; // -1 表示图不连通
}邻接矩阵实现
当 接近 时,堆优化不如邻接矩阵的 。每次暴力扫描未选点:
long long primDense(int n, const vector<vector<long long>>& w) {
const long long INF = (1LL << 62);
vector<long long> dist(n, INF);
vector<char> used(n, false);
dist[0] = 0;
long long ans = 0;
for (int it = 0; it < n; ++it) {
int u = -1;
for (int v = 0; v < n; ++v) {
if (!used[v] && (u == -1 || dist[v] < dist[u])) u = v;
}
if (u == -1 || dist[u] == INF) return -1;
used[u] = true;
ans += dist[u];
for (int v = 0; v < n; ++v) {
if (!used[v] && w[u][v] < dist[v]) dist[v] = w[u][v];
}
}
return ans;
}调用示例
int n, m;
cin >> n >> m;
vector<vector<pair<int, long long>>> g(n);
for (int i = 0; i < m; ++i) {
int u, v;
long long w;
cin >> u >> v >> w;
--u;
--v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
cout << prim(n, g) << '\n';实现细节
INF取1LL << 62,要远大于任何可能的边权和。- 堆里会有同一顶点的多条过期记录,必须
if (used[u]) continue跳过。 dist的松弛是min(dist[v], w),不是min(dist[v], dist[u] + w)。- 图不连通时
cnt != n,返回-1。 - 1-index 输入先
--u; --v;;邻接矩阵写法同理。 - 自环会被
used[u]跳过;重边保留最小的那条即可。 - 选满 个点即可结束;堆可能非空,不需要清空。
复杂度
| 写法 | 时间 | 空间 | 适用 |
| 堆优化 | 稀疏图 | ||
| 邻接矩阵 | 稠密图 |
对应例题
- 洛谷 P3366:【模板】最小生成树
- 洛谷 P1546:最短网络 Agri-Net(稠密图,适合邻接矩阵)
- 洛谷 P1195:口袋的天空(生成森林:对每个未访问块各跑一次)