(算法基础)朴素版Prim算法

适用情景

1. 在最小生成树问题当中，涉及到权重和最小值。并且这个图是稠密图(n^2 ~ m)的情形下

---

时间复杂度

1. O(N^2)

---

算法解释

1. 先得知道一下什么是无向图的生成树，树总该知道的吧，生成树就是包含这个无向图中的n个点，并且有n-1条边，其实说白了就是一棵树，当于从原先的无向图的结构当中“拿取”一部分组成了一棵树，这棵树就叫做无向图的生成树。然后这棵树既然有n-1条边，图当中边是有权重的，这些边的权重之和最小的那棵树就称为无向图的最小生成树

2. 首先对于这个图来说，首先是无向图（说白了也是一种特殊的有向图），然后prim算法适用于稠密图，那既然是稠密图的话，想当然就是用邻接矩阵去存储边。然后对于这个图而言，正权边与负权边无关紧要；最后对于重边和自环，重边的话肯定是取小的，然后环的话是不可能出现在最小生成树当中，需要回避的

int dist[N][N];

3. 然后对于这个邻接矩阵初始化操作变成无穷大（等会儿要进行取小操作），然后就是把边输入到这个邻接矩阵当中，无向图的话，实际上就是一种特殊的有向图罢了

memset(g,0x3f3f3f3f,sizeof(g));
int a,b,c;
while(m--)
{scanf("%d %d %d",&a,&b,&c);g[a][b]=g[b][a]=MIN(g[a][b],c);
}

4. 然后这是一个很关键的一步，创建一个dist数组，这个dist数组表示每个点到联通块集合的最短距离（这个联通块集合不断壮大壮大，最后就是我的一个最小生成树），在一开始的话，也全部都默认初始化为无穷大

int dist[N];
memset(dist,0x3f,sizeof(dist));

5. 除此之外还需要一个数组st起标记作用，就是去说明该点是否已经在联通块集合（这个联通块集合，不断壮大壮大，最后就是我需要求的最小生成树）当中。

int st[N];

6. 然后接下来正式就是prim算法，这个prim算法的话与迪杰斯特拉算法非常相似。首先是先去循环n次，然后第一次循环的话，由于是刚刚开始，就选择一号点作为联通快集合的开拓点（真正在联通块集合当中，每一个点没有先来后到之分），然后对于外循环的第一次，他就是仅仅去更新一下别人的dist，并且去标记一下自己已经进入联通块集合当中而已。然后对于接下来的每一次外循环，与Dijkstra算法相似，首先先去找集合外的距离联通块集合距离最近的点，把这个点找到之后。先要去判断一下这个点距离集合的最短距离，如果发现是初始化的那个无穷大值，好那么这时候就说明生成不了最小生成树；如果不是，用这个点所能及更新它所能连接到的其他点的到联通块集合的最短距离并且呢把他自己呢要加入到联通块集合当中（也就是说需要标记一下）。by the way，然后在这个过程当中，我就可以去求我这个最后生成的最小生成树它的各边权重和。

int res=0; //最后生成的最小生成树它的各边权重和
for (int i=0;i<n;i++)
{int t=0;for (int j=1;j<=n;j++){if (st[j]==0 && (t==0 || dist[j]<dist[t])){t=j;}}if (i!=0){if (dist[t]==0x3f3f3f3f){printf("impossible\n");return 0;}else{res+=dist[t];}}st[t]=1;for (int j=1;j<=n;j++){dist[j]=MIN(dist[j],g[t][j]);    }}
printf("%d\n",res);

---

例题

来源：AcWing

858. Prim算法求最小生成树 - AcWing题库

#include <stdio.h>
#include <string.h>
#define MIN(a,b) ((a)<(b)?(a):(b))
#define N 510
int g[N][N];
int dist[N];
int st[N];
int main()
{memset(dist,0x3f,sizeof(dist));int n,m;scanf("%d %d",&n,&m);memset(g,0x3f3f3f3f,sizeof(g));int a,b,c;while(m--){scanf("%d %d %d",&a,&b,&c);g[a][b]=g[b][a]=MIN(g[a][b],c);}int res=0;for (int i=0;i<n;i++){int t=0;for (int j=1;j<=n;j++){if (st[j]==0 && (t==0 || dist[j]<dist[t])){t=j;}}if (i!=0){if (dist[t]==0x3f3f3f3f){printf("impossible\n");return 0;}else{res+=dist[t];}}st[t]=1;for (int j=1;j<=n;j++){dist[j]=MIN(dist[j],g[t][j]);    }}printf("%d\n",res);return 0;
}