Java 树的构造算法

连通的定义：从A定点出发能到达B定点，则称A-B连通

连通的基本性质：

自反性：A一定连通A（ps:自己可以和自己PY交易）
对称性：如果A和B连通，则B和A也连通（无向的情况下）
传递性：如果A连通B，B连通C，则A连通C

树：

大小（size）：树的节点数量
深度（depth）:某个节点到根节点的链接路径的数量
高度（height）:树所有节点中深度最大的值

森林的构造（目标：深度尽量小，树尽量少）：

quick-find
quick-union
加权quick-union
路径压缩

实现

quick-find算法（所有具有连通关系的触点都指向终触点，查找触点很快，但连通触点较慢）


class UF {
	int[] id;
	int count;

	UF(int N) {
		id = new int[N];
		count = N;
	}
        
        //将所有连通触点指向最后的触点


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

	void union(int p, int q) {
		int pID = find(p);//获取起触点
		int qID = find(q);//获取终触点

		if (pID == qID) {//如果已经连通，结束
			return;
		}
		for (int i = 0; i < id.length; i++) {//遍历所有触点
			if (id[i] == pID) {//如果有触点指向起触点，说明起触点之前已经和其他触点连接
				id[i] = qID; //将所有指向起触点的触点指向终触点
				count--;//连通数量减一
			}
		}
	}

	
	boolean connection(int p, int q) {
		return id[p] == id[q];
	}

	int count() {
		return count;
	}

}

quick-union(所有具有连通关系的触点都指向自己的终触点，连通触点很快，但查找触点较慢)

class UF1 {
	int[] id;
	int count;

	UF1(int N) {
		id = new int[N];
		count = N;
	}

        
        //查找触点的根触点，类似递归回溯
        int find(int p) {
		while(p!=id[p]) p = id[p];
		return id[p];
	}

	void union(int p, int q) {
		int pRoot = find(p);
		int qRoot = find(q);

		if (pRoot == qRoot) {
			return;
		}
		id[pRoot] = qRoot;//直接将新节点指向根节点
	}

	

	boolean connection(int p, int q) {
		return id[p] == id[q];
	}

	int count() {
		return count;
	}

}

加权quick-union(在quick-union的基础上将小树挂在根节点上，而不是挂在子树上，减少了数的深度,最常用)

package chapter1_5;

/**
 * @author : jeasion
 * @name
 * @comment
 * @return
 */
public class WeightQuickUnion {
	int[] id;
	int count;
	int[] size;

	public WeightQuickUnion(int N) {
		id = new int[N];
		size = new int[N];
		count = N;
		for (int i = 0; i < id.length; i++) {
			id[i] = i;
			size[i] = 1;
		}

	}

	void union(int p, int q) {
		int pRoot = find(p);
		int qRoot = find(q);

		if (pRoot == qRoot) {
			return;
		}
        //如果p树的size小于q树的size,说明q树比p树大，则将p树挂到p树上
		if (size[pRoot] <= size[qRoot]) {
	//将p树的根节点qRoot赋给q树的根节点，使q树成为p树根节点的直接子节点
                        id[pRoot] = qRoot;
			size[qRoot] += size[pRoot];
		} else {
			id[qRoot] = pRoot;
			size[qRoot] += size[pRoot];
		}
	}

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

	boolean connection(int p, int q) {
		return id[p] == id[q];
	}

	int count() {
		return count;
	}

}