数据结构(十一)-并查集

参考文献

并查集

• 处理连通性问题

package com.holelin.unionfind;

/**
 * 并查集接口
 */
public interface UnionFind {
	/**
	 * p,q是否属于同一集合
	 *
	 * @param p p表示的元素
	 * @param q q表示的元素
	 * @return 是返回tue;反之返回false;
	 */
	boolean isConnected(int p, int q);

	/**
	 * 合并两个元素所属的集合
	 *
	 * @param p p表示的元素
	 * @param q q表示的元素
	 */
	void unionElements(int p, int q);

	/**
	 * 返回并查集中元素的个数
	 *
	 * @return 并查集中元素的个数
	 */
	int getSize();
}

QuickFind

package com.holelin.unionfind;

/**
 * ClassName: QuickFind
 * 并查集第一版 (Quick Find)
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/16
 */

public class QuickFind implements UnionFind {
	private int[] id;

	public QuickFind(int size) {
		id = new int[size];
		// 设置每个元素的集合编号
		for (int i = 0; i < size; i++) {
			id[i] = i;
		}
	}

	/**
	 * 查询元素p所对应的集合编号
	 *
	 * @param p 元素p
	 * @return 元素p所对应的集合编号
	 */
	private int find(int p) {
		if (p < 0 || p >= id.length) {
			throw new IllegalArgumentException("p is out of bound");
		}
		return id[p];
	}

	/**
	 * O(1)
	 */
	@Override
	public boolean isConnected(int p, int q) {
		return find(p) == find(q);
	}

	/**
	 * O(n)
	 */
	@Override
	public void unionElements(int p, int q) {
    // 将p和q归并到相同的分量中
		int pID = find(p);
		int qID = find(q);
		// 如果p和q已经在相同分量之中则不需要采取任何行动
		if (pID == qID) {
			return;
		}
    // 将p分量重命名为q的名称
		for (int i = 0; i < id.length; i++) {
			if (id[i] == pID) {
				id[i] = qID;
			}
		}
	}

	@Override
	public int getSize() {
		return id.length;
	}
}

基于rank的优化

• 加权quick-union: 总是将较小的树连接到较大的树上.

package com.holelin.unionfind;

/**
 * ClassName: QuickUnionByRank
 * 基于rank的优化
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/16
 */

public class QuickUnionByRank implements UnionFind {
	private int[] parent;
	/**
	 * rank[i] 表示以i为根的集合所表示的树的层数
	 */
	private int[] rank;

	public QuickUnionByRank(int size) {
		parent = new int[size];
		rank = new int[size];
		for (int i = 0; i < size; i++) {
			parent[i] = i;
			rank[i] = 1;
		}
	}

	/**
	 * 查询元素p所对应的集合编号
	 * O(h) h为树的高度
	 *
	 * @param p 元素p
	 * @return 元素p所对应的集合编号
	 */
	private int find(int p) {
		if (p < 0 || p >= parent.length) {
			throw new IllegalArgumentException("p is out of bound");
		}
		// p == parent[p] -- p指向自己,此时p为根节点
		while (p != parent[p]) {
			p = parent[p];
		}
		return p;
	}

	@Override
	public boolean isConnected(int p, int q) {
		return find(p) == find(q);
	}

	@Override
	public void unionElements(int p, int q) {
		int pRoot = find(p);
		int qRoot = find(q);
		if (qRoot == pRoot) {
			return;
		}
		// 将rank低的集合指向rank高的集合
		if (rank[pRoot] < rank[qRoot]) {
			parent[pRoot] = qRoot;
		} else if (rank[pRoot] > rank[qRoot]) {
			parent[qRoot] = pRoot;
		} else {
			parent[qRoot] = pRoot;
			rank[pRoot] += 1;
		}
	}

	@Override
	public int getSize() {
		return parent.length;
	}
}

基于路径压缩的优化

package com.holelin.unionfind;

/**
 * ClassName: QuickUnionByRank
 * 基于路径压缩的优化
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/16
 */

public class QuickUnionByPathCompression implements UnionFind {
	private int[] parent;
	/**
	 * rank[i] 表示以i为根的集合所表示的树的层数
	 */
	private int[] rank;

	public QuickUnionByPathCompression(int size) {
		parent = new int[size];
		rank = new int[size];
		for (int i = 0; i < size; i++) {
			parent[i] = i;
			rank[i] = 1;
		}
	}

	/**
	 * 查询元素p所对应的集合编号
	 * O(h) h为树的高度
	 *
	 * @param p 元素p
	 * @return 元素p所对应的集合编号
	 */
	private int find(int p) {
		if (p < 0 || p >= parent.length) {
			throw new IllegalArgumentException("p is out of bound");
		}
		// p == parent[p] -- p指向自己,此时p为根节点
		while (p != parent[p]) {
      // 路径压缩
			parent[p]=parent[parent[p]];
			p = parent[p];
		}
		return p;
	}

	@Override
	public boolean isConnected(int p, int q) {
		return find(p) == find(q);
	}

	@Override
	public void unionElements(int p, int q) {
		int pRoot = find(p);
		int qRoot = find(q);
		if (qRoot == pRoot) {
			return;
		}
		// 将rank低的集合指向rank高的集合
		if (rank[pRoot] < rank[qRoot]) {
			parent[pRoot] = qRoot;
		} else if (rank[pRoot] > rank[qRoot]) {
			parent[qRoot] = pRoot;
		} else {
			parent[qRoot] = pRoot;
			rank[pRoot] += 1;
		}
	}

