最小生成树
最小生成树（MST）知识点
最小生成树（MST） 是图论中的一个经典问题，目的是在一个带权无向图中，找到一棵生成树，使得树的边的权值之和最小。
最小生成树的基本概念：
生成树：一个图的生成树是一个包含图中所有顶点的树，它是一个无环的连通子图。
最小生成树：一个图的生成树中，边的权值之和最小的生成树称为最小生成树。
prim算法
第一步，选距离生成树最近节点
第二步，最近节点加入生成树
第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
53. 寻宝
#include<bits/stdc++.h>
using namespace std;
int main() {
int v, e;
cin >> v >> e;
// 创建一个邻接矩阵，初始化为INT_MAX（表示没有边）
vector<vector<int>> grid(v + 1, vector<int>(v + 1, INT_MAX));
// mindist数组：存储每个节点到生成树的最小距离，初始化为INT_MAX
vector<int> mindist(v + 1, INT_MAX);
// visited数组：记录每个节点是否已经加入生成树
vector<bool> visited(v + 1, false);
// 输入所有边的信息（节点和权值）
for (int i = 0; i < e; i++) {
int x, y, z;
cin >> x >> y >> z;
grid[x][y] = z; // 无向图：邻接矩阵的两个方向都赋值
grid[y][x] = z;
}
// 从节点1开始，距离初始化为0
int cur = 1;
// 逐步扩展生成树，进行v-1轮
for (int i = 1; i < v; i++) {
// 找到未访问节点中，mindist最小的节点
int minval = INT_MAX;
// 第一步：选距离生成树最近的节点
for (int j = 1; j <= v; j++) {
// 如果节点j还没有加入生成树，并且它到生成树的距离小于当前的最小值
if (!visited[j] && mindist[j] < minval) {
cur = j; // 更新当前节点为最小距离的节点
minval = mindist[j]; // 更新最小值
}
}
// 第二步：最近节点加入生成树
visited[cur] = true; // 将当前节点标记为已访问
// 第三步：更新非生成树节点到生成树的最小距离（更新mindist数组）
for (int j = 1; j <= v; j++) {
// 如果节点j没有被访问，并且当前边的权值小于它到生成树的最短距离
if (!visited[j] && grid[cur][j] < mindist[j]) {
mindist[j] = grid[cur][j]; // 更新mindist[j]
}
}
}
// 计算最小生成树的权值总和
int ans = 0;
for (int i = 2; i <= v; i++) {
ans += mindist[i]; // 加入每个节点到生成树的最小距离
}
cout << ans; // 输出最小生成树的权值和
}
kruskal算法
边排序：首先将所有的边按权值升序排列。
并查集：通过并查集来判断两个节点是否已经连接，如果没有连接，则将这条边加入到最小生成树中。
#include<bits/stdc++.h>
using namespace std;
struct edge {
int l, r, v; // 边的两个端点 l, r 和边的权值 v
};
// 并查集父节点数组，用来存储每个节点的父节点
vector<int> father(10001, 0);
// 初始化并查集，父节点初始化为自己
void init() {
for(int i = 0; i <= 10001; i++) {
father[i] = i; // 每个节点的父节点初始化为它自己
}
}
// 查找操作，查找节点 u 的根节点
int find(int u) {
if(u == father[u]) return u; // 如果父节点是自己，返回该节点
else return father[u] = find(father[u]); // 路径压缩，递归查找父节点
}
// 合并操作，合并两个节点所在的集合
void join(int x, int y) {
int x1 = find(x); // 查找 x 的根节点
int y1 = find(y); // 查找 y 的根节点
if(x1 == y1) return; // 如果两个节点已经在同一个集合中，直接返回
father[y] = x; // 将 y 的父节点指向 x，合并集合
}
// 边的比较函数，用于排序
bool cmp(edge a, edge b) {
return a.v < b.v; // 按边的权值升序排序
}
int main() {
int v, e; // v 为节点数，e 为边数
cin >> v >> e; // 输入节点数和边数
vector<edge> edges; // 存储所有的边
while(e--) {
int x, y, z;
cin >> x >> y >> z; // 输入边的两个端点和权值
edges.push_back({x, y, z}); // 将边加入到边的列表中
}
sort(edges.begin(), edges.end(), cmp); // 按照边的权值升序排序
init(); // 初始化并查集
int ans = 0; // 存储最小生成树的权值和
for(auto i : edges) {
int x = find(i.l); // 查找边的起点 i.l 的根节点
int y = find(i.r); // 查找边的终点 i.r 的根节点
if(x != y) { // 如果两个端点不在同一集合中，说明这条边不形成环
ans += i.v; // 将这条边的权值加到最小生成树的权值和中
join(x, y); // 合并这两个节点所在的集合
}
}
cout << ans; // 输出最小生成树的权值和
}