最小（代价）生成树-克鲁斯卡尔算法（Kruskal）
克鲁斯卡尔算法是一种用来寻找最小生成树的算法。在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。这同样是一个比较难以理解的算法，这一次我又是看了别人的博客才理解了一点。
1.将图的所有连接线去掉，只剩顶点
2.从图的边集数组中找到权值最小的边，将边的两个顶点连接起来
3.继续寻找权值最小的边，将两个顶点之间连接起来，如果选择的边使得最小生成树出现了环路，则放弃该边，选择权值次小的边
4.直到所有的顶点都被连接在一起并且没有环路，最小生成树就生成了。
- 在生成图的时候利用的是边集数组，并且已经是按权值从小到大排好序的。
- parent数组就是用来判断边与边是否形成环路的，现在你可能还不太理解。现在你可以将最小生成树的整个过程想象成一个修路的过程，图中的每一个顶点作为一个村庄，现在我们要把村庄连起来，修总距离最短的路，但是不能使村庄之间出现环路，就是比如我要在A和B之间修路，在两个村庄修路连通之前我们先检查一下从A出发和从B出发能否到达同一个村庄，能则说明有环，不能修，不能则说明没环，可以修。我们把parent想象成一幅地图，每修一条路我们就标记一下。
解释代码
- 第一步、初始化parent数组全部为0,意味着所有顶点都没有连接，也就是现在村庄与村庄之间是没有路的状态
for (int i = 0; i < G->numvertex; i++)
{
parent[i] = 0; //初始化全部为0,
}
- 第二步、循环寻找边集数组中权值小的边（由于我们事前已经排序过，所以只要从边集数组的第0个元素往下判断是否有环即可）
n = Find(parent, edges[i].begin); // 4 2 0 1 5 3 8 6 6 6 7
m = Find(parent, edges[i].end); // 7 8 1 5 8 7 6 6 6 7 7
if( n != m ) // 如果n==m，则形成环路，不满足！
{
parent[n] = m; // 将此边的结尾顶点放入下标为起点的parent数组中，表示此顶点已经在生成树集合中
printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
}
int Find(int *parent, int f)
{
while( parent[f] > 0 )
{
f = parent[f];
}
return f;
}
0.（4,7）这条边判断是否有环，代码如下：
-
我们从4出发，现在来看parent数组，parent[4]=0，（注：parent[i]=0,意味着该连通路继续往下没有路了）意思是到4就停了，此时得到n=4;
-
我们从7出发，parent[7]=0,到7就停了，也没有走出去，此时得到m=7;所以从4、7出发不会走到同一个村庄，修路，改变地图parent数组的值，parent[4]=7，意味着从村庄4出发能走到7，修了一条路。
顶点4连到顶点7
-
边（2,8）
-
parent[2]=0,parent[8]=0，参照地图parent，从村庄2和8出发没有走到同一个村庄，所以放心大胆修条路，n=2,m=8;将2与8连接，改变parent数组,parent[2]=8，现在从2出发能走到村庄8了。
2.边（0,1）
parent[0]=0,parent[1]=0;与上面情况一样，放心大胆修吧，n=0,m=1,更新地图parent[0]=1，意味着从0出发能走到1.
3.边（0,5）
-
我们从0出发，parent[0]=1,说明此时0村庄已经有一条路通往外界了，它和1是连接的，那么按照parent的指引，我们来到了村庄1发现没路了parent[1]=0，最后到达村庄1，
-
我们从5出发，parent[5]=0,地图指示没有路往下走了，没有走到同一个村庄，所以可以在村庄0和5之间修路了，更新一下地图parent[1]=5。
-
这里需要解释一下，为什么是在村庄0和5之间修路呢，因为我们要检查的就是能不能在0和5之间修路，既然结论是可以，那么就在0和5之间修条路就行了，那为什么标记地图的时候标记的是parent[1]=5呢？因为我们的地图是按照修路的顺序进行更新的，上次0和1已经修通路了按照指示我们知道0可以到1了，这次又修了5和他们连通，我们就接下来继续标记，即从连通路中=0的那个下标开始标记下一个修路的村庄。意味着0可以到1可以到5
4.边（1,8）
-
我们从1出发，parent[1]=5，我们走到村庄5，parent[5]=0,最后到达村庄5,，
-
我们从8出发，parent[8]=0,最后就在村庄8，说明我们没有到同一个村庄，修路修路！！！更新地图parent[5]=8
5.边（3,7）
-
parent[3]=0，parent[7]=0,说明从3和7出发也不会走到同一个村庄，修路，更新地图
6.边（1,6）
-
我们从1出发，parent[1]=5,来到村庄5，parent[5]=8;来到村庄8，parent[8]=0,我们最后到达村庄8，
-
我们从6出发，parent[6]=0，最后到达6，没有到的同一村庄，在1,6之间修路，更新地图，parent[8]=6;
7.边（5,6）
-
我们从5出发，parent[5]=8;来到村庄8，parent[8]=6,来到村庄6，parent[6]=0;所以最终到达村庄6；
-
我们从6出发，parent[6]=0,最后也是止于村庄6，连通5和6村庄就会出现环路，所以5和6不能修路
8.边（1,2）
我们从1出发，parent[1]=5,来到5，parent[5]=8,来到8，parent[8]=6,来到6，parent[6]=0,到达6终止
我们从2出发，paerent[2]=8,来到8，parent[8]=6,来到6，parent[6]=0,到达6终止，修路会出现环路，所以不修
9.边（6,7）
-
我们从6出发，parent[6]=0,止于6；
-
我们从7出发，parent[7]=0,止于7；修路，更新parent
- 继续执行检查每条边发现在没有符合情况的了，那么克鲁斯卡尔算法生成的最小生成树就生成完了
完整代码
#include<stdio.h>
#define MAXEDGE 100
#define MAXVERTEX 100
typedef struct Edge
{
int begin;//边的起点
int end; //边的终点
int wight;//边的权值
}Edge;
typedef struct Graph
{
char vertex[MAXVERTEX];//顶点
Edge edges[MAXEDGE];//边
int numvertex,numedges;//顶点和边的个数
}MGraph;
void CreateGraph(MGraph* G)
{
printf("请输入顶点和边的个数：\n");
scanf("%d%d", &G->numvertex, &G->numedges);
printf("请输入顶点：\n");
getchar();//利用该函数除去上一系我们在输入结束时按得回车符
for (int i = 0; i < G->numvertex; i++)
{
scanf("%c", &G->vertex[i]);
}
printf("按权值从小到大输入边（vi,vj）对应的起点和终点的下标，begin，end以及权值wight:\n");
for (int k = 0; k < G->numedges; k++)
{
Edge e;
scanf("%d%d%d", &e.begin, &e.end, &e.wight);
G->edges[k] = e;
}
}
int Find(int *parent, int f)
{
while (parent[f]>0)
{
f = parent[f];
}
return f;
}
//最小生成树，克鲁斯卡尔算法
void Kruskal(MGraph *G)
{
int parent[MAXVERTEX];//存放最小生成树的顶点
for (int i = 0; i < G->numvertex; i++)
{
parent[i] = 0;
}
int m, n;
for (int i = 0; i < G->numedges; i++)
{
n = Find(parent, G->edges[i].begin);
m = Find(parent, G->edges[i].end);
if (n != m)//m=n说明有环
{
parent[n] = m;
printf("(%d,%d) %d\t", G->edges[i].begin, G->edges[i].end, G->edges[i].wight);//打印边和权值
}
}
}
int main()
{
MGraph G;
CreateGraph(&G);
Kruskal(&G);
return 0;
}
对于上面的那张图最后输出 （4,7）7，（2,8）8，（0,1）10，（0,5）11，（1,8）12，（3,7）16，（1,6）16，（6，7）19
