常用的最小生成树的算法主要有两种，一种是Prim算法，一种是Kruskal算法。题目链接：KamaCoder 53. 寻宝（第七期模拟笔试）


这里假设有V个节点，因为我们的节点的标号是1~V，这样我们直接使用标号作为索引，不用额外的+1或者-1操作。

1. Prim算法

Prim算法基本的思路是按点来遍历，适合点比较少边比较多的稠密图，步骤是：

1. 初始化minDist(最小生成树到每个节点的最小值)，grid(图里的边权)，visited(是否加入最小生成树)，我们把minDist设置为长度V+1，把grid设置为长和宽分别为V+1和V+1，visited长度也是V+1。

• minDist初始化，初始化均为一个很大的值，这里的节点的数量小于等于10000，设置为10001：

vector<int> minDist(V+1, 10001);

• grid初始化，一开始我们设置为一个很大的值，表示任意的两个点u和v是不可达的，因为我们后面要计算节点到最小生成树的最小值，所以我们初始化为最大值，后面求最小值才是有效的：

vector<vector<int>> grid(V+1, vector<int>(V+1, 10001));

• visited初始化，一开始所有的节点都是没有访问过的，所以我们初始化为0，表示没有访问过，后面访问过加入了最小生成树以后我们要把节点visited对应的节点的值设置为1

vector<int> visited(V+1, 0);

2. 求离最小生成树最近的点cur，定义初始距离minVal = INT_MAX，然后遍历所有的节点$j\in [1,V]$，如果$minVal<minDist[j]$，minVal赋值为minDist[j]，cur赋值为j，所有节点遍历结束以后，我们找到了离最小生成树最近的那个点，第一个找到的cur其实是1：

int minVal = INT_MAX;    
int cur = -1;
for (int j = 1; j <= V; ++j)
{if (!visited[j] && minDist[j] < minVal) // j不在最小生成树中并且j节点到最小生成树的距离比minVal更小{minVal = minDist[j];cur = j;}
}

3. 把节点cur加入到最小生成树里，其实就是将visited[cur]标记为1

visited[cur] = 1;

4. 更新cur加入最小生成树以后得minDist：遍历所有节点$j\in [1,V]$，如果grid[cur][j] < minDist[j]，那么更新minDist[j]为grid[cur][j]：

for (int j = 1; j <= V; ++j)
{if (!visited[j] && grid[cur][j] < minDist[j])// j不在最小生成树中并且cur到j的距离比j到最小生成树上一次距离小minDist[j] = grid[cur][j];
}

因为一个最小生成树有V个节点我们需要添加V-1条边，那么我们就需要遍历V-1次（minDist更新V-1次，回想我们的更新minDist使用了grid[cur][j]，表示从cur到j，因为第一个顶点是没有父亲节点的，所以第一个顶点对应的minDist[1]是不会更新的，j不会为1，更新的minDist的索引是从2到V的），那我们就可以写出完整的代码了：

#include <iostream>
#include <climits>
#include <vector>
using namespace std;int main()
{int V, E;cin >> V >> E;vector<int> visited(V+1, 0);vector<int> minDist(V+1, 10001);vector<vector<int>> grid(V+1, vector<int>(V+1, 10001));for (int i = 0; i < E; ++i){int x, y, v;cin >> x >> y >> v;grid[x][y] = v;grid[y][x] = v;}for (int i = 1; i < V; ++i){int minVal = INT_MAX;    int cur = -1;for (int j = 1; j <= V; ++j){if (!visited[j] && minDist[j] < minVal){minVal = minDist[j];cur = j;}}visited[cur] = 1;for (int j = 1; j <= V; ++j){if (!visited[j] && grid[cur][j] < minDist[j])minDist[j] = grid[cur][j];}}int ans = 0;for (int i = 2; i <= V; ++i)ans += minDist[i];cout << ans << endl;
}

Kruskal算法

Prim算法基本的思路是按边来遍历，适合边比较少点比较多的稀疏图，步骤是：

1. 对所有的边权排序，小的边权排前面，大的排后面
2. 遍历所有边权，如果边权的起点和终点不在同一集合（属于最小生成树和不属于最小生成树），那么连接这两个起点和终点到最小生成树里，记录最小生成树的边的答案，遍历完所有边记得到答案。

判断是不是在同一集合和链接两个点到同一个集合，我们使用并查集来做。

#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;class UnionSet
{vector<int> father;int pathLength = 0;
public:UnionSet(int n): father(n, 0){for (int i = 0; i < n; ++i)father[i] = i;}int find(int u){return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩}void Union(int u, int v){int uRoot = find(u);int vRoot = find(v);if (uRoot == vRoot)return;father[vRoot] = uRoot;}bool isSame(int u, int v){int uRoot = find(u);int vRoot = find(v);return uRoot == vRoot;}void addPathLength(int val){pathLength += val;}int GetPathLength(){return pathLength;}};
struct Edge
{int start, end, val;
};
int main()
{int V, E;cin >> V >> E;vector<Edge> edges;for (int i = 0; i < E; ++i){int x, y, v;cin >> x >> y >> v;edges.push_back({x, y, v});}sort(edges.begin(), edges.end(), [](Edge& e1, Edge& e2){return e1.val < e2.val;});UnionSet unionSet(V+1);for (int i = 0; i < edges.size(); ++i){int x = edges[i].start;int y = edges[i].end;int val = edges[i].val;if (!unionSet.isSame(x, y)){unionSet.Union(x, y);unionSet.addPathLength(val);}}cout << unionSet.GetPathLength() << endl;
}