• 【图论——第七讲】Pirm算法求最小生成树问题及其堆优化


    ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客:面向阿尼亚学习
    算法学习笔记系列持续更新中~

    阿



    一、前言

    最小生成树定义:

    一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。

    最小生成树其实是最小权重生成树的简称


    二、Pirm算法求最小生成树

    时间复杂度 O(n^2)

    Prim 算法采用的是一种贪心的策略。(Prim算法和Dijkstra算法思路相似)

    Prim算法简述

    每次将离连通部分的最近的点和点对应的边加入的连通部分,连通部分逐渐扩大,最后将整个图连通起来,并且边长之和最小。

    实现步骤

    int prim() {
        memset(dist, 0x3f, sizeof dist);//初始化为无限大
    
        for (int i = 0; i < n; i++) {//遍历n个点
        
     //1.找到集合距离最近的点
            int t = -1;//初始化为没有找到的点
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;//更新
                }
            }
           //不是第一个取出的节点,并且当前节点的距离为INF,表示没有和集合中点相连的边
            if (i && dist[t] == INF) return INF;
           //不是第一个取出的节点,是其他点与集合中的连接线(最小边)
            if (i) res += dist[t];
     //2.更新当前最短边权点t到集合的距离(保留最小的值,如果比之前最短t到集合的距离还小,更新)
            for (int j = 1; j <= n; j++) {
                dist[j] = min(dist[j], g[t][j]);
            }
             st[t] = true;//加入集合
        }
    
        return res;
    
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    Prim算法与Dijkstra算法的区别

    //Dijkstra算法是更新不在集合中的点 离起点的距离
    dist[j]=min(dist[j], dist[t]+g[t][j])
    
    • 1
    • 2
    Prim是更新不在集合中的点 离集合S的距离
    dist[j] = min(dist[j], g[t][j])
    
    • 1
    • 2

    例题:

    给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。
    求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。

    输入样例:
    4 5
    1 2 1
    1 3 2
    1 4 3
    2 3 2
    3 4 4
    输出样例:
    6

    #include<iostream>
    #include<cstring>
    
    using namespace std;
    const int N = 510, INF = 0x3f3f3f3f;
    int dist[N], g[N][N];    // 存储其他点到当前最小生成树的距离,邻接矩阵,存储所有边
    int n, m;
    bool st[N];  // 存储每个点是否已经在生成树中
    int res = 0;
    
    int prim() {
        memset(dist, 0x3f, sizeof dist);//初始化距离数组为一个很大的数
    
        for (int i = 0; i < n; i++) {
    
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
    
            if (i && dist[t] == INF) return INF;
            st[t] = true;
    
            if (i) res += dist[t];
    
            for (int j = 1; j <= n; j++) {
                dist[j] = min(dist[j], g[t][j]);
            }
        }
    
        return res;
    
    }
    
    int main() {
        memset(g, 0x3f, sizeof g);
        cin >> n >> m;
    
        for (int i = 0; i < m; i++) {
            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) cout<<"impossible"<<endl;
        else cout << t << endl;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    记录最小生成树路径

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N = 510;
    int g[N][N];//存储图
    int dt[N];//存储各个节点到生成树的距离
    int st[N];//节点是否被加入到生成树中
    int pre[N];//节点的前去节点
    int n, m;//n 个节点,m 条边
    
    void prim()
    {
        memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数(10亿左右)
        int res= 0;
        dt[1] = 0;//从 1 号节点开始生成 
        for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
        {
            int t = -1;
            for(int j = 1; j <= n; j++)//每个节点一次判断
            {
                if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中,且到树的距离最短,则选择该点
                    t = j;
            }
    
            st[t] = 1;// 选择该点
            res += dt[t];
            for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
            {
                if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离,则更新。
                {
                    dt[i] = g[t][i];//更新距离
                    pre[i] = t;//从 t 到 i 的距离更短,i 的前驱变为 t.
                }
            }
        }
    }
    
    void getPath()//输出各个边
    {
        for(int i = n; i > 1; i--)//n 个节点,所以有 n-1 条边。
    
        {
            cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号,pre[i] 是 i 节点的前驱节点。他们构成一条边。
        }
    }
    
    int main()
    {
        memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
        cin >> n >> m;//输入节点数和边数
        while(m --)
        {
            int a, b, w;
            cin >> a >> b >> w;//输出边的两个顶点和权重
            g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
        }
    
        prim();//求最小生成树
        getPath();//输出路径
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    三、Pirm算法堆优化

    时间复杂度O(m∗logn)

    很少用,时间复杂度高的时候可以考虑kruskal算法,实现简单
    堆优化Prim相比于Kruskal难写一些,也没有效率上的优势,所以基本上没人写。

    #include<iostream>
    #include<cstring>
    #include<queue>
    #include<vector>
    #include<algorithm>
    using namespace std;
    typedef pair<int,int> PII;
    const int N=510;
    int g[N][N],dist[N];
    bool st[N];
    
    int n,m;
    int prim()
    {
        int res=0,tt=0;
        memset(dist,0x3f,sizeof dist);
        dist[1]=0;
        priority_queue<PII,vector<PII>,greater<PII>> heap;
        heap.push({0,1});
        while(heap.size())
        {
            PII t = heap.top();
            heap.pop();
            int t1 = t.first,t2 = t.second;
            for(int i=1;i<=n;i++)
            {
                if(st[t2]) continue;
                st[t2]=true;
                tt++;
                if(t2>1) res+=dist[t2];
    
                for(int j=1;j<=n;j++)
                {
                    if(dist[j]>g[t2][j])
                    {
                        if(!st[j])
                        {
                            dist[j] = g[t2][j];
                            heap.push({dist[j],j});
                        }
                    }
                }
            }
    
        }
        if(tt!=n) return -1;
        return res;
    }
    int main()
    {
        memset(g,0x3f,sizeof g);
        cin>>n>>m;
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            cin>>u>>v>>w;
            g[u][v]=g[v][u]= min(g[u][v],w);
        }
        int t = prim();
        if(t==-1) cout<<"impossible";
        else cout<<t;
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    最后

    莫言真理无穷尽,寸进自有寸进欢

    在这里插入图片描述

  • 相关阅读:
    【总结】坐标变换和过渡矩阵(易忘记)
    小菜鸡近期的一些胡思乱想
    基于51单片机霍尔汽车自行车码表测速测里程显示proteus仿真原理图PCB
    Redis怎么测?这篇文章写的太全了
    Hotspot启动原理(二)
    结合源码聊一聊为何线上RocketMQ偶尔出现system busy
    Fair原理篇Fair逻辑动态化架构设计与实现
    微信小程序获取微信用户步数
    计算机毕业设计Java公司薪酬管理系统(源码+系统+mysql数据库+Lw文档)
    docker容器化技术
  • 原文地址:https://blog.csdn.net/m0_63233163/article/details/125589152