union-find算法
union-find算法是一个解决动态连通性的经典算法, 具有广泛性的应用. 简单起见, 我们将对象称为触点, 将整数对称为连接, 将等价类称为连通分量, 并用0 到N-1的整数来表示N个触点. API 1 2 3 4 5 6 7 public class UF { UF(int N) // 以整数标识初始化N个触点 void union(int p, int q) // 在p和q之间添加一条连接 int find(int p) //p所在分量的标识符 boolean connected(int p, int q) // p和q之间是否存在于同一个分量中 int count() // 连通分量的数量 } 成本模型: 以数组的访问次数作为成本模型, 无论读写. 算法的关键在于find和union的设计上. quick-find算法 1 2 3 4 5 6 7 8 9 10 11 12 //quick-find算法 public int find(int p) { return id[p]; } public void union(int p, int q) { int pID = find(p), qID = find(q); // 两次读操作 if (pID != qID) { // N次读操作, 1~(N-1)次写操作 for (int i = 0; i < id.length; i++) if (id[i] == pID) id[i] = qID; count--; } } quick-find使用一个触点为索引的数组作为数据结构, 每次find()调用访问数组一次, 而union()调用访问数组(N+3)到(2N+1)次. 假设我们最后只得到 了一个连通分量, 那么至少需要调用N-1次union(), 即至少$ (N+3)(N-1) \sim N^2 $次数组访问. 意味着该算法是平方级别的, 也意味着该算法不试用于 规模更大(百万级)的场景. ...