文章目录
前言
一、Prim算法
二、AcWing 858. Prim算法求最小生成树
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：Prim，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、Prim算法
Prim算法是用来计算最小生成树的算法，把最后的树当成一个集合，开始时，所有的点到树的距离都是ox3f3f3f3f，然后一开始任选一个点加入树中，然后用该点更新其他点的距离，然后之后的每次都是选择距离最近的点加入树中并更新所有点的距离
举一个例子理解Prim算法的实际用途，比如现在有5个村庄，我们需要在一个村庄建立一个发电站供五个村庄用电，因为修高压电线需要很多的软妹币，为了省钱，我们需要既能联通所有村庄，并且使得路途最短，这个时候，我们就可以利用Prim算法去找到最短的路段之和.
下图来自：ACWing算法基础课
二、AcWing 858. Prim算法求最小生成树
本博客给出本题截图：
本题分析
我们用邻接矩阵去存储整个图，dist数组表示的是该点到树的距离比如dist[i] = k;的含义就是j点到树的距离为k，如果k == 0x3f3f3f3f就意味着该点和树不连通，g数组存的是两个点之间的距离，比如g[i][j]的值就存储的是i点到j点的距离，st数组存储的是该点是否被加入到了树中，st[i] == true;代表着i点已经加入到了树中，st[i] == false代表i点没有加入到树中
因为我们要最短路径，所以当两个点之间存在多条边的时候，我们只需要保存最短的那一条边，且为无向图，所以我们有下述操作：
g[u][v] = g[v][u] = min(g[u][v], w);
我们需要把dist数组全部赋值为INF，意味着一开始所有的点到树的距离都是INF
接下来介绍Prim函数核心
for (int i = 0; i < n; i ++ ) //依次遍历n个点 { int t = -1; //t = -1代表目前没有选择点 for (int j = 1; j <= n; j ++ ) //这个循环是为了让我们找到不在图中的距离图最小的点，所以如果存在dist[j] < dist[t]的话就更新 //t = -1证明这是第一个点，我们需要把它加入到树中 if (!st[j] && (t == -1 || dist[j] < dist[t])) //j这个点必须是没有选过的 t = j; //这个t就是不在树中的距离树最近的点 if (i && dist[t] == INF) return INF; //如果不是第一个点（因为第一个点距离树的距离是INF） //并且这个点到树的距离是INF的话，证明这个点不和树有交集，就返回INF if (i) res += dist[t]; //只要不是第一次循环，就把dist[t]加入到res中，因为第一次循环是随便拿一个点放入到树中的 //并且这个点到树的距离是INF st[t] = true; //这个点已经加入到树中了，我们就标记一下这个点 for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]); //用这个点更新其他点到树的距离 }
AC代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 510, INF = 0x3f3f3f3f; int n, m; int g[N][N]; bool st[N]; int dist[N]; int prim() { memset(dist, 0x3f, sizeof dist); int res = 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; if (i && dist[t] == INF) return INF; if (i) res += dist[t]; st[t] = true; for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]); } return res; } int main() { scanf("%d%d", &n, &m); memset(g, 0x3f, sizeof g); for (int i = 0; i < m; i ++ ) { int u, v, w; scanf("%d%d%d", &u, &v, &w); g[u][v] = g[v][u] = min(g[u][v], w); } int t = prim(); if (t == INF) printf("impossible"); else printf("%d", t); return 0; }
三、时间复杂度
关于Prim算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
