克鲁斯卡尔算法
克鲁斯卡尔算法百度到的解释是：克鲁斯卡尔算法是一种用来寻找最小生成树的算法。在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。这同样是一个比较难以理解的算法，这一次我又是看了别人的博客才理解了一点。
1.将图的所有连接线去掉，只剩顶点
2.从图的边集数组中找到权值最小的边，将边的两个顶点连接起来
3.继续寻找权值最小的边，将两个顶点之间连接起来，如果选择的边使得最小生成树出现了环路，则放弃该边，选择权值次小的边
4.直到所有的顶点都被连接在一起并且没有环路，最小生成树就生成了。
先来看核心代码，然后在解释代码：
int Find(int *parent, int f)
{
//从下标f开始寻找parent数组中元素为0的下标
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; //初始化全部为0,
}
int m, n;
for (int i = 0; i < G->numedges; i++)
{
n = Find(parent, G->edges[i].begin); //从该边的起点开始寻找parent数组中为0的元素的下标，
m = Find(parent, G->edges[i].end);//从该边的终点点开始寻找parent数组中为0的元素的下标，
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);//打印边和权值
}
}
}
这里为了方便，我在生成图的时候利用的是边集数组，并且已经是按权值从小到大排好序的。
可以看到我们定义了一个parent数组，这个数组是干嘛的呢？这个数组就是用来判断边与边是否形成环路的，现在你可能还不太理解。现在你可以将最小生成树的整个过程想象成一个修路的过程，图中的每一个顶点作为一个村庄，现在我们要把村庄连起来，修总距离最短的路，但是不能使村庄之间出现环路，就是比如我要在A和B之间修路，在两个村庄修路连通之前我们先检查一下从A出发和从B出发能否到达同一个村庄，能则说明有环，不能修，不能则说明没环，可以修。我们把parent想象成一幅地图，每修一条路我们就标记一下。
图结构
边集数组
我们来看一下对于上图的这种图，克鲁斯卡尔算法的操作。
第一步初始化parent数组全部为0,意味着所有顶点都没有连接，也就是现在村庄与村庄之间是没有路的状态
for (int i = 0; i < G->numvertex; i++)
{
parent[i] = 0; //初始化全部为0,
}
|
parent |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
第二步循环寻找边集数组中权值小的边（由于我们事前已经排序过，所以只要从边集数组的第0个元素往下判断是否有环即可）
.
0.（4,7）这条边判断是否有环，代码如下：
int Find(int *parent, int f)
{
//从下标f开始寻找parent数组中元素为0的下标
while (parent[f]>0)
{
f = parent[f];
}
return f;
}
n = Find(parent, G->edges[i].begin); //从该边的起点开始寻找parent数组中为0的元素的下标，
m = Find(parent, G->edges[i].end);//从该边的终点点开始寻找parent数组中为0的元素的下标，
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);//打印边和权值
}
|
parent |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
我们从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，修了一条路。
|
parent |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
0 |
0 |
顶点4连到顶点7
1.边（2,8）
|
parent |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
0 |
0 |
parent[2]=0,parent[8]=0，参照地图parent，从村庄2和8出发没有走到同一个村庄，所以放心大胆修条路，n=2,m=8;将2与8连接，改变parent数组,parent[2]=8，现在从2出发能走到村庄8了。
|
parent |
0 |
0 |
8 |
0 |
7 |
0 |
0 |
0 |
0 |
2.边（0,1）
|
parent |
0 |
0 |
8 |
0 |
7 |
0 |
0 |
0 |
0 |
parent[0]=0,parent[1]=0;与上面情况一样，放心大胆修吧，n=0,m=1,更新地图parent[0]=1，意味着从0出发能走到1.
|
parent |
1 |
0 |
8 |
0 |
7 |
0 |
0 |
0 |
0 |
3.边（0,5）
|
parent |
1 |
0 |
8 |
0 |
7 |
0 |
0 |
0 |
0 |
我们从1出发，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
|
parent |
1 |
5 |
8 |
0 |
7 |
0 |
0 |
0 |
0 |
4.边（1,8）
|
parent |
1 |
5 |
8 |
0 |
7 |
0 |
0 |
0 |
0 |
我们从1出发，parent[1]=5，我们走到村庄5，parent[5]=0,最后到达村庄5,，
我们从8出发，parent[8]=0,最后就在村庄8，说明我们没有到同一个村庄，修路修路！！！更新地图parent[5]=8
|
parent |
1 |
5 |
8 |
0 |
7 |
8 |
0 |
0 |
0 |
将1与8连起来
5.边（3,7）
|
parent |
1 |
5 |
8 |
0 |
7 |
8 |
0 |
0 |
0 |
parent[3]=0，parent[7]=0,说明从3和7出发也不会走到同一个村庄，修路，更新地图
|
parent |
1 |
5 |
8 |
7 |
7 |
8 |
0 |
0 |
0 |
6.边（1,6）
|
parent |
1 |
5 |
8 |
7 |
7 |
8 |
0 |
0 |
0 |
我们从1出发，parent[1]=5,来到村庄5，parent[5]=8;来到村庄8，parent[8]=0,我们最后到达村庄8，
我们从6出发，parent[6]=0，最后到达6，没有到的同一村庄，在1,6之间修路，更新地图，parent[8]=6;
|
parent |
1 |
5 |
8 |
7 |
7 |
8 |
0 |
0 |
6 |
7.边（5,6）
|
parent |
1 |
5 |
8 |
7 |
7 |
8 |
0 |
0 |
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）
|
parent |
1 |
5 |
8 |
7 |
7 |
8 |
0 |
0 |
6 |
我们从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）
|
parent |
1 |
5 |
8 |
7 |
7 |
8 |
0 |
0 |
6 |
我们从6出发，parent[6]=0,止于6；
我们从7出发，parent[7]=0,止于7；修路，更新parent
|
parent |
1 |
5 |
8 |
7 |
7 |
8 |
7 |
0 |
6 |
继续执行检查每条边发现在没有符合情况的了，那么克鲁斯卡尔算法生成的最小生成树就生成完了
完整代码：
#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
最后,自己的理解也比较浅显，记录一下，加深印象，希望日后能有更深的理解。
相关阅读
你是如何坚持读完《算法导论》这本书的？ 《算法导论》不够猛，答者顺便补充 “你是如何坚持读完《计算机编程的艺术》这本书的？”
人类会关注图中对象的形状，深度学习计算机系统所用的算法不一样，它会研究对象的纹理。图片中的动物轮廓是猫，但是猫披着大象皮肤纹理
基于深度学习的人脸识别算法简介Contrastive LossTriplet LossCenter LossA-Softmax Loss参考文献：简介 我们经常能从电影中看到各
AIC信息准则（即Akaike information criterion），是用来衡量统计模型拟合优良性的一个标准，是是由日本统计学家赤池弘次创立和发展的，因
【数据结构与算法】初入数据结构的哈希表(Hash Table)
初入数据结构的哈希表(Hash Table) 这次我们来总结一下关于哈希表的知识，首先我们要了解什么是哈希表，哈希函数的构造思路有哪些