求最小生成树算法——Prim
算法：
时间复杂度 : 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 }