文章目录
前言
一、Prim算法
二、AcWing 858. Prim算法求最小生成树
本题分析
AC代码
三、时间复杂度


前言
复习acwing算法基础课的内容，本篇为讲解基础算法：Prim，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。

一、Prim算法
Prim算法是用来计算最小生成树的算法，把最后的树当成一个集合，开始时，所有的点到树的距离都是ox3f3f3f3f，然后一开始任选一个点加入树中，然后用该点更新其他点的距离，然后之后的每次都是选择距离最近的点加入树中并更新所有点的距离
举一个例子理解Prim算法的实际用途，比如现在有5个村庄，我们需要在一个村庄建立一个发电站供五个村庄用电，因为修高压电线需要很多的软妹币，为了省钱，我们需要既能联通所有村庄，并且使得路途最短，这个时候，我们就可以利用Prim算法去找到最短的路段之和.
下图来自：ACWing算法基础课


二、AcWing 858. Prim算法求最小生成树
本题链接：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算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。

最小生成树prim算法：
graph[][] 待生成树的图，
used[] 使用过的节点，
distance[] 生成树到各节点的最短距离，
start 任意起始点。
1：将 start 放入 used ，从起始点 start 遍历周边节点，将可到达的节点的距离放入 distance 。
public static void init(int[][] graph, boolean[] used, int[] distance){
		int from = GraphUtils.FROM;
		for (int i = 0; i < graph.length; i++){
			used[i] = false;
			distance[i] = graph[from][i];
		}
		used[from] = true;
		distance[from] = 0;
	}


2：在 distance 中选择没有在 used 中并且距离最小的联通点 min ，添加到 used 中。
3：遍历 min 联通的节点around，如果 graph[min][around] < distance[around] 设置 distance[around] = graph[min][around]。
注：此处可添加 sum+= min;用于计算最小生成树的路长总和。
4：循环 2，3 直到全部在 used 中。
public static int prim(int[][] graph){
		boolean[] used = new boolean[graph.length];
		int[] distance = new int[graph.length];
		init(graph, used, distance);
		int sum = 0;
		for (int i = 0; i < graph.length; i++){
			int min = GraphUtils.MAX;
			int minIndex = GraphUtils.FROM;
			for (int j = 0; j < graph.length; j++){
				if ((!used[j]) && distance[j] < min){
					min = distance[j];
					minIndex = j;
				}
			}
			if (min != GraphUtils.MAX) {
				used[minIndex] = true;
				sum += min;
				LOG.d(minIndex);
				for (int j = 0; j < graph.length; j++){
					if ((!used[j]) && distance[j] > graph[minIndex][j]){
						distance[j] = graph[minIndex][j];
					}
				}
			}
		}
		return sum;
	}

Concrete Content
最小生成树的Prim算法也是贪心算法的一大经典应用。Prim算法的特点是时刻维护一棵树，算法不断加边，加的过程始终是一棵树。
Prim算法过程：
一条边一条边地加， 维护一棵树。

初始 $E ＝｛｝$空集合， $V = ｛$任意节点$｝$

循环 $（n – 1）$ 次，每次选择一条边$（v1,v2）$， 满足：$v1$ 属于 $V , v2$ 不属于 $V$。且 $（v1,v2）$权值最小。

$E = E + （v1,v2）$

$V = V + v2$

最终 $E$ 中的边是一棵最小生成树，  $V$ 包含了全部节点。

最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法;
输入
第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。$（2 <= N <= 1000, 1 <= M <= 50000)$

第$2 - M + 1$行：每行3个数$S$ $E$ $W$，分别表示M条边的2个顶点及权值。$(1 <= S, E <= N，1 <= W <= 10000)$
输出
输出最小生成树的所有边的权值之和。
输入示例
9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8

输出示例

37

请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。
代码如下：

?   (☄⊙ω⊙)☄
#include<iostream>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxx=1100;
int e[maxx][maxx],dis[maxx];
bool book[maxx];
int n,m;
void init()
{
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(i==j)e[i][j]=0;
            else
                e[i][j]=inf;
}
int prim(int e[][maxx],int n)
{
    int ans=0;
    memset(book,false,sizeof(book));
    book[0]=true;
    for(int i=1; i<n; i++)
        dis[i]=e[0][i];
    for(int i=1; i<n; i++)
    {
        int minn=inf,u=-1;
        for(int j=0; j<n; j++)
        {
            if(!book[j]&&dis[j]<minn)
            {
                minn=dis[j];
                u=j;
            }
        }
        if(ans==inf)
            return -1;
        ans+=minn;
        book[u]=true;
        for(int v=0; v<n; v++)
            if(!book[v])
                dis[v]=min(dis[v],e[u][v]);
    }
    return ans;
}
int main()
{
    while(cin>>m>>n)
    {
        init();
        for(int i=0; i<n; i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            if(e[a-1][b-1]>c)
                e[a-1][b-1]=e[b-1][a-1]=c;
        }
        cout<<prim(e,m)<<endl;
    }
    return 0;
}


以下图为例介绍Prim算法的执行过程。



Prim算法的过程从A开始 V = {A}, E = {}



选中边AF , V = {A, F}, E = {(A,F)}



选中边FB, V = {A, F, B}, E = {(A,F), (F,B)}



选中边BD, V = {A, B, F, D},   E = {(A,F), (F,B), (B,D)}



选中边DE, V = {A, B, F, D, E},   E = {(A,F), (F,B), (B,D), (D,E)}



选中边BC, V = {A, B, F, D, E, c},   E = {(A,F), (F,B), (B,D), (D,E), (B,C)}, 算法结束。

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
A.Prim算法：
procedure prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do
begin
lowcost:=cost[v0,i];
closest:=v0;
end;
for i:=1 to n-1 do
begin
{寻找离生成树最近的未加入顶点k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]< min) and (lowcost[j]< >0) then
begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {将顶点k加入生成树}
{生成树中增加一条新的边k到closest[k]}
{修正各点的lowcost和closest值}
for j:=1 to n do
if cost[k,j]< lwocost[j] then
begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}