Prim 算法¶
简介¶
Prim 算法是另外一种常见并且十分好写的最小生成树算法。Prim 算法的中心思想和 Kruskal 不同，它是每一次选择一个点，而非像 Kruskal 算法一样每次选择一个点。
算法思想¶
我们每一次都选择一个距离起始节点最近的一个结点，然后往旁边拓展，更新到结点的距离，接着不断加入生成树当中，最后就能求出一颗最小生成树。跟 Dijkstra 特别像，可以利用距离不断增大的拓扑序来使用二叉堆来快速选择最近的结点。
朴素算法时间复杂度为 \(\mathcal O(n^2)\)，加入堆优化之后时间复杂度为 \(\mathcal O(m\log_2 n)\)，优先队列时间复杂度为 \(\mathcal O(m\log_2 m)\)。对于 \(m\approx n^2\) 的题目当中，一般都不会使用 Kruskal 算法，因为 Kruskal 算法比较依赖 \(m\) 的大小，而 \(\mathcal O(n^2)\) 的朴素 Prim 更适合求解此类问题。需要注意的是，这时候就别再加堆优化了，不然时间复杂度就会与 Kruskal 一样。
代码
void prim() {
fill(d + 1, d + n + 1, 1e9);
for (q.emplace(1, 0), d[1] = 0; q.size(); ) {
auto t = q.top();
ans += t.v, q.pop();
if (f[t.to]) {
continue;
}
f[t.to] = 1;
for (auto i : e[t.to]) {
if (i.v < d[i.to]) {
q.emplace(i.to, d[i.to] = i.v);
}
}
}
}