序
最小生成树问题是我在各项图论问题中最先理解与解决的，其目的就是在连通图中选择出：
使得各点构成联通的最小边权的边集
其中用到的数据结构与算法也是相对很好理解的并查集和Kruskal算法，我在我之前的文章小话数据结构-图 (聚焦与于实现的理解)也有提到过，现在再来系统的阐述一下这问题的解决思路。
并查集
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
并查集是一个写法简单，经常使用到的数据结构，主要操作有以下三种
初始化操作
int p[N]; //存储每个点的祖宗节点 for (int i = 1; i <= n; i ++ ) p[i] = i;// 初始化，节点编号是1~n
查找函数
int find( int x ){ if(p[x] != x) p[x] = find(p[x]); return p[x];//返回的是x的祖宗节点 }
合并操作
p[find(a)] = find(b);//将a加入b的祖宗的集合
并查集还可以维护每一个子集的大小、或是自子集到祖宗节点的距离，给出以下代码，只是使用Kruskal算法只需要使用朴素的并查集就可以了。
int p[N], size[N];//p[]存储每个点的祖宗节点, size[]表示祖宗节点所在集合中的点的数量 int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x]; } for (int i = 1; i <= n; i ++ ){// 初始化，节点编号是1~n p[i] = i; size[i] = 1; } // 合并a和b所在的两个集合并储存集合中元素个数： size[find(b)] += size[find(a)]; p[find(a)] = find(b);
int p[N], d[N];//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离 int find(int x){ if (p[x] != x){ int u = find(p[x]); d[x] += d[p[x]];//继承偏移量 p[x] = u; } return p[x]; } for (int i = 1; i <= n; i ++ ){// 初始化，节点编号是1~n p[i] = i; d[i] = 0; } // 合并a和b所在的两个集合： p[find(a)] = find(b); d[find(a)] = distance; // 初始化find(a)的偏移量
Kruskal算法【O(mlogm)】
这个顶着一个高端名字的针对解决最小生成树的算法，也就是一个彻头彻尾的贪心思想的算法，基本的步骤如下
①：将所有边按照权值从小到大排序
②：将所有边依次放入图中，如果没有连入新的点，则丢弃不要。
③：当整个图联通时，返回结果
这里给一张别人博客里非常直观的动图
在②步骤中，并查集就可以发挥出其作用，快速的判定出当前选择的边的点是否在一个集合中，从而方便的实现算法。
那我们直接用代码来实现：
int n, m; int p[N]; struct Edge{ int a, b, w; }edges[M]; int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x]; } int kruskal(){ sort(edges, edges + m);//排序 for (int i = 1; i <= n; i ++ ) p[i] = i; int res = 0, cnt = 0;//res记录权值，cnt记录已选择的边数 for (int i = 0; i < m; i ++ ){ int a = edges[i].a, b = edges[i].b, w = edges[i].w; a = find(a), b = find(b); if (a != b) {//将选择的边并入图中 p[a] = b; res += w; cnt ++ ; } } if (cnt < n - 1) return INF;//若结束后不能使整个图联通，则无法求出结果 return res; }
至此，kruskal算法就成功实现了，可以根据实际情况改变部分参数，从而获得需要求解的部分。
希望我的抛砖引玉能引起更多的思考😄!