算法代码实现之Union-Find，Golang(Go语言)实现，quick-find、qu

发布时间：2020-12-16 18:33:37 所属栏目：大数据来源：网络整理

导读：本算法主要解决动态连通性一类问题，这里尽量用精炼简洁的话来阐述。数据结构描述：有N个节点（索引0~N-1），可以查询节点数量可以连接两个节点可以查询两个节点是否连通算法大致设计思路：每个节点初始化为不同的整数标记通过一个辅助函数查询某个节

本算法主要解决动态连通性一类问题，这里尽量用精炼简洁的话来阐述。

数据结构描述：

有N个节点（索引0~N-1），可以查询节点数量
可以连接两个节点
可以查询两个节点是否连通

算法大致设计思路：

每个节点初始化为不同的整数标记
通过一个辅助函数查询某个节点的标记值
如果两节点标记相同，说明两节点是连通的

用一个包专门处理union-find算法(unionfind)

定义接口和基类(union_find.go)：

    
    
     
       
     
     
       
     
     
       
     
     
       
     
     
       
     
     
       
     
     
       
     
     
       
     
     
       
     
     
       
     
     
       
     
    
    
package unionfind//union-find的quick-find实现版type QuickFind struct { BaseUnionFind}func (qf *QuickFind) Connectedp, q intboolreturn qf.id[]==q] Union i j :=],123)">if i for k v  range qfid k= icount--func NewQuickFindn *QuickFind&QuickFind{*NewBaseUnionFindn)}}

QuickFind：

a和b进行union的时候，将b及与b连通节点的标记都置为和a的标记一样
标记相同的节点是连通的

quick_find.go:

QuickUnion:

连通的节点形成一棵树，根节点相同

quick_union.go:

//union-find的quick-union实现版type QuickUnion}//查询根节点qu *QuickUnion findRootp int p != qu pfindRoot) rp rq rq rpfunc NewQuickUnion*QuickUnion&QuickUnion}

加权QuickUnion(附带路径压缩优化):

union的时候小树挂在大树下
查询根节点的时候顺便将该节点的父节点直接指向根节点，压缩路径

weighted_quick_union.go:

//union-find的加权quick-union实现版，//另外还作了路径压缩优化type WeightedQuickUnion QuickUnion sz []//查询根节点，顺便压缩路径wqu *WeightedQuickUnion wquwqu]]szrp< rq+=elsefunc NewWeightedQuickUnion*WeightedQuickUnion make([] n 0;++ sz1&WeightedQuickUnion{QuickUnion:*NewQuickUnion),161)">:}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!