1. 算法概述

普里姆算法（Prim's Algorithm）是一种用于求解最小生成树（MST） 的贪心算法。与 Kruskal 算法不同，Prim 算法以顶点为中心，从一个起始顶点开始，每次选择一条连接"已选顶点集合"与"未选顶点集合"的最小权重边，将对应顶点加入已选集合。该算法特别适用于稠密图（边数较多的图）。

2. 核心思想

• 顶点扩展：从一个任意起点开始，逐步将顶点加入 MST。
• 贪心选择：每次找到一条边 (u, v)，其中 u 在已选集合中，v 不在，且边的权重最小。
• 优先队列优化：使用最小堆（priority_queue）维护候选边，每次 O(log E) 取出最小边。
• visited 数组：标记顶点是否已加入 MST，避免重复处理。

3. 算法步骤/伪代码

Prim(G, start):
    priority_queue<Edge> pq   // 最小堆，按边权排序
    visited[V] = false
    pq.push({start, start, 0})   // 虚拟起始边
    total_weight = 0
    edge_count = 0

    while pq is not empty and edge_count < V:
        (u, v, w) = pq.top(); pq.pop()
        if visited[v]: continue
        visited[v] = true
        total_weight += w
        edge_count++
        for each neighbor (next, weight) of v:
            if not visited[next]:
                pq.push({v, next, weight})

    return total_weight

4. C++ 代码实现

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

// ==================== 优先队列优化版 Prim 算法 ====================
struct Edge {
    int to, weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

// 用于优先队列的比较器
struct Node {
    int vertex, weight;
    Node(int v, int w) : vertex(v), weight(w) {}
    bool operator>(const Node& other) const {
        return weight > other.weight; // 小顶堆
    }
};

int prim(int V, vector<vector<Edge>>& graph, int start = 0) {
    vector<bool> visited(V, false);
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    // 将起点加入优先队列
    pq.push(Node(start, 0));
    int totalWeight = 0;
    int edgeCount = 0;

    while (!pq.empty() && edgeCount < V) {
        Node node = pq.top();
        pq.pop();

        if (visited[node.vertex]) continue;

        visited[node.vertex] = true;
        totalWeight += node.weight;
        edgeCount++;

        // 遍历邻接边，将未访问的邻居加入队列
        for (const Edge& e : graph[node.vertex]) {
            if (!visited[e.to]) {
                pq.push(Node(e.to, e.weight));
            }
        }
    }

    // 若未访问全部顶点，说明图不连通
    if (edgeCount < V) return -1;
    return totalWeight;
}

// ==================== 朴素 O(V²) 版 Prim（适合稠密图） ====================
int primDense(int V, vector<vector<int>>& adjMatrix) {
    vector<bool> visited(V, false);
    vector<int> minDist(V, INT_MAX);
    minDist[0] = 0;
    int totalWeight = 0;

    for (int i = 0; i < V; i++) {
        // 选取未访问中 minDist 最小的顶点
        int u = -1;
        for (int j = 0; j < V; j++) {
            if (!visited[j] && (u == -1 || minDist[j] < minDist[u])) {
                u = j;
            }
        }

        if (minDist[u] == INT_MAX) return -1; // 不连通

        visited[u] = true;
        totalWeight += minDist[u];

        // 更新邻居的 minDist
        for (int v = 0; v < V; v++) {
            if (!visited[v] && adjMatrix[u][v] < minDist[v]) {
                minDist[v] = adjMatrix[u][v];
            }
        }
    }

    return totalWeight;
}

// ==================== 测试 ====================
int main() {
    // 示例：5 个顶点，无向带权图
    //      (0)
    //   2 / | \ 3
    //   (1) | (2)
    //   4 \ | / 6
    //      (3)---(4)
    //         1
    int V = 5;
    vector<vector<Edge>> graph(V);

    // 添加边（无向图，需添加双向）
    auto addEdge = [&](int u, int v, int w) {
        graph[u].push_back(Edge(v, w));
        graph[v].push_back(Edge(u, w));
    };
    addEdge(0, 1, 2);
    addEdge(0, 2, 3);
    addEdge(0, 3, 6);
    addEdge(1, 3, 4);
    addEdge(2, 3, 6);
    addEdge(3, 4, 1);

    int result = prim(V, graph, 0);
    cout << "最小生成树总权重 (堆优化): " << result << endl;
    // 期望输出: 10   (边: 0-1(2), 0-2(3), 3-4(1), 1-3(4))

    // 测试朴素版
    vector<vector<int>> adjMatrix(V, vector<int>(V, INT_MAX));
    for (int i = 0; i < V; i++) adjMatrix[i][i] = 0;
    adjMatrix[0][1] = adjMatrix[1][0] = 2;
    adjMatrix[0][2] = adjMatrix[2][0] = 3;
    adjMatrix[0][3] = adjMatrix[3][0] = 6;
    adjMatrix[1][3] = adjMatrix[3][1] = 4;
    adjMatrix[2][3] = adjMatrix[3][2] = 6;
    adjMatrix[3][4] = adjMatrix[4][3] = 1;

    int result2 = primDense(V, adjMatrix);
    cout << "最小生成树总权重 (朴素版): " << result2 << endl;

    return 0;
}

运行示例

最小生成树总权重 (堆优化): 10
最小生成树总权重 (朴素版): 10

5. 复杂度分析

• 堆优化版时间复杂度：O((V + E) log V)
  • 每个顶点入队一次、出队一次：O(V log V)
  • 每条边被检查一次并可能入队：O(E log V)
• 朴素版时间复杂度：O(V²) —— 适合完全图或接近完全图的稠密场景。
• 空间复杂度：O(V + E)，存储邻接表和 visited 数组。

图类型	推荐算法	复杂度
稀疏图 (E ≈ V)	Kruskal	O(E log E)
稠密图 (E ≈ V²)	Prim (朴素)	O(V²)
中等图	Prim (堆优化)	O((V+E) log V)

6. 应用场景

场景	说明
城市管网设计	供水/供气管道的最短总长度规划
集成电路布线	最小化芯片上各模块间的连接线总长
近似算法	旅行商问题（TSP）的 MST 近似解
图像处理	最小生成树分割（MST-based Segmentation）
网络广播	最小化广播消息的总传输代价

7. 经典例题

最小生成树模板题（洛谷 P3366 / POJ 1258）

题目描述：给出一个无向图，求出最小生成树。如果图不连通，输出 orz。

解题思路：

1. 选用 Prim 堆优化版处理一般稀疏/中等图。
2. 如果最终访问的顶点数 < V，说明图不连通，返回 -1。
3. 对于完全图场景（如 POJ 1258 Agri-Net，n ≤ 100，给出邻接矩阵），直接用朴素 O(V²) 版。

代码要点：

• 优先队列存储 {顶点, 到MST的最小边权}。
• visited 数组避免重复处理。
• 出队时若已访问则跳过（lazy deletion 技巧）。

对比 Kruskal

• Kruskal：基于边排序 + 并查集，适合边数少的稀疏图，实现直观。
• Prim：基于顶点扩展 + 优先队列，适合边数多的稠密图，可优化到 O(V²) 朴素版。
• 两者都是经典的 MST 贪心算法，理论上等价，实际选用取决于图的密度。