[数据结构·图] 最小生成树——普里姆算法

最小生成树：普里姆算法 (Prim) - 邻接表版

1. 算法核心思想

Prim 算法是一种 贪心算法。它的逻辑类似于“通过不断吞并最近的邻居来扩张领土”。

1. 集合划分：将顶点分为两个集合：
   • 已选集合 ($S$)：已经在最小生成树中的点。
   • 未选集合 ($V-S$)：还没有加入树的点。
2. 贪心策略：每次从“未选集合”中找到一个顶点，使得它与“已选集合”之间的边权值最小。
3. 更新：将该顶点加入 $S$，并更新它的邻居到 $S$ 的距离。

---

2. 数据结构设计

由于使用邻接表，我们无法像邻接矩阵那样 $O(1)$ 查边，也无法高效地扫描所有点的最短距离。因此，我们需要配合 优先队列 (Min-Heap) 来快速获取当前距离生成树最近的点。

• 图存储：vector<vector<pair<int, int>>> adj (存目标点和权值)。
• 距离数组：dist[i] 记录节点 $i$ 到当前生成树集合的最小距离（注意：不是到源点的距离，那是 Dijkstra）。
• 访问标记：vis[i] 记录节点是否已经加入生成树。
• 优先队列：priority_queue，存储 {距离, 节点编号}，每次弹出距离最小的点。

---

3. C++ 代码实现 (堆优化版)

#include <iostream>
#include <vector>
#include <queue>
#include <functional> // for greater

using namespace std;

const int INF = 0x3f3f3f3f;

// 定义边的结构：目标点和权值
// 这里为了方便优先队列排序，也可以直接用 pair<int, int>
// pair<int, int> 的默认排序是先比较 first，再比较 second
typedef pair<int, int> PII; // {distance, u}

// 普里姆算法核心函数
// n: 节点数, adj: 邻接表
int prim(int n, const vector<vector<pair<int, int>>>& adj) {
    // 1. 初始化
    int total_weight = 0;      // 最小生成树的总权值
    int count = 0;             // 记录加入MST的节点数量
    vector<int> dist(n + 1, INF); // 节点到生成树的最短距离
    vector<bool> vis(n + 1, false); // 标记是否已加入MST
    
    // 小根堆：存储 {当前距离, 节点编号}
    // greater 让优先队列变成小顶堆（默认是大顶堆）
    priority_queue<PII, vector<PII>, greater<PII>> pq;

    // 2. 从起点（通常是节点1）开始
    dist[1] = 0;
    pq.push({0, 1}); // {距离0, 节点1}

    while (!pq.empty()) {
        // 3. 取出距离生成树最近的点
        auto [d, u] = pq.top();
        pq.pop();

        // 如果这个点已经加入过 MST，跳过（因为堆中可能存在旧的劣质记录）
        if (vis[u]) continue;

        // 4. 将该点加入 MST
        vis[u] = true;
        total_weight += d;
        count++;

        // 5. 考察 u 的所有邻居 v
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;

            // 如果 v 还没加入 MST，并且通过 u 连接 v 的代价更小
            if (!vis[v] && w < dist[v]) {
                dist[v] = w;      // 更新 v 到 MST 的最短距离
                pq.push({w, v});  // 将新的距离压入堆
            }
        }
    }

    // 如果加入的节点数小于 n，说明图不连通，无法生成 MST
    if (count < n) return -1; 
    
    return total_weight;
}

int main() {
    // 示例输入：
    // 4 5  (4个点，5条边)
    // 1 2 1
    // 1 3 2
    // 2 3 1
    // 2 4 3
    // 3 4 2
    
    int n, m;
    if (cin >> n >> m) {
        // 使用邻接表存储带权无向图
        vector<vector<pair<int, int>>> adj(n + 1);

        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            // 无向图，双向添加
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        int result = prim(n, adj);

        if (result == -1) {
            cout << "The graph is disconnected, MST does not exist." << endl;
        } else {
            cout << "Total Weight of MST: " << result << endl;
        }
    }
    return 0;
}
````

