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 表示图不连通
}

邻接矩阵实现

当 𝑚 接近 𝑛2 时,堆优化不如邻接矩阵的 𝑂(𝑛2)。每次暴力扫描未选点:

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] 跳过;重边保留最小的那条即可。
  • 选满 𝑛 个点即可结束;堆可能非空,不需要清空。

复杂度

写法时间空间适用
堆优化𝑂((𝑛+𝑚)log𝑛)𝑂(𝑛+𝑚)稀疏图
邻接矩阵𝑂(𝑛2)𝑂(𝑛2)稠密图

对应例题

  • 洛谷 P3366:【模板】最小生成树
  • 洛谷 P1546:最短网络 Agri-Net(稠密图,适合邻接矩阵)
  • 洛谷 P1195:口袋的天空(生成森林:对每个未访问块各跑一次)
源码位置