并查集union_find

动态连通性

问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数p、q可以被理解为“p和q是相连的”。我们假设“相连”是一种等价关系，这也就意味着它具有：

自反性：p和p是相连的。
对称性：如果p和q是相连的，那么q和p也是相连的。
传递性：如果p和q是相连的且q和r是相连的，那么p和r也是相连的。

等价关系能够将对象分为多个等价类。在这里，当且仅当两个对象相连时它们才属于同一个等价类。我们的目标是编写一个程序来过滤掉序列中所有无意义的整数对（两个整数均来自于同一个等价类中）。换句话说，当程序从输入中读取了整数对p和q时，如果已知的所有整数对都不能说明p和q是相连的，那么则将这一对整数写入到输出中。如果已知的数据可以说明p和q是相连的，那么程序应该忽略p、q这对整数并继续处理输入中的下一对整数

quick-find

简介

所有N个数据对应数组id[N]，初始化数组id[i]=i;即第i个数据的所属分量为i;
对于输入的数据对p,q:
先判断是否在同一分量，否的话调用union方法：即将后者的分量内所有数据的分量标识改为前者的分量标识。

UF.java

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class UF
{
	private int[] id;// 分量id
	private int count;// 分量总数

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

	public int count()// 返回分量总数
	{
		return count;
	}

	public boolean connected(int p, int q)// p,q是否在同一分量
	{
		return find(p) == find(q);
	}

	public int find(int p)// p所在分量的标识符
	{
		return id[p];
	}

	public void union(int p, int q)// 连接p,q
	{
		int pId = find(p);
		int qId = find(q);
		for (int i = 0; i < id.length; i++)
		{
			if (id[i] == pId)
			{
				id[i] = qId;
			}
		}
		count--;
	}

	public static void main(String[] args)
	{
		int N = StdIn.readInt();
		UF uf = new UF(N);
		int flag = 0;// 输入计数器
		while (!StdIn.isEmpty())
		{

			int p = StdIn.readInt();
			int q = StdIn.readInt();
			flag++;
			if (uf.connected(p, q))
			{
				continue;
			}
			uf.union(p, q);
			if (flag % 100 == 0)
			{
				System.out.println(flag);
			}
		}
		StdOut.println(N);
		StdOut.println(uf.count() + "components");
	}
}

分析

假设使用本算法解决动态连通性问题并且最后只得到一个连通分量，
那么一共要调用N-1次union()操作。每次connected()会调用两次find(),
每次find()调用要访问一次数组，而归并两个分量的union()操作会调用两次find()
所以该情况下至少要进行(2+2+N-1)*(N-1)~N^2次数组访问。

显然该算法在largeUF.txt(100万级别的输入)条件下运行时间过长。

quick-union

简介

每个触点所对应的id[]元素都是同一个分量中的另一个触点的名称（也可能是它自己）
所有N个数据对应数组id[N]，初始化数组id[i]=i;即第i个数据的所属分量为i;
对于输入的数据对p,q:
先判断是否在同一分量，否的话调用union方法：即跟随链接到达各自的根触点，
然后将一个根触点链接到另一根触点即实现一个分量重命名为另一个分量。

代码

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class UF
{
	private int[] id;// 分量id
	private int count;// 分量总数

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

	public int count()// 返回分量总数
	{
		return count;
	}

	public boolean connected(int p, int q)// p,q是否在同一分量
	{
		return find(p) == find(q);
	}

	public int find(int p)// p所在分量的标识符
	{
		while(p != id[p])
		{
			p = id[p];
		}
		return p;
	}

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

	public static void main(String[] args)
	{
		int N = StdIn.readInt();
		UF uf = new UF(N);
		int flag = 0;// 输入计数器
		while (!StdIn.isEmpty())
		{

			int p = StdIn.readInt();
			int q = StdIn.readInt();
			flag++;
			if (uf.connected(p, q))
			{
				continue;
			}
			uf.union(p, q);
			if (flag % 100 == 0)
			{
				System.out.println(flag);
			}
		}
		StdOut.println(N);
		StdOut.println(uf.count() + "components");
	}
}

分析

find()方法访问数组的次数是给定触点在树中深度的两倍再加1，
union()和connected()访问数组的次数分别为两次find()+1和两次find()操作。
假设使用本算法解决动态连通性问题并且最后只得到一个连通分量，对于最底层数与root数用union()
进行的数组访问次数为2N+1+2,因此处理整个N对数据所需的访问数组次数为2(1+2+…+N)~N^2。

加权quick-union

简介

在quick-union的基础上，更改union方法，使得每次将较小的树连接在较大树的根节点上
以此减少整棵树的高度，故而减少数组访问次数

代码

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class UF
{
	private int[] id;// 分量id
	private int[] sz;// 各节点所对应分量的大小
	private int count;// 分量总数

	public UF(int N)
	{
		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)// p,q是否在同一分量
	{
		return find(p) == find(q);
	}

	public int find(int p)// p所在分量的标识符
	{
		while (p != id[p])
		{
			p = id[p];
		}
		return p;
	}

	public void union(int p, int q)// 连接p,q
	{
		int i = find(p);
		int j = find(q);
		if (sz[i] < sz[j])
		{
			id[i] = j;
			sz[j] += sz[i];
		} else
		{
			id[j] = i;
			sz[i] += sz[j];
		}
		count--;
	}

	public static void main(String[] args)
	{
		int N = StdIn.readInt();
		UF uf = new UF(N);
		int flag = 0;// 输入计数器
		while (!StdIn.isEmpty())
		{

			int p = StdIn.readInt();
			int q = StdIn.readInt();
			flag++;
			if (uf.connected(p, q))
			{
				continue;
			}
			uf.union(p, q);
			if (flag % 100 == 0)
			{
				System.out.println(flag);
			}
		}
		StdOut.println(N);
		StdOut.println(uf.count() + "components");
	}
}

分析

加权quick-union算法在处理N个触点和M条连接时最多访问数组cMlgN次，c为常数。