首先，因为最近刚学了最小生成树，所以想趁热打火。 先总结一下吧~
奶酪图、树的概念、遍历和保存以及本文的所有代码都是用C写的。
最小生成树概念最小生成树(Minimum Spanning Tree，MST )是一种特殊的映射。 虽然具备朴素树的所有性质，但图中边权最小，但也是通过各节点的子树。
定义具有NN-N个节点的联结图的生成树是原图的极小联结子图，包含原图中的NN-N个所有节点，并且具有维持图表联结的最小边。 可以由Kruskal (悲伤枕头)算法或Prim算法确定最小生成树。 [1]
大意一张连通图G G G中，有nn个节点和mm条边，第I个边的权重为w i w_i wi。 将图表G G G的最小生成树作为T T T。
那么，图G G G的最小生成树TT必须满足以下条件。
T T T必须包括G G G的所有节点； TT的边数必须等于n1n-1n1； TT的边权和所有生成树中必须是最小的； T T T必须是G G G的子图。 如果有以下连结图gg (左)，则其最小生成树tt为图)右)。
[2]
很明显，对于图g g，t
T T 的边权和在所有生成树中最小。我们称这样的树为图 G G G 的 最小生成树（简称MST）。 算法我们不妨来介绍两种较为常见的求最小生成树的算法。
在介绍算法之前，我们先来看这样一道题目：
题目链接：洛谷P3366。
题目很容易理解，即求出给定图的最小生成树边权和。那么，我们来看看这些算法吧！
Kruskal 基本思路Kruskal（悲凉的枕头） 是一种贪心策略，类似图论中的Bellman-Ford算法。
简单来说，如果我们挑选了 n − 1 n-1 n−1 条较小边，那么显而易见，这 n − 1 n-1 n−1 条边的权值相加也会是一个较小值。按照这种思路，我们可以挑选 n − 1 n-1 n−1 条 G G G 里面最小的边并将它们相连。
但是，你以为这就完了？怎么可能。
显然我们上面的做法有一个缺陷：它虽然保证了边权和最小，但是得出的却并不一定是一棵树。相反，它反而有可能得出来一个图（或森林）。我们需要解决这个问题。
显然，对于一条 u ↔ v u leftrightarrow v u↔v 的无向边，若点 u u u 和点 v v v 已经连通（直接或间接），那么我们就不再需要加入当前边了。
对于每次遍历，我们都会对当前边的所到达的节点进行一个排查：如果节点已经连通，则无需加边；否则连接两点。
这样一来，我们就剩下一个最重要的问题没解决了：如何判断两个点有没有连通？
我们可以使用并查集这个数据结构进行存储和判重。每次判断两点的连通性的时候，我们只需要查询他们的祖先是否相同即可。同理，对于每次连接操作，我们只需要进行并查集的合并操作来合并 u , v u,v u,v 两点即可。
参考代码 #include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int N = 2 * 1e5 + 10;struct edge { // 存边 int u, v, w;} e[N];edge mst[5010]; // 最小生成树int vtx[5010], k, ans, n, m; // vtx并查集数组，k当前最小生成树节点数，ans边权和bool cmp(edge a, edge b) { return a.w < b.w; // 按照边权排序}int Find(int x) { // 并查集查找操作 if (vtx[x] == x) return x; return vtx[x] = Find(vtx[x]);}void Union(int u, int v) { // 并查集合并操作 int fu = Find(u), fv = Find(v); if (fu != fv) vtx[fv] = fu;}void kruskal() { // Kruskal最小生成树 for (int i = 0; i < m; i++) { // 遍历所有边 if (Find(e[i].u) != Find(e[i].v)) { // 如果两点没有连接 k++; // MST边数++ mst[k].u = e[i].u, mst[k].v = e[i].v, mst[k].w = e[i].w; // 记录当前边 ans += e[i].w; // 总权重增加 Union(e[i].u, e[i].v); // 连接两点 } }}int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) vtx[i] = i; // 并查集初始化，祖先都是自己，即每个点都未连接 for (int i = 0; i < m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); sort(e, e + m, cmp); // 对边权进行排序 kruskal(); // 获取MST if (k == n - 1) printf("%dn", ans); // 如果边数满足条件，输出总权值 else printf("orz"); // 否则输出orz return 0;} Prim 基本思路Prim（普利姆） 是Dijkstra的一个扩展。
Prim算法与Dijkstra算法唯一的区别在于：Prim算法所记录的距离（dis数组）并非从某个起点到终点的距离，而是当前的生成树到某个点的最短距离。
其余部分与Dijkstra算法一致。同样，Prim算法也可以使用堆进行优化，以提高效率。
但是，一般我们不推荐在稀疏图上使用Prim堆优化。堆优化后的Prim在稀疏图上的效率与Kruskal类似，但明显Kruskal代码复杂度较低。
参考代码 #include <iostream>#include <cstdio>#include <memory.h>#include <algorithm>using namespace std;const int N = 5010;int g[N][N], dis[N]; // 邻接矩阵存图bool vis[N]; // 是否经过了某个点int n, m, ans, u, v, w;void initialize() { // 初始化 memset(g, 0x3f, sizeof(g)); memset(dis, 0x3f, sizeof(dis));}void addEdge(int u, int v, int w) { // 添加一条 u <-> v，权值为w的无向边 if (u != v && g[u][v] > w) g[u][v] = g[v][u] = w;}void prim() { // Prim for (int i = 0; i < n; i++) { // 遍历每个点 int k = 0; // 距离最近的点的坐标 for (int j = 1; j <= n; j++) { // 寻找距离点i最近的未访问过的点 if (!vis[j] && dis[j] < dis[k]) k = j; } vis[k] = 1; // 标记访问 ans += dis[k]; // 记录权值 for (int j = 1; j <= n; j++) { // 再次遍历每个点，更新最短路 if (!vis[j] && dis[j] > g[k][j]) { // 未访问过且路程比当前记录的小 dis[j] = g[k][j]; // 更新权值 } } }}int main() { initialize(); scanf("%d%d", &n, &m); while (m--) { scanf("%d%d%d", &u, &v, &w); addEdge(u, v, w); addEdge(v, u, w); } dis[1] = 0; // 约定俗成，从点1跑prim，赋值为0是为了消除自环 prim(); for (int i = 1; i <= n; i++) { // 判断是否建立成树 if (!vis[i]) { // 如果有点未访问，则没有最小生成树 printf("orzn"); return 0; } } printf("%dn", ans); // 否则输出权重和 return 0;} 参考资料 最小生成树_百度百科 最小生成树的两种方法（Kruskal算法和Prim算法）