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

2023-12-18 19:29:45

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;
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/135069236
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。