问题

问题的输入是一列整数对，每个整数都表示一种类型的对象，一对整数p，q可以理解为‘p和q是相连的’，现需要设计一个数据结构来保存程序中已知的所有整数对，并且用它们来判断一对新对象是否相连的

quick-find算法

	/**
	 * 
	 * @author zzk
	 *
	 */
	public class UF {
		
		private int[] id; // 分量id
		
		private int count;// 分量数量
		
		public UF(int N) {
			//初始化分量id
			count = N;
			id = new int[N];
			for(int i = 0; i < N; i++) {
				id[i] = i;
			}
		}
		public int count() {
			return count;
		}
		/**
		 * 判断两个分量是否相等，也就是相连
		 * @param p
		 * @param q
		 * @return
		 */
		public boolean connected(int p, int q) {
			return find(p) == find(q);
		}
		/**
		 * 查找分量
		 * @param p
		 * @return
		 */
		public int find(int p) {
			return id[p];
		}
		/**
		 * 合并分量
		 * @param p
		 * @param q
		 */
		public void union(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;
				}
			}
			count --;
		}
	}

分析

• 每次find()调用只需要访问数组一次，而归并两个分量的union()操作访问数组的次数在(N + 3)到(2N + 1)之间。

• 假设最后只得到了一个连通分量，那么这至少需要调用N - 1次union()，即至少(N + 3)(N - 1) ~ N ^ 2次数组访问。

• quick-find算法是平方级别的。

quick-union算法

	/**
	 * 
	 * @author zzk
	 *
	 */
	public class UF_union {
		
		private int[] id;  //分量id
		
		private int count; //分量数量
		
		public UF_union(int N) {
			//初始化分量id
			idCount = 0;
			count = N;
			id = new int[N];
			for(int i = 0; i < N; i++) {
				id[i] = i;
			}
		}
		public int count() {
			return count;
		}
		/**
		 * 判断两个分量是否相等，也就是相连
		 * @param p
		 * @param q
		 * @return
		 */
		public boolean connected(int p, int q) {
			return find(p) == find(q);
		}
		/**
		 * 查找分量
		 * 换成查找p的根节点
		 * @param p
		 * @return
		 */
		public int find(int p) {
			idCount++;
			while(p != id[p]) {
				p = id[p];
			}
			return p;
		}
		/**
		 * 合并分量
		 * 统一根节点的值
		 * @param p
		 * @param q
		 */
		public void union(int p, int q) {
			//将p和q的根节点统一
			int pRoot = find(p);
			int qRoot = find(q);
			
			if(pRoot == qRoot) {
				return;
			}
			id[pRoot] = qRoot;
			count --;
		}
		public int getIdCount() {
			return idCount;
		}
	}

分析

• 最佳情况的输入，用例的运行时间是线性级别
• 最坏情况的输入，用例的运行时间是平方级别的

加权quick-union算法

	/**
	 * 对UF_union进行改进
	 * 加权quick_union的算法
	 * @author zzk
	 *
	 */
	public class WeightedQuickUnionUF {
		private int[] id;		//父链接数组(由触点索引)
		private int[] sz;		//(由触点索引的)各个根节点所对应的分量的大小
		private int count;		//连接分量的数量
		private int idCount;	//访问id数组次数
		public WeightedQuickUnionUF(int N) {
			idCount = 0;
			count = N;
			id = new int[N];
			for(int i = 0; i < N; i++) {
				id[i] = i;
			}
			sz = new int[N];
			for(int i = 0; i < N; i++) {
				sz[i] = 1;
			}
		}
		public int count() {
			return count;
		}
		
		public boolean connected(int p, int q) {
			return find(p) == find(q);
		}
		//跟随连接找到根节点
		public int find(int p) {
			idCount++;
			while(p != id[p]) {
				p = id[p];
			}
			return p;
		}
		//连接
		public void union(int p, int q) {
			int i = find(p);
			int j = find(q);
			if(i == j) {
				return;
			}
			//将小树的根节点连接到大树的节点
			if(sz[i] < sz[j]) {
				idCount++;
				id[i] = j;
				sz[j] += sz[i];
			}else {
				idCount++;
				id[j] = i;
				sz[i] += sz[j];
			}
			count --;
		}
		public int getIdCount() {
			return idCount;
		}
		
	}

分析

• 记录每一棵树的大小并总是将较小的树连接到较大的树上。
• 加权quick-union算法是对数级别的。