algorithm 基于不交集的最佳实现
示例
我们可以做两件事来改进简单和次优不相交集子算法:
路径压缩启发式:findSet不需要处理高度大于的树2。如果最终迭代了这样的树,它可以将较低的节点直接链接到根,从而优化将来的遍历。
subalgofindSet(v:anode):
ifv.parent!=v
v.parent=findSet(v.parent)
returnv.parent
基于高度的合并启发式:对于每个节点,存储其子树的高度。合并时,将较高的树作为较小树的父树,这样就不会增加任何人的身高。
subalgounionSet(u,v:nodes):
vRoot=findSet(v)
uRoot=findSet(u)
ifvRoot==uRoot:
return
ifvRoot.height<uRoot.height:
vRoot.parent=uRoot
elseifvRoot.height>uRoot.height:
uRoot.parent=vRoot
else:
uRoot.parent=vRoot
uRoot.height=uRoot.height+1
这会导致每次操作都花费时间,而这是快速增长的阿克曼函数的逆函数,因此增长非常缓慢,可以考虑用于实际目的。O(alpha(n))alphaO(1)
由于初始排序,因此构成了整个Kruskal的算法。O(mlogm+m)=O(mlogm)
注意
路径压缩可能会降低树的高度,因此在联合操作期间比较树的高度可能不是一件容易的事。因此,为了避免存储和计算树的高度的复杂性,可以随机选择生成的父级:
subalgo unionSet(u, v: nodes): vRoot = findSet(v) uRoot = findSet(u) if vRoot == uRoot: return if random() % 2 == 0: vRoot.parent= uRoot else: uRoot.parent= vRoot
在实践中,这种随机算法与用于findSet操作的路径压缩一起将产生可比的性能,但实现起来要简单得多。