	@Override
	public int getSize() {
		return parent.length;
	}
}

基于路径压缩的优化(使用递归方式)

package com.holelin.unionfind;

/**
 * ClassName: QuickUnionByRank
 * 基于路径压缩的优化(使用递归方式)
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/16
 */

public class QuickUnionByPathCompression2 implements UnionFind {
	private int[] parent;
	/**
	 * rank[i] 表示以i为根的集合所表示的树的层数
	 */
	private int[] rank;

	public QuickUnionByPathCompression2(int size) {
		parent = new int[size];
		rank = new int[size];
		for (int i = 0; i < size; i++) {
			parent[i] = i;
			rank[i] = 1;
		}
	}

	/**
	 * 查询元素p所对应的集合编号
	 * O(h) h为树的高度
	 *
	 * @param p 元素p
	 * @return 元素p所对应的集合编号
	 */
	private int find(int p) {
		if (p < 0 || p >= parent.length) {
			throw new IllegalArgumentException("p is out of bound");
		}
		if (p!=parent[p]){
			parent[p]=find(parent[p]);
		}
		return parent[p];
	}

	@Override
	public boolean isConnected(int p, int q) {
		return find(p) == find(q);
	}

	@Override
	public void unionElements(int p, int q) {
		int pRoot = find(p);
		int qRoot = find(q);
		if (qRoot == pRoot) {
			return;
		}
		// 将rank低的集合指向rank高的集合
		if (rank[pRoot] < rank[qRoot]) {
			parent[pRoot] = qRoot;
		} else if (rank[pRoot] > rank[qRoot]) {
			parent[qRoot] = pRoot;
		} else {
			parent[qRoot] = pRoot;
			rank[pRoot] += 1;
		}
	}

	@Override
	public int getSize() {
		return parent.length;
	}
}

基于size的优化

package com.holelin.unionfind;

/**
 * ClassName: QuickUnionBySize
 * 基于size的优化
 * @author HoleLin
 * @version 2.0
 * @date 2019/2/16
 */

public class QuickUnionBySize implements UnionFind {
	private int[] parent;
	/**
	 * sz[i] 表示以i为根的集合中元素个数
	 */
	private int[] sz;

	public QuickUnionBySize(int size) {
		parent = new int[size];
		sz = new int[size];
		for (int i = 0; i < size; i++) {
			parent[i] = i;
			sz[i] = 1;
		}
	}

	/**
	 * 查询元素p所对应的集合编号
	 * O(h) h为树的高度
	 *
	 * @param p 元素p
	 * @return 元素p所对应的集合编号
	 */
	private int find(int p) {
		if (p < 0 || p >= parent.length) {
			throw new IllegalArgumentException("p is out of bound");
		}
		// p == parent[p] -- p指向自己,此时p为根节点
		while (p != parent[p]) {
			p = parent[p];
		}
		return p;
	}

	@Override
	public boolean isConnected(int p, int q) {
		return find(p) == find(q);
	}

	@Override
	public void unionElements(int p, int q) {
		int pRoot = find(p);
		int qRoot = find(q);
		if (qRoot == pRoot) {
			return;
		}
		// 将元素个数较少的集合指向元素个数多的集合
		if (sz[pRoot] < sz[qRoot]) {
			// pRoot的根节点指向qRoot
			parent[pRoot] = qRoot;
			// 将以pRoot为根的树中元素个数加到以qRoot为根的树
			sz[qRoot] += sz[pRoot];

		} else {
			parent[qRoot] = pRoot;
			sz[pRoot] += sz[qRoot];
		}
	}

	@Override
	public int getSize() {
		return parent.length;
	}
}

测试用例

package com.holelin.unionfind;

import java.util.Random;

/**
 * ClassName: UnionFindTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/16
 */

public class UnionFindTest {
	private static double testUF(UnionFind uf, int m) {
		int size = uf.getSize();
		Random random = new Random();
		long startTime = System.nanoTime();

		for (int i = 0; i < m; i++) {
			int a = random.nextInt(size);
			int b = random.nextInt(size);
			uf.unionElements(a, b);
		}
		for (int i = 0; i < m; i++) {
			int a = random.nextInt(size);
			int b = random.nextInt(size);
			uf.isConnected(a, b);
		}
		long endTime = System.nanoTime();
		return (endTime - startTime) / 100000000.0;
	}

	public static void main(String[] args) {
		int size = 10000000;
		int m = 10000000;
//		QuickFind quickFind = new QuickFind(size);
//		System.out.println("QuickFind: "+testUF(quickFind,m)+"s");
		QuickUnionBySize quickUnion = new QuickUnionBySize(size);
		System.out.println("QuickUnionBySize: "+testUF(quickUnion,m)+"s");
		QuickUnionByRank quickUnionByRank= new QuickUnionByRank(size);
		System.out.println("QuickUnionByRank: "+testUF(quickUnionByRank,m)+"s");
		QuickUnionByPathCompression quickUnionByPathCompression= new QuickUnionByPathCompression(size);
		System.out.println("QuickUnionByPathCompression: "+testUF(quickUnionByPathCompression,m)+"s");

		QuickUnionByPathCompression2 quickUnionByPathCompression2= new QuickUnionByPathCompression2(size);
		System.out.println("QuickUnionByPathCompression2: "+testUF(quickUnionByPathCompression2,m)+"s");
	}
}