最小生成树Prim算法

求最小生成树算法——Prim

例题：

https://www.luogu.org/problem/P3366

算法：

时间复杂度 : O(n²)

算法主体思想:

prim算法主要是用到贪心的思想，假设我们有两个集合A和B，A集合表示最小生成树集合(及A集合中的点都在最小生成树中)，B集合表示非最小生成树集合(及B集合中的点都不在最小生成树中)。一开始，我们可以随便将一个点放入集合A，然后我们选择到最小生成树中距离最小的点放入A集合(前提是最小 && 当前点在B集合)，然后用当前点更新其他在B集合中的点到A集合的距离。以此类推，循环n次之后(一共有n个点，所以n次之后，B集合为空，所有点都在A集合)，就可得到最小生成树。

算法主要变量声明:

我们可以记录每个点到最小生成树集合中的最小距离，记为dis[i]————第i个点到最小生成树集合中的最小距离(注意:是到最小生成树集合的最短距离，不是到起点)。然后我们还需知道一个点是否在最小生成树集合中，于是我们用vis[i]表示i是否在最小生成树集合中(在A集合，还是在B集合)。当然我们可以用f[i][j]来记录第i个点到第j个点的距离。

算法主要步骤:

1. 初始化所有点都在B集合中，所有点到A集合中的距离都为0

2. 随机选择一个点(选1即可)，并将当前点到最小生成树的距离为0

3. 重复n次以下步骤(及把所有点都放到A集合)

定义变量minn表示每次搜到的到最小生成树集合的最小距离(初始化为INF), k表示搜到的最小值的编号
搜索B集合中到A集合的最小值
标记搜到的点在A集合
ans来累加当前点到最小生成树集合的距离
通过当前搜到的点k，来更新其他点到最小生成树集合的最短距离

4. 得到最小生成树，边权之和在ans里

示意图：

code：

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f//定义最大值(0x3f3f3f3f是一个很大的数) 
 3 using namespace std;
 4 int n, m, dis[1001], vis[1001], f[1001][1001], ans;//dis[i]表示第i个点到最小生成树集合的最小值(及到最小生成树中任意点的最小值), vis[i]表示第i个点是否在最小生成树中, f[i][j]表示从第i个点到达第j个点的最小值(无法到达就赋INF), ans记录最小生成树边权 
 5 inline void prim(int s)//Prim模板 
 6 {
 7     memset(vis, 0, sizeof(vis));//初始化为未在最小生成树中 
 8     memset(dis, INF, sizeof(dis));//初始化为最大值 
 9     dis[s] = 0;//初始点s到最小生成树生成树中距离为0 
10     for(register int i = 1; i <= n; ++i)//n个点都要连通就要把n个点都放进最小生成树里 
11     {
12         int minn = INF;//用来记录每次搜到的离最小生成树集合的最小值 
13         int k = 0;//用来记录搜到最小值的编号 
14         for(register int j = 1; j <= n; ++j)//寻找最小值 
15         {
16             if(!vis[j] && dis[j] < minn)//不能访问过 && 离最小生成树的距离最短 
17             {
18                 minn = dis[j];//替换 
19                 k = j;
20             }
21         }
22         if(!k)//没有点在最小生成树中了(这个也可以判断图是否连通，如果k没有值，就代表图没有连通，因为最小生成树中点的数量一定是n(生成树的定义就是用n - 1条边，使得n个点能互相到达)) 
23         {
24             break;
25         }
26         vis[k] = 1;//标记 
27         ans += dis[k];//累加最小值 
28         for(register int j = 1; j <= n; ++j)
29         {
30             if(!vis[j] && dis[j] > f[k][j])//更新长度(这里是到最小生成树集合的最短长度，不是到s的最短长度) 
31             {
32                 dis[j] = f[k][j];//更新 
33             }
34         }
35     }
36     return;
37 }
38 signed main()
39 {
40     memset(f, INF, sizeof(f));//赋最大值 
41     scanf("%d %d", &n, &m);
42     for(register int i = 1, x, y, z; i <= m; ++i)
43     {
44         scanf("%d %d %d", &x, &y, &z);
45         f[x][y] = f[y][x] = min(f[x][y], z)/*小心毒瘤数据*/;//连双向边 
46     }
47     prim(1);//从1开始就好了 
48     printf("%d", ans);
49     return 0;
50 }