C++实现最小生成树时，Prim算法与Kruskal算法有何区别？

Question

在使用C++实现最小生成树（MST）时，Prim算法和Kruskal算法是两种最常见的贪心算法。它们在思想、数据结构、适用场景等方面存在显著差异。Prim算法从顶点出发，逐步扩展生成树，适合用邻接矩阵或优先队列实现，适用于稠密图；而Kruskal算法从边出发，按权重从小到大选择边，并利用并查集判断是否形成环，更适合稀疏图。两者在时间复杂度、实现逻辑和代码结构上各有不同。本文将围绕C++实现角度，深入探讨Prim与Kruskal算法在最小生成树中的区别，帮助开发者根据实际场景选择更优算法。

Answer 1

一、最小生成树（MST）概述

最小生成树是图论中的经典问题之一，广泛应用于网络设计、城市道路规划等领域。在给定的带权无向连通图中，MST是一棵包含所有顶点的树，使得所有边的权重之和最小。

Prim算法和Kruskal算法是求解MST的两种主流贪心算法，它们各有特点，适用于不同的图结构和应用场景。

二、Prim算法与Kruskal算法的核心思想对比

• Prim算法：从一个顶点开始，逐步加入与当前生成树连接的最小权值边，最终覆盖所有顶点。
• Kruskal算法：将所有边按权重从小到大排序，依次选择不形成环的边，直到连接所有顶点。

三、算法实现所需的数据结构分析

算法	核心数据结构	说明
Prim	优先队列（最小堆）、邻接矩阵或邻接表	优先队列用于选择下一个最小权值的顶点，邻接表或矩阵用于存储图结构。
Kruskal	并查集（Union-Find）、排序后的边数组	并查集用于检测环，边数组按权重排序后依次处理。

四、C++实现代码结构与逻辑分析

4.1 Prim算法实现（邻接表 + 优先队列）

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

void prim(int n, vector<vector<pii>>& adj) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<int> key(n, INT_MAX);
    vector<bool> inMST(n, false);
    pq.push({0, 0});
    key[0] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true;

        for (auto& p : adj[u]) {
            int v = p.first;
            int weight = p.second;
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                pq.push({key[v], v});
            }
        }
    }
}
  

4.2 Kruskal算法实现（并查集 + 边排序）

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

vector<Edge> edges;
vector<int> parent;

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

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

void kruskal(int n) {
    sort(edges.begin(), edges.end());
    parent.resize(n);
    iota(parent.begin(), parent.end(), 0);
    vector<Edge> mst;
    for (auto& e : edges) {
        if (find(e.u) != find(e.v)) {
            mst.push_back(e);
            unite(e.u, e.v);
        }
    }
}
  

五、时间复杂度对比

两者的时间复杂度取决于图的表示方式和使用的数据结构：

算法	时间复杂度	说明
Prim（邻接表 + 优先队列）	O(E log V)	适用于稀疏图，效率较高。
Prim（邻接矩阵）	O(V²)	适合稠密图，实现简单。
Kruskal	O(E log E)	主要开销在排序边，适用于稀疏图。

六、适用场景与性能对比分析

选择Prim或Kruskal算法，应根据图的密度、实现复杂度和性能需求进行权衡：

• 稠密图：顶点数V接近边数E，适合使用Prim算法（邻接矩阵实现）。
• 稀疏图：边数E远小于V²，更适合Kruskal算法或Prim算法（邻接表+优先队列）。

七、算法流程图对比

7.1 Prim算法流程图

graph TD
      A[初始化所有顶点为未访问]
      B[选择一个起始顶点加入MST]
      C[更新所有与MST相邻的顶点的最小边权]
      D[选择最小边权的顶点加入MST]
      E[重复C-D直到所有顶点加入]
      A --> B
      B --> C
      C --> D
      D --> E

7.2 Kruskal算法流程图

graph TD
      F[将所有边按权重排序]
      G[初始化并查集结构]
      H[依次选择最小边]
      I[判断是否形成环]
      J[若不形成环则加入MST]
      K[重复H-J直到所有顶点连接]
      F --> G
      G --> H
      H --> I
      I -->|是| J
      J --> K
      I -->|否| H

八、开发者选择建议

在实际开发中，开发者应根据以下因素选择算法：

• 图的规模与密度
• 是否需要频繁查询或动态更新
• 对代码可读性和维护性的要求
• 是否已有现成的图结构表示