Kruskal算法

Kruskal 算法

Kruskal 算法是一种用于求解最小生成树的贪心算法。它的基本思想是通过选择边来逐步构建最小生成树，确保每一步都选择权值最小的边，同时避免形成环。

算法引入

假设你是一位城市道路规划者，下面是你的城市以及蓝图。

现在要求你建设其中的一些道路（每一条道路的建设需要金币），使每个城市之间都能互相到达，并且所花费的金币最少。
而你是算法高手，一下就想到了树这个数据结构，树是特殊的图，有向无环图，只要生成一颗树，就能满足其中任意两个城市可以互相到达的条件，现在要处理的就是划分金币最少。于是便有了最小生成树。

算法步骤

1. 初始化：将图中的所有边按照权值从小到大进行排序。

   struct Edge     // 存储边
   {
       int a, b, w;
       bool operator< (const Edge &W)const
       {
           return w < W.w;
       }
   }edges[M];
   
   sort(edges, edges + m);

2. 创建并查集：为每个顶点创建一个单元素集合，用于判断是否形成环。

   for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

3. 遍历边集合：按照排好序的边的顺序，依次检查每条边。

   for (int i = 0; i < m; i ++ )
   {
       int a = edges[i].a, b = edges[i].b, w = edges[i].w;//取出边的数据
   
       //合并操作
   }

4. 判断边的两个顶点是否在同一集合：如果不在同一集合，说明加入这条边不会形成环，则选择加入，并合并这两个顶点的集合。

   a = find(a), b = find(b);
   if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
   {
       p[a] = b;
       res += w;
       cnt ++ ;
   }

5. 重复步骤 4 直到最小生成树的边数达到 n-1（其中 n 为图中顶点的个数）。

   int n, m;       // n是点数，m是边数
   int p[N];       // 并查集的父节点数组
   
   struct Edge     // 存储边
   {
       int a, b, w;
   
       bool operator< (const Edge &W)const
       {
           return w < W.w;
       }
   }edges[M];
   
   int find(int x)     // 并查集核心操作
   {
       if (p[x] != x) p[x] = find(p[x]);
       return p[x];
   }
   
   int kruskal()
   {
       sort(edges, edges + m);
   
       for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集
   
       int res = 0, cnt = 0;
       for (int i = 0; i < m; i ++ )
       {
           int a = edges[i].a, b = edges[i].b, w = edges[i].w;
   
           a = find(a), b = find(b);
           if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
           {
               p[a] = b;
               res += w;
               cnt ++ ;
           }
       }
   
       if (cnt < n - 1) return INF;
       return res;
   }

   根据步骤得出，我们可以把上图的最小生成树的过程画出来。

封装模板

struct DSU
{
	std::vector<int> p, siz;
	DSU() {}
	DSU(int n) { init(n); }
	void init(int n)
	{
		p.resize(n);
		std::iota(p.begin(), p.end(), 0);
		siz.assign(n, 1);
	}
	int find(int x)
	{
		while (x != p[x])
		{
			x = p[x] = p[p[x]];
		}
		return x;
	}
	bool same(int x, int y) { return find(x) == find(y); }
	bool merge(int x, int y)
	{
		int px = find(x);
		int py = find(y);
		if (px == py)
		{
			return false;
		}
		siz[px] += siz[py];
		p[py] = px;
		return true;
	}
	int size(int x) { return siz[find(x)]; }
};
struct MST
{
	using TII = tuple<int,int,int>;
	int n;
	priority_queue<TII,vector<TII>,greater<TII>> eg;
	MST(int n) : n(n){}
	void add(int x,int y,int w)
	{
		eg.emplace(w,x,y);
	}
	int kruskal()
	{
		DSU dsu(n + 1);
		int ans = 0,cnt = 0,w,x,y;
		while(eg.size())
		{
			tie(w,x,y) = eg.top();
			eg.pop();
			if(dsu.same(x,y)) continue;
			dsu.merge(x,y);
			ans += w;
			cnt ++ ;
		}
		if(cnt < n - 1) return INF;
		return ans;
	}
};

题目练习

P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)