Kurskal算法生成最小生成树MST

时间:2022-07-08 09:53:45

1.解析

while循环其实不是只循环V-1次,因为如果找出的边能够形成环的话,这条边并不是我们需要的边,所以本次循环无效。while循环中其实包含了找出最小的功能,这个其实可以通过单独的一个函数来实现。就是按边长度升序来排列。

kruskal算法其实是一个找边的算法,对于一V个顶点的图,必定由V-1条边构成一个最小生成树,那么按边的权值遍历图每一条边。判断如果添加这条选出的当前权最小的边,图中会不会生成一个环,如果生成环,则当前找到的这条边无效,继续找下一条权值最小边。

每找出一条边,相当于图中合并了两个连通部件(初始化是一个顶点算一个连通部件),因此找到V-1条边就相当于是将原来分离的V个连通部件合并成一个更大的连通部件。

在两个连通部件之间添加一条边,会组成一个更大的连通部件,并且不存在环。

2.算法实例

3.单独提取合并集合的方法

为了是程序更加清晰,将合并集合的方法单独提取出来。代码实例如下:

修改以后原来的程序只稍作修改即可,在void kruskal(graph *g)中作如下修改: