本文共 2709 字，大约阅读时间需要 9 分钟。

以边为目标去构建最小生成树的算法就是Kruskal算法。

直接去找最小权值的边去构建生成树是很自然的想法，只不过构建时要考虑是否会形成环路而已。 共有15条边，将它们按权值升序排列。 接下来就是遍历按顺序每一条边； 对于某一条边是否该被纳入最小生成树的判定如下（涉及到并查集算法）： 判断这条边的两个顶点G.edge[i].begin和G.edge[i].end是否在同一个集合中；若顶点G.edge[i].begin和顶点G.edge[i].end不在同一个集合，即说明该边（G.edge[i].begin–>G.edge[i].end）没有与现有的生成树形成环路，可以把该边纳入现有的生成树；否则说明该边与现有的生成树会形成环路，所以不能把该边纳入现有的生成树。 所以问题归结到两点上： 1.如何判断某一条边的两个顶点是否在同一个集合中？ 答：并查集算法，利用Find函数找出每个顶点所在集合的根结点。若根结点相同，则说明这两个顶点在同一个集合中；若根结点不同，这说明这两个顶点属于两个不同的集合。 2.如果某一条边的两个顶点属于两个不同的集合，可以纳入现有的生成树，那么该如何纳入？ 答：把两个集合合并为一个集合：即先找出每个顶点所在集合的根结点，然后把两个根结点之间建立上下级关系（这里谁是上级谁是下级无所谓，优化算法不在这里讨论）。

接下来用图解法画出我的理解：

首先定义parent[e_root] = b_root;表示b_root是e_root的上级（这就是两个集合的合并,b_root和e_root分别是两个集合的根结点）。

完整代码如下：

#include
   
    using namespace std;#define MAXEDGE 20#define MAXVEX 20typedef struct {   	int begin;	int end;	int weight;}Edge;typedef struct {   	Edge edge[MAXEDGE];	int numEdges;}MGraph;void MiniSpanTree_KrusKal(MGraph& G);int Find(int*parent, int f);int main() {   	MGraph G;//权值升序排序	G.edge[0].begin = 4; G.edge[0].end = 7; G.edge[0].weight = 7;	G.edge[1].begin = 2; G.edge[1].end = 8; G.edge[1].weight = 8;	G.edge[2].begin = 0; G.edge[2].end = 1; G.edge[2].weight = 10;	G.edge[3].begin = 0; G.edge[3].end = 5; G.edge[3].weight = 11;	G.edge[4].begin = 1; G.edge[4].end = 8; G.edge[4].weight = 12;	G.edge[5].begin = 3; G.edge[5].end = 7; G.edge[5].weight = 16;	G.edge[6].begin = 1; G.edge[6].end = 6; G.edge[6].weight = 16;	G.edge[7].begin = 5; G.edge[7].end = 6; G.edge[7].weight = 17;	G.edge[8].begin = 1; G.edge[8].end = 2; G.edge[8].weight = 18;	G.edge[9].begin = 6; G.edge[9].end = 7; G.edge[9].weight = 19;	G.edge[10].begin = 3; G.edge[10].end = 4; G.edge[10].weight = 20;	G.edge[11].begin = 3; G.edge[11].end = 8; G.edge[11].weight = 21;	G.edge[12].begin = 2; G.edge[12].end = 3; G.edge[12].weight = 22;	G.edge[13].begin = 3; G.edge[13].end = 6; G.edge[13].weight = 24;	G.edge[14].begin = 4; G.edge[14].end = 5; G.edge[14].weight = 26;	G.numEdges = 15;	MiniSpanTree_KrusKal(G);	system("pause");	return 0;}void MiniSpanTree_KrusKal(MGraph& G) {   	int parent[MAXVEX];//parent用来找根结点	for (int i = 0; i < MAXVEX; i++)		parent[i] = -1;	for (int i = 0; i < G.numEdges; i++) {   //遍历每条边		int b_root = Find(parent, G.edge[i].begin);//找各自集合的根结点		int e_root = Find(parent, G.edge[i].end);		if (b_root != e_root) {   //假如b_root与e_root不相等，说明顶点G.edge[i].begin和顶点G.edge[i].end不在同一个集合，即说明边（G.edge[i].begin-->G.edge[i].end）没有与现有的生成树形成环路			parent[e_root] = b_root;//把两个集合合并成一个,即令b_root的上级为e_root或令e_root的上级为b_root			//parent[b_root] = e_root;//这样写也行，谁是上下级没关系			cout << G.edge[i].begin << "-->" << G.edge[i].end << endl;		}	}}int Find(int*parent, int f) {   //用来找根结点	while (parent[f] != -1)		f = parent[f];	return f;}
   

所以最终构成最小生成树的边如下：