图论之Prim

一、前言

此篇主要针对图论中的求最小生成树的一种算法Prim算法，这个算法其实整体的结构和dijkstra算法是相似的，所以整体的思路也和dijkstra算法有异曲同工之妙。首先，讲一下自己对最小生成树这个概念的理解。

生成树: 包含图中所有结点，且整个结点形成的一张图中不含有任何环，一旦再多连接两个结点形成一条边，一定会生成一个环的一个结构图。

最小生成树: 在一个图中找到的所有生成树中，所有边加起来的权值最小的那一棵生成树是一颗最小生成树。

本章题大多来源于ACwing,欢迎大家来这个平台一起学习算法！！

二、题目汇总

①Prim算法模板(ACwing.858)

时间复杂度: $O(n^2)$

适用场景: 点数少，边数多的最小生成树求解。

思路: 和dijkstra算法结构差不多，但是此时定义的dist数组指的是，此时计算的某个点，到我们此时求到的生成树整个集合中的一个最小值距离。也就是说我们在推导dist数组的时候，同样每次选取一个距离集合最短的那一条边进行一个延申，不断延申的时候求出某个点到整个已经求出的部分最小生成树的一个距离最小值。

更新过程:

紫色 当前利用的更新点

蓝色当前更新完后，某个点距离整个集合的最小距离

红色两个结点边的长度

上图最终的最小生成树就为3！

完整AC代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 505, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
bool st[N];
int n, m;

int prim() {
    int res = 0;
    dist[1] = 0;
    
    for(int i = 1; i <= n; i ++ ) {
        int t = -1;
        //寻找离集合最近的那一条边
        
        for(int j = 1; j <= n; j ++ ) {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
     	//如果dist[t] = INF代表没有边连向集合，直接返回    
        if(dist[t] == INF) return INF;
        st[t] = true;
        for(int j = 1; j <= n; j ++ ) {
            dist[j] = min(dist[j], g[t][j]);
        }
        
        res += dist[t];
    }
    
    return res;
}

int main() {
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof st);
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        //先去掉自环
        //注意这种都是无向图，所以两个边都需要赋值
        if(a != b) g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    int ans = prim();
    
    if(ans == INF) cout << "impossible" << endl;
    else cout << ans << endl;
    
    return 0;
}