Kruskal算法
Kruskal算法是一种用来寻找最小生成树的算法之一。
该算法需要用到两个数据结构：
- 存储边的顶点和权值的数据结构
- 并查集
图的存储结构：
（0,1）1
（2,4）2
（3,5）3
（1,4）4
（0,2）5
（0,3）6
（2,3）7
（1,2）8
（4,5）9
并查集：
0 0
1 1
2 2
3 3
4 4
5 5
算法步骤：
- 对图的存储结构，按照权值，从小到大排序。
- 对并查集进行初始化，即把每一个位置中的值初始化为其对应下标。
- 选取存储结构的最小项，查询该边所对应的顶点在并查集中是否同源，同源则进行5，不同于则进行4.
- 若不同源，则把该边加入生成树，并计算和，修改前者的根在并查集中位置的值为后者的根。
- 若同源，则跳过，继续遍历剩余数据结构。
通过Kruskal算法之后：
此时
图的存储结构：
（0,1）1
（2,4）2
（3,5）3
（1,4）4
（0,2）5
（0,3）6
（2,3）7
（1,2）8
（4,5）9
并查集：
0 1
1 4
2 4
3 5
4 5
5 5
该算法适用于简单图