Java实现并查集

喝杯82年的Java压压惊

这次需要介绍的就是并查集

那么先说一下 这次的算法是

1. union-find (简单并查集)

2.quick-union (优化的并查集)

3.加权值quick-union(处理了2的最坏情况)

4.路径压缩加权值quick-union

如果只是想要一下算法,你可以直接跳到最后看第4个算法

union-find

故事大概就讲完了 很好理解吧. 其实算法也不难

让我们先看一下 API

加粗样式

public class UnionFind { private int[] id; 存储这几伙强盗的逻辑关系 数组下标i代表第i伙强盗 值代表 他老大是谁 private int count; 表示一共有几个强盗团伙 public UnionFind(int N) 做初始化操作 N 代表一开始有几伙强盗 public int getCount() 获取强盗团伙的数量 public boolean connected(int p, int q) 判断 p 和 q 这两伙强盗 是不是一家的 public int find(int p) 找到第p伙强盗的老大 public void union(int p, int q) 联合两伙强盗 } 

好了让我们一个一个方法来看 首先看构造函数

 public UnionFind(int N) { count = N; id = new int[N]; for(int i = 0; i < N; i++) id[i] = i; } 

public int getCount() { return count; } 

这个方法就不用介绍了吧?

 public int find(int p) { return id[p]; } 

这个方法返回第P伙强盗的老大 id[p] 中存的值就是老大的下标

public boolean connected(int p, int q) { return find(p) == find(q); } 

看看 两个的老大是不是同一个 也很简单把?

接下来就是最关键的一个方法了

联合 其实也不难

public void union(int p, int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot) return; for(int i = 0; i < id.length; i++) if(id[i] == pRoot) id[i] = qRoot; count--; } 

完整代码

public class UnionFind { private int[] id; private int count; public UnionFind(int N) { count = N; id = new int[N]; for(int i = 0; i < N; i++) id[i] = i; } public int getCount() { return count; } public boolean connected(int p, int q) { return find(p) == find(q); } public int find(int p) { return id[p]; } public void union(int p, int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot) return; for(int i = 0; i < id.length; i++) if(id[i] == pRoot) id[i] = qRoot; count--; } } 

好了 让我们分析一下时间复杂度

通过上面的问题 我们需要优化一下算法

quick-union

其他方法不用变 只需要 修改 find() 和 union的两个方法就可以 首先看一下 find()

public int find(int p) { while(p != id[p]) p = id[p]; return p; } 

所以先看一下 union()方法

public void union(int p, int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot) return; id[pRoot] = qRoot; count--; } 

这里3干掉了5 就给3和5 连一条线 并且 ip[5] = 3;

完整代码

public class QuickUnion { private int[] id; private int count; publicQuickUnion(int N) { count = N; id = new int[N]; for(int i = 0; i < N; i++) id[i] = i; } public int getCount() { return count; } public boolean connected(int p, int q) { return find(p) == find(q); } public int find(int p) { while(p != id[p]) p = id[p]; return p; } public void union(int p, int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot) return; id[pRoot] = qRoot; count--; } } 

加权值quick-union

第二个方法已经快了很多

然后都是一样的

最后一个就不画了 3上面连个4
你会发现这样的情况遍历还是很多 树的高度呈线性增长
我们在实际的应用只关心两者联合在一起了 也就是两个团伙结盟在一起的问题

所以我们何不让小团伙依附于大团伙呢?

所以我们要在API里加一个成员变量

private int[] sz; 

public WeightedQuickUnion(int N) { count = N; id = new int[N]; sz = new int[N]; for(int i = 0; i < N; i++) { id[i] = i; sz[i] = 1; } } 

public void union(int p, int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot) return; if(sz[pRoot] < sz[qRoot]) { id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; } else { id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } count--; } 

完整代码

public class WeightedQuickUnion { private int[] id; private int count; private int[] sz; public WeightedQuickUnion(int N) { count = N; id = new int[N]; sz = new int[N]; for(int i = 0; i < N; i++) { id[i] = i; sz[i] = 1; } } public int getCount() { return count; } public boolean connected(int p, int q) { return find(p) == find(q); } public int find(int p) { while(p != id[p]) p = id[p]; return p; } public void union(int p, int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot) return; if(sz[pRoot] < sz[qRoot]) { id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; } else { id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } count--; } } 

路径压缩加权值quick-union

实现方法也简单 其他的不变修改find就行

public int find(int p) { if(p != id[p]) id[p] = find(id[p]); return id[p]; } 

最终版代码 路径压缩加权值quick-union

public class UnionFind { private int[] id; private int count; private int[] sz; public UnionFind(int N) { count = N; id = new int[N]; sz = new int[N]; for(int i = 0; i < N; i++) { id[i] = i; sz[i] = 1; } } public int getCount() { return count; } public boolean connected(int p, int q) { return find(p) == find(q); } public int find(int p) { if (p != id[p]) id[p] = find(id[p]); return id[p]; } public void union(int p, int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot) return; if(sz[pRoot] < sz[qRoot]) { id[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; } else { id[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } count--; } } 

最后的最后让我们分析一下时间复杂度

 存在N伙强盗增长数量级(最坏情况) 算法 构造函数 union() find() union-find算法 O(n) O(n) O(1) quick-union算法 O(n) 树的高度 树的高度 加权quick-union算法 O(n) O(lgn) O(lgn) 路径压缩的加权quick-union算法 O(n) 非常接近O(1) 非常接近O(1) 理想情况 O(n) O(1) O(1) 

大家帮我点个赞呗?!