算法基础22-最小生成树

prim

链接: acwing上一个关于prim很好的题解

prim 算法干的事情是：给定一个无向图，在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中，叫做求最小生成树。

prim 算法采用的是一种贪心的策略。

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

//AcWing 858. Prim算法求最小生成树
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510;

int g[N][N];//稠密图，用邻接矩阵存储
int st[N];//记录生成树中已经添加了哪些节点
int pre[N];//记录每个节点是由哪个节点连接如生成树的
int dist[N];//！！记录每个节点到生成树的距离

int n, m;

void prim()
{
    int res = 0;//最小生成树权值总和
    memset(dist, 0x3f, sizeof dist);
    memset(pre, -1, sizeof pre);
    dist[1] = 0; 
    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;
            }
        }
        
        //2022.6.1 发现测试用例加强后，需要判断孤立点了
        //如果孤立点，直返输出不能，然后退出
        if(dist[t] == 0x3f3f3f3f) 
        {
            cout << "impossible";
            return;
        }
        
        st[t] = 1;//将找到的节点加入生成树
        res += dist[t];//给生成树的权值赋值
        for (int i = 1; i <= n; i ++ )//遍历所有节点，用刚刚加入的新节点去 更新不在生成树中的节点（或者说剩余节点）距离生成树的距离
        {
            if (!st[i] && dist[i] > g[t][i])//如果不是生成树中的节点 
            {                               //并且 这个节点距离生成树的距离 < 新加入生成树节点t在图中和它之间的距离
                dist[i] = g[t][i];          //就更新
                pre[i] = t;                 //更新之后i距离生成树最短距离的前驱节点设置为t
            }
        }
    }
    cout << res;//返回最小生成树的权重
}

int main()
{
    memset(g, 0x3f, sizeof(g));//邻接矩阵初始化
    cin >> n >> m;
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[b][a] = g[a][b] = min(g[a][b], c);//a,b之间可能有多条边，存最短的就行了
    }
    
    prim();
     //getPath();//输出各个节点添加进最小生成树顺序，也可以说是输出路径
    return 0;
}

优化：

上面代码的时间复杂度为 O(n^2)。

与Dijkstra类似，Prim算法也可以用堆优化，优先队列代替for循环查找距离生成树中最短距离的节点。
优化的Prim算法时间复杂度O(mlogn)。适用于稀疏图，但是稀疏图的时候求最小生成树，Kruskal 算法更加实用。（因为kruskal算法是遍历边，每次找图里面不在生成树中最短的边）

kruskal

算法思路：

• 将所有边按照权值的大小进行升序排序，然后从小到大一一判断。

• 如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。

• 直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。

• 筛选出来的边和所有的顶点构成此连通网的最小生成树。

• 判断是否会产生回路的方法为：使用并查集。

• 在初始状态下给各个个顶点在不同的集合中。、

• 遍历过程的每条边，判断这两个顶点的是否在一个集合中。

• 如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。

可以发现kruskal遍历的是一条一条边，因此只要将图的所有边存下来就行了
也正是因此，kruskal比较适合找出稀疏图的最小生成树

//AcWing 859. Kruskal算法求最小生成树
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int p[N];

struct E{
    int a;
    int b;
    int w;
    bool operator < (const E& rhs){//sort是根据数据结构自己的<运算符进行排序的，
                                    //因此我们要重定义结构体的运算符
        return this->w < rhs.w;
    }

}edg[N * 2];//边数为m，m=2*n，其实算是稀疏图了，如果m=n*n那算稠密图了
int res = 0;//最小生成树的权值

int n, m;
int cnt = 0;
int find(int a){//并查集模版，查找该集合内的父节点
    if(p[a] != a) p[a] = find(p[a]);
    return p[a];
}
void kruskal(){
    for(int i = 0; i < m; i++)
    {
        int pa = find(edg[i].a);//表示a所在的集合的父节点
        int pb = find(edg[i].b);//表示b所在的集合的父节点
        if(pa != pb){//判断a,b是否已经在一个集合内，如果在一个集合内还合并的话就会造成回路，就不符合树的定义了
            res += edg[i].w;//收最小生成树的集权值
            p[pa] = pb;//a所在集合的父节点 = b所在集合的父节点
            cnt ++; //记录加入生成树的边数，
        }
    }
}

int main()
{

    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;//初始化并查集
                                        //节点下标从1开始，所以 i从1开始
    for(int i = 0; i < m; i++){//初始化边集合数组
        int a, b , c;
        cin >> a >> b >>c;
        edg[i] = {a, b, c};
    }
    sort(edg , edg + m );//每次取最短的边，因此提前将边数组排序，到时候直接从头开始就遍历就是最小的
    kruskal();
    
    if(cnt < n - 1){//如果加入的边数小于n-1说明最小生成树不存在
        cout<< "impossible";
    }
    else cout << res;
    return 0;
}