Prim
进阶Prim 从一个点出发贪心扩展，适合稠密图的最小生成树。
// 算法讲解
Prim
输入节点数和带权边，观察 Prim 从节点 0 扩展 MST 的过程。
待机
速度 中
待机 ⌨1int prim(int V, vector<vector<pair<int,int>>>& adj) {
2 vector<int> key(V, INT_MAX);
3 vector<bool> inMST(V, false);
4 key[0] = 0;
5 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
6 pq.push({0, 0});
7 int total = 0;
8 while (!pq.empty()) {
9 auto [w, u] = pq.top(); pq.pop();
10 if (inMST[u]) continue;
11 inMST[u] = true;
12 total += w;
13 for (auto [v, weight] : adj[u])
14 if (!inMST[v] && weight < key[v]) {
15 key[v] = weight;
16 pq.push({key[v], v});
17 }
18 }
19 return total;
20}
复杂度分析
时间 O((V+E) log V)
空间 O(V)
最优 O(V log V) 稠密图
最坏 O((V+E) log V)
算法讲解
Prim 从一个初始节点出发，维护一个"已在树中"的集合。
每轮从连接树内外的所有边中选权值最小的一条，将新节点加入树中。
用优先队列优化后时间复杂度为 O((V+E) log V)，适合稠密图。
和 Kruskal 不同，Prim 是"加点法"而非"加边法"，两者殊途同归。