如何构建一个数据结构的最小生成树？

最小生成树 前置知识 并查集 图论 概念 条件 最小生成树的满足条件为： 在无向图中选取总权值最少的边让所有点连通。 要求结果是一棵树，边数比点数少 \(1\)。 当然，最小生成树的结果可能不唯一。 特性 图中任意一条非树边都会和树边构成一个环。 非树边一定是环中最大的边。否则可以替换掉最大的边，得到一个更小生成树。 其他 最小生成树有两种算法：Kruskal 和 Prim。 Kruskal 是在并查集的基础上展开。 Prim 是在最短路的基础上展开。 Kruskal 介绍 我们可以从选边的角度来构造生成树，通过点的连通性来对边的选取进行判断。 我们按权值由小到大选择不成环的边加入树中。（由树的特性可知，成环时该边一定是环中最大的边，不应该选取）。如果选出的边比点数少 \(1\)，说明最小生成树存在，否则不存在。 那么如何快速的判断是否成环？我们可以使用并查集来合并点及判断点的连通性。 步骤 读入所有边并初始化并查集（\(f_i = i\)）。 按权值排序。 合并所有边并计算答案。 输出。 Prim 可以从选点的角度来构造生成树，不断将新的点拉入生成树中。 步骤 读入所有边。 把所有点的距离设为 \(\infty\)，并将任意一点距离设为 \(0\)。 寻找没有进入生成树且距离最小的点进入生成树并累加距离到答案。 更新相邻点距离。 重复 \(3, 4\) 步直到所有点进入生成树。 输出。 证明 假定当前的生成树为 \(A\)，且 \(x\) 是离生成树最近的点。如果 \(x\) 与 \(A\) 的边在最终的生成树中，那么现在可以将 \(x\) 拉入生成树中。如果 \(x\) 与 \(A\) 相连的边不在最终的生成树中，那么 \(x\) 必然要通过另一个当前与 \(A\) 直接相连的点 \(y\)，间接与 \(A\) 相连。那么 \(xA,yA,xy\) 构成环，且 \(xA\) 比 \(yA\) 更短，替换后可以得到更小生成树。 例题 1（洛谷 P3366 【模板】最小生成树） 给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。 原题：https://www.luogu.com.cn/problem/P3366 【Kruskal】 代码是以前写的，可能不好看。