算法基础之Kruskal算法求最小生成树

Kruskal算法求最小生成树

• 核心思想: Kruskal算法 : 将每组数据根据权重排序 小的在前面 判断ab是否已经联通(并查集) 没有的话加上一条边

  •   #include <cstring>
      #include <iostream>
      #include <algorithm>
      
      using namespace std;
      const int N = 100010 , M = 2*N , INF = 0x3f3f3f3f;
      
      int n,m;
      int p[N];
      
      struct edge{
          int a,b,w;
          
          bool operator< (const edge &W) const{  //重载 <  根据w权值排序
              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);  //找到ab祖宗 
              if(a!= b)  //不联通
              {
                  p[a] = b;
                  res +=w;
                  cnt ++ ;
              }
          }
          if(cnt < n-1) return INF;  //cnt为边数 若<n-1 说明不是一颗完整树(前提)
          return res;
      }
      int main()
      {
          cin>>n>>m;
          
          for(int i=0;i<m;i++)
          {
              int a,b,w;
              cin>>a>>b>>w;
              edges[i] = {a,b,w};
          }
          
          int t = kruskal();
          
          if(t == INF) puts("impossible");
          else cout<<t;
      }