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

文章目录

• ​​一、前言​​
• ​​二、Pirm算法求最小生成树​​
• ​​三、Pirm算法堆优化​​
• ​​最后​​

一、前言

最小生成树定义：

一个有 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;

}      

​

​Prim算法与Dijkstra算法的区别​

​

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

Prim是更新不在集合中的点 离集合S的距离
dist[j] = min(dist[j], g[t][j])      

例题：

给定一个 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;
}      

记录最小生成树路径

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

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

最后

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