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

Prim算法求最小生成树

• 核心思想：Prim 算法 类似于dijkstra算法 更新距离时改为到**集合(生成树)**的距离

  • 最小生成树长这样 每次迭代放一个最近(有边)点，一条最短边进生成树

  • 

  •   #include <cstring>
      #include <iostream>
      #include <algorithm>
      
      using namespace std;
      const int N = 510, INF = 0x3f3f3f3f;
      
      int  g[N][N];  //稠密图
      int d[N];  //记录到集合距离
      int n,m,res;  //res记录集合内总权值
      bool st[N];
      
      int Prim(){
          memset(d,0x3f,sizeof d); 
          d[1] = 0;
          
          for(int i=0;i<n;i++)
          {
              int t = -1;  //找最近的点
              for(int j = 1;j<=n;j++)  //找最近的点
              {
                  if(!st[j] && (t==-1 || d[t] > d[j]))  //找最近的点
                  {
                      t = j;
                  }
              }
              
              if(d[t] == INF) return INF;  //最短的距离是INF 说明没有联通的点
              res += d[t];  //t加入集合 总权值加上t的
              st[t] = true;
              
              for(int j=1;j<=n;j++) d[j] = min(d[j] , g[t][j]);  //用t更新其他店距集合的距离
          }
          
          return res;
          
      }
      
      int main(){
          cin>>n>>m;
          
          memset(g, 0x3f, sizeof g);
          
          while(m--)
          {
              int a,b,c;
              cin>>a>>b>>c;
              g[a][b] = g[b][a] = min(g[a][b], c);  //无向图建双向的边
              
          }
          
          int t = Prim();
          
          if(t == INF) puts("impossible");
          else cout<<t;
      }