Kruskal 算法¶

简介¶

Kruskal 算法是一种常见、好写的最小生成树算法，发明者为 Kruskal。使用了贪心、排序等算法和并查集。

算法思想¶

我们可以维护一个森林，然后每一次取出最优的边，判断这两个结点在不在同一个树当中，如果在，那么就说明他们已经联通了，就抛弃掉这条边；否则，就将这条边所在的两棵树合并，并累加答案。抽象一点，其实就是维护一堆集合，而这个任务可以交给并查集轻松地处理。

如果排序时间复杂度为 \(\mathcal O(m\log_2 m)\)，并查集时间复杂度为 \(\mathcal O(m\alpha(n))\)，那么该算法的时间复杂度为 \(\mathcal O(m\log_2 m)\)。对于值域范围比较小的图，我们可以使用基数排序或者计数排序，那么时间复杂度就能接近 \(\mathcal O(m\alpha(n))\)。

代码

int F(int x) {
  return f[x] == x ? x : f[x] = F(f[x]);
}

void U(int u, int v) {
  u = F(u), v = F(v);
  u != v && (f[u] = v);
}

int kruskal() {
  sort(e + 1, e + m + 1, [](const Edge &a, const Edge &b) {
    return a.w < b.w;
  });
  int ans = 0;
  for (int i = 1; i <= m; i++) {
    if (F(e[i].u) == F(e[i].v)) {
      continue;
    }
    U(e[i].u, e[i].v);
    ans += e[i].w;
  }
  return ans;
}

最大生成树也是同理，只需要将排序当中的小于号改成大于号就行了。

注意

Kruskal 算法对边 \(m\) 的大小较为依赖，因此在完全图（\(m\approx n^2\) ）当中，Kruskal 算法可能会在排序的时候被卡，但是 Prim 算法的 \(\mathcal O(n^2~)\) 就可以通过。如果你不想出现这种尴尬的情况，就可以学习一下 Prim 算法。

Kruskal 算法¶

简介¶

算法思想¶

评论