本算法主要解决动态连通性一类问题,这里尽量用精炼简洁的话来阐述。
数据结构描述:
算法大致设计思路:
用一个包专门处理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:
i j j c }
QuickUnion:
- 连通的节点形成一棵树,根节点相同