那么显然这两条边之间并不会引起冲突，所以我们可以都保留。所以这不会引起反例。
第二种情况是这两条边连通三个不同的集合：
这种情况和上面一样，我们可以都要，并不会影响连通情况。所以也不会引起反例。
最后一种是这两条边连通的是两个集合，也就是下面这样。
在这种情况下，这两条件之间互相冲突，我们只能选择其中的一条。但是显然，不论我们怎么选都是一样的。因为都是连接了这两个连通块，然后带来的价值也是一样的，并不会影响最终的结果。
当我们把所有情况列举出来之后，我们就可以明确，在这个问题当中贪心法是可行的，并不会引起反例，所以我们可以放心大胆地用。
实际问题与代码实现
明白了算法原理之后，我们来看看这个算法的实际问题。其实这个算法在现实当中的使用蛮多的，比如自来水公司要用水管连通所有的小区。而水管是有成本的，那么显然自来水公司希望水管的总长度尽量短。比如山里的村庄通电，要用尽量少的电缆将所有村庄连通，这些类似的问题其实都可以抽象成最小生成树来解决。当然现实中的问题可能没有这么简单，除了考虑成本和连通之外，还需要考虑地形、人文、社会等其他很多因素。
最后，我们试着用代码来实现一下这个算法。
classDisjointSet:
def__init__(self,element_num=None):
self._father={}
self._rank={}
#初始化时每个元素单独成为一个集合
ifelement_numisnotNone:
foriinrange(element_num):
self.add(i)
defadd(self,x):
#添加新集合
#如果已经存在则跳过
ifxinself._father:
return
self._father[x]=x
self._rank[x]=0
def_query(self,x):
#如果father[x]==x，说明x是树根
ifself._father[x]==x:
returnx
self._father[x]=self._query(self._father[x])
returnself._father[x]
defmerge(self,x,y):
ifxnotinself._father:
self.add(x)
ifynotinself._father:
self.add(y)
#查找到两个元素的树根
x=self._query(x)
y=self._query(y)
#如果相等，说明属于同一个集合
ifx==y:
return
#否则将树深小的合并到树根大的上
ifself._rank[x]<self._rank[y]:
self._father[x]=y
else:
self._father[y]=x
#如果树深相等，合并之后树深 1
ifself._rank[x]==self._rank[y]:
self._rank[x] =1
#判断是否属于同一个集合
defsame(self,x,y):
returnself._query(x)==self._query(y)
#构造数据
edges=[[1,2,7],[2,3,8],[2,4,9],[1,4,5],[3,5,5],[2,5,7],[4,5,15],[4,6,6],[5,6,8],[6,7,11],[5,7,9]]
if__name__=="__main__":
disjoinset=DisjointSet(8)
#根据边长对边集排序
edges=sorted(edges,key=lambdax:x[2])
res=0
foru,v,winedges:
ifdisjoinset.same(u,v):
continue
disjoinset.merge(u,v)
res =w
print(res)
其实主要都是利用并查集，我们额外写的代码就只有几行而已，是不是非常简单呢？
结尾
相信大家也都感觉到了Kruskal算法的原理非常简单，如果你是顺着文章脉络这样读下来，相信一定会有一种顺水推舟，一切都自然而然的感觉。也正是因此，它非常符合直觉，也非常容易理解，一旦记住了就不容易忘记，即使忘记了我们也很容易自己推导出来。这并不是笑话，有一次我在比赛的时候临时遇到了，当时许久不写Kruskal算法，一时想不起来。凭着仅有的一点印象，硬是在草稿纸上推导了一遍算法。
在下一篇文章当中我们继续研究最小生成树问题，一起来看另外一个类似但不相同的算法——Prim。
今天的文章就到这里，原创不易，需要你的一个关注，你的举手之劳对我来说很重要。
