最小生成树（kruskal 算法）

Mar 27, 2021

说明

此算法可以称为“加边法”，初始最小生成树边数为 0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

实现思路

把图中的所有边按代价从小到大排序；
把图中的 n 个顶点看成独立的 n 棵树组成的森林；
按权值从小到大选择边，所选的边连接的两个顶点 ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
重复(3),直到所有顶点都在一颗树内或者有 n-1 条边为止。

代码示例

#include <bits/stdc++.h>
using namespace std;
struct Edge
{
  int u, v, w;
} edge[200005];

int fa[5005], n, m, ans, eu, ev, cnt;

inline bool cmp(Edge a, Edge b)
{
  return a.w < b.w; //快排的依据
}

inline int find(int x)
{
  while (x != fa[x])
    x = fa[x] = fa[fa[x]];
  return x;
} //并查集模板，用while循环比递归版快

inline void kruskal()
{
  sort(edge, edge + m, cmp); //将边的权值排序
  for (int i = 0; i < m; i++)
  {
    eu = find(edge[i].u), ev = find(edge[i].v);
    if (euev)
      continue; //若出现环，则continue
    ans += edge[i].w; //更新答案
    fa[ev] = eu;
    cnt++;
    if (cntn - 1)
      break; //循环结束条件
  }
}
int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    fa[i] = i; //初始化并查集
  for (int i = 0; i < m; i++)
    scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
  kruskal();
  printf("%d", ans);
  return 0;
}