这是因为采用了并查集这种数据結构
set[]这个数组在算法中所起的作用不是你想的那样,你去看看并查集的知识相信你一看就明白了。
我刚看了一下我还是搞不懂并查集和树的双亲存储结构有啥不同,都是用一维数组来表示数组里存储的是该结点的双亲结点。。请详细指教!!!谢谢!!
克鲁斯卡爾算法在加入一条边之前先要判断加入这条边是否会产生回路。
判断的依据是这条边的两个集合端点问题是否在同一棵树中。如果是嘚话就不能加入因为会产生回路;如果两个集合端点问题分别在不同的树中,就不会产生回路而是把两棵树连成更大的一棵树。
我们知道树可以看做是点的集合那么判断两个点是否在同一棵树中,就等价于判断这两个点是否在同一个集合中
如果只用简单暴力的方式來解决这个问题是很低效的,并查集就可以提高效率
并查集本质上就是一个树形的数据结构,而且就是你说的那样采用了双亲表示法。原理很简单如果A跟B在一个集合中,A跟C在一个集合中那么B跟C必然在一个集合中。对应到并查集中就是如果A点所在的树的根节点和B点嘚根节点一样,那么A和B就在同一棵树中
说白了,并查集就是一个采用双亲表示法的树形数据结构用以高效解决集合的合并、查询的问題。