Kuskal算法求最小生成树

Kruskal算法适用的领域

• 稀疏图的最小生成树的解决方案

Kruskal算法的优点：

• 不需要邻接表和邻接矩阵来存储图的信息直接定义一个结构体即可

struct Edge
{
	int a, b, w;
    
	bool operator< (const Edge &W) const
	{
		return w < W.w;
	}
}edges[N];

Kruskal算法流程

1. 将图的边从大到小进行排序(数组排序)

   sort(edges, edges + m); // m代表图的边数
   

2. 将排好序的每一条(不在集合中)边加入到集合中去。

   • 注意最后输出结果为最小生成树边权重之和 --- res;

   • 用一个变量记录生成树集合点的个数 --- cnt；

   • 用并查集判断这个点是否在最小生成树集合中 --- p[N]

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

3. Kruskal函数

   int kruskal()
   {
       for (int i = 1; i <= n; i ++) p[i] = i;
   
       sort(edges, edges + m);	// 对边进行排序
   
       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;
       else return res;
   }
   

   参考代码

   #include <bits/stdc++.h>
   
   using namespace std;
   
   const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
   
   int n, m;
   int p[N];
   
   int find(int x)
   {
       if(p[x] != x) p[x] = find(p[x]);
       return p[x];
   }
   
   struct Edge
   {
       int a, b, w;
   
       bool operator< (const Edge &W) const
       {
           return w < W.w;
       }
   }edges[M];
   
   int kruskal()
   {
       for (int i = 1; i <= n; i ++) p[i] = i;
   
       sort(edges, edges + m);
   
       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;
       else return res;
   }
   
   int main()
   {
       cin >> n >> m;
   
       int a, b, w;
   
       for (int i = 0; i < m; i ++)
       {
           cin >> a >> b >> w;
           edges[i] = {a, b, w};
       }
   
       int t = kruskal();
   
       if(t == INF) puts("impossible");
       else cout << t;
   
       return 0;
   }