---

## 4. 关键点深度解析

### 4.1 为什么要用 `visited` 数组？

在优先队列中，同一个节点可能会被多次压入。

例如：点 $C$ 离 $MST$ 的距离原先是 10（通过点 A），后来发现通过点 B 距离只有 5。我们会把 {5, C} 压入堆，但旧的 {10, C} 还在堆里。

当 {5, C} 弹出并处理完后，vis[C] 变为 true。等轮到 {10, C} 弹出时，通过 if (vis[u]) continue; 这一行代码可以直接忽略它。这叫懒惰删除 (Lazy Deletion)。

### 4.2 `dist` 数组的含义

在 Dijkstra 算法中，dist[i] 代表“从起点到 $i$ 的最短路径长度”。

但在 Prim 算法中，dist[i] 代表 “节点 $i$ 到当前生成的这棵树（集合 $S$）的最短距离”。这是两者最大的区别。

### 4.3 为什么适合邻接表？

- **普通 Prim (邻接矩阵)**：每次寻找最近点需要扫描 `dist` 数组，复杂度 $O(V)$，总复杂度 $O(V^2)$。
    
- **堆优化 Prim (邻接表)**：
    
    - 寻找最近点：$O(\log E)$ (从堆弹出的开销)。
        
    - 更新邻居：每条边扫描一次，堆操作一次。
        
    - **总时间复杂度**：$O(E \log V)$ 或 $O(E \log E)$。
        
    - 在稀疏图（$E \ll V^2$）中，这种写法远快于邻接矩阵版。
        

---

## 5. 复杂度分析

| **版本**       | **存储结构** | **查找最小值方式**    | **时间复杂度**         | **适用场景**       |
| ------------ | -------- | -------------- | ----------------- | -------------- |
| **朴素 Prim**  | 邻接矩阵     | 线性扫描数组         | $O(V^2)$          | 稠密图 (点少边多)     |
| **堆优化 Prim** | **邻接表**  | **优先队列 (二叉堆)** | **$O(E \log V)$** | **稀疏图 (点多边少)** |

由于大多数工程应用和算法题目给出的图都是稀疏图（例如城市路网），使用**邻接表 + 优先队列**是更加通用的选择。




# Prim 算法 vs Dijkstra 算法逻辑对比

### 1. 核心公式区别
- **Dijkstra (最短路):** 寻找路径总和最小。
$$
dist[v] = \min(dist[v], dist[u] + weight(u, v))
$$
- **Prim (最小生成树):** 寻找连接节点的单边最小。
$$
dist[v] = \min(dist[v], weight(u, v))
$$

### 2. 修正后的 Prim 代码片段
```cpp
void prim(vector<vector<pair<int,int>>> &adj, int n, int start, vector<int> &parent) {
    vector<int> dist(n + 1, INF);
    vector<bool> vis(n + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start}); // 注意：pq.push({weight, node})

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (vis[u]) continue;
        vis[u] = true; // 正式加入最小生成树

        for (auto &edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            // 如果 v 不在树中，且边 (u, v) 的权重小于 v 到树的当前距离
            if (!vis[v] && w < dist[v]) { 
                dist[v] = w;      // 更新为边权，而不是累加和
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

---

4. 为什么要这样改？

• Dijkstra： 想象你在算油费。你从 A 经过 B 到 C，油费是 A->B 加上 B->C 的总和。
• Prim： 想象你在拉光缆。你的光缆已经铺到了 B，现在要连到 C。你只关心 B 到 C 这段线缆要买多长，而不关心之前从 A 到 B 花了多少钱。

5. 小细节提示

你的代码中有一处小笔误：

• pq.push(0, start); 应该是 pq.push({0, start});（对于 std::pair 需要花括号）。

现在你能理解为什么你的代码会跑出“最短路径树”而不是“最小生成树”了吗？