生成树的定义
一个连通图的生成树是一个极小的连通子图，它包含图中全部的n个顶点，但只有构成一棵树的n-1条边。
可以看到一个包含3个顶点的完全图可以产生3颗生成树。对于包含n个顶点的无向完全图最多包含
3. 选择边
6. 选择边
判断添加一条边后是否形成环
要判断添加一条边 X-Y 是否形成环，我们可以判断顶点X在最小生成树中的终点与顶点Y在最小生成树中的终点是否相同，如果相同则说明存在环路，否则不存环路，从而决定是否添加一条边。
所谓终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。看下图，我们可以对图中顶点进行排序，排序后的顶点存放在一个数组中，每一个顶点则对应一个下标，同样的我们针对排序后的数组创建一个顶点的终点数组，初始时图中的每一个顶点是一棵树，每一个顶点的终点初始化为自身，我们用0来表示。
|
下标 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
数据 |
V0 |
V1 |
V2 |
V3 |
V4 |
V5 |
V6 |
V7 |
V8 |
|
终点 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
回到之前的算法执行过程，我们配合这个终点数组再来一次。
- 选择权值最小的边
6
7
8
数据
V0
V1
V2
V3
V4
V5
V6
V7
V8
终点
0
0
0
0
7
0
0
0
0
此时发现4的终点更新为7；
- 选择边
6
7
8
数据
V0
V1
V2
V3
V4
V5
V6
V7
V8
终点
0
0
8
0
7
0
0
0
0
2的终点更新为8；
- 选择边
6
7
8
数据
V0
V1
V2
V3
V4
V5
V6
V7
V8
终点
1
0
8
0
7
0
0
0
0
4. 选择边
6
78数据V0V1V2V3V4V5V6V7V8终点558070000
5.选择边
6
78数据V0V1V2V3V4V5V6V7V8终点558078000
6.选择边
6
78数据V0V1V2V3V4V5V6V7V8终点558778000
7.选择边
6
78数据V0V1V2V3V4V5V6V7V8终点558778006
8.选择边 级别的。
- 选择边
- 选择边
