Union-Find 算法

问题描述

问题的输入是一对整数对，其中每个整数都表示某种类型的对象，一对整数 p q 可以被理解为「p 和 q 是相连的」，我们假设「相连」是一种等价关系，那么有：

• 自反性：p 和 p 相连
• 对称性：p 和 q 相连，q 和 p 也相连
• 传递性：p 和 q 相连且 q 和 r 相连，那么 p 和 r 也相连

显而易见这是「等价关系」的三条性质，我们通过「等价关系」可以将集合划分成多个「等价类」。在这里，我们定义同一等价类当中的任意两个数均是相连的。

我们的目标是过滤掉一个序列当中所有「相连」的整数对。换句话说，当我输入一个整数对 p 和 q ，如果 p q 相连，那么程序自动跳过并处理下一对整数对，如果二者不相连，那么程序应当输出这对整数对

在这里，为了便于讨论，我们将对象称为触点，将整数对称为连接，将各个等价类称为连通分量，除此之外，我们用 \(0\) 到 \(N-1\) 的整数来表示 \(N\) 个触点

​

算法接口

我们设计如下的接口：

class UF
{
public:
	UF(int N);//用整数表示N个触点
	void Union(int p, int q);//在p和q之间添加一条连接
	int find(int p);//p所在连通分量的标识符
	bool connected(int p, int q);//如果p和q是连通的返回true
	int Count();//连通分量的数量
    //一开始我们有N个分量，将两个分量归并的Union操作会使总连通分量数减一
};

由于每个触点和分量都会用 int 类型来表示，那么在底层设计中，我们维护一个「以触点为索引」的 id[] 数组，来表示所有的连通分量。我们使用连通分量当中某个触点的名称来表示整个连通分量，因此只要部分触点属于同一个连通分量，那么它们对应的元素值（id[i]）都会相同。

一开始，我们有 \(N\) 个触点，每个触点都单独表示了一个分量。由于 id 数组的值会用来表示连通分量，为避免冲突，我们将 id[i] 的值初始化成 i 。我们使用 find 方法来判断触点（也就是数组索引）属于哪一个连通分量（也就是索引对应的值）。

基于 find 接口的声明，我们很容易得到 connected 方法的实现，它只有一条语句：find(p) == find(q) ，并返回一个 bool 值

除此之外，我们还需要维护一个变量 count 来表示当前的连通分量个数

到此为止，我们给出如下实现：

class UF
{
private:
	vector<int>id;
	int count;
public:
	UF(int N)//用整数表示N个触点
	{
		count = N;
		id.assign(N, 0);
		for (int i = 0; i < N; i++)
			id[i] = i;
	}
	bool connected(int p, int q)//如果p和q是连通的返回true
	{
		return find(p) == find(q);
	}
	int Count()//连通分量的数量
	{
		return count;
	}
	void Union(int p, int q);//在p和q之间添加一条连接
	int find(int p);//p所在连通分量的标识符
};

我们分析的重点将放在 Union 和 find 的实现上面

​

Union 和 find 的实现

quick-find 实现

根据连通的定义，我们很容易想到：当 id[p] 与 id[q] 相等时，我们说 p 和 q 是连通的。也就是说，在同一个连通分量当中，所有的 id[i] 全部都相同。在 find 的实现部分，只要 id[p] 与 id[q] 的值相等，那么便可以返回 true 。在 Union 的实现部分，我们首先需要检查二者是否处于同一个连通分量，如果是则不需要做任何动作，否则我们需要将二者的值统一。为此，我们需要遍历整个数组，让 id[q] 的值全部变为 id[p] 的值

void Union(int p, int q)//在p和q之间添加一条连接
{
    int pID = find(p);
    int qID = find(q);
    if (pID == qID)
        return;
    for (int i = 0; i < id.size(); i++)
        if (id[i] == pID)
            id[i] = qID;
    count--;//不要忘了将连通分量减一
}
int find(int p)//p所在连通分量的标识符
{
    return id[p];
}

​

quick-find 算法分析

在此，我们统计的是访问数组的次数，即读取数组与向数组写入我们都认为是访问数组

在 find 算法实现中，我们访问数组的次数是一次

在 connected 算法实现中，我们需要调用两次 find 函数

在 Union 算法实现中，我们至少需要调用两次 find 函数。在数组读取的部分，我们需要读取 \(N\) 次来进行 if 的判断；在写入数组的部分，在最坏的情况下，我们需要写入 \(N-1\) 次，最好的情况下是写入一次。

因此，在当前 Union 的实现中，我们需要访问的次数为 \(N+3\) 到 \(2N+1\)

我们考虑一个极端的情况，我们一开始输入了 \(N\) 个点，也就是 \(N\) 个连通分量，假设我们调用 \(N-1\) 次 Union 函数来使得只存在一个连通分量的时候，这时最少的访问次数为 \((N-1)(N+3) \sim N^2\) （在这里，我们使用 \(\sim\) 来表述等价）

这个时间复杂度是平方级别的，显然，我们需要去优化一下这个算法

​

quick-Union 算法

我们采取使用 quick-find 相同的数据结构——以触点作为数组索引，但我们对 id[i] 的值赋予不同的意义。具体来说，我们让 id[i] 的值表示同一连通分量当中某个触点的名称（也就是索引），当然，这个值也可以是自己本身。我们称这种联系为链接

在 find 的实现中，我们从给定触点开始，通过链接找到下一个触点，不断将这个过程进行下去，最后我们一定能够找到一个指向自己的触点，即链接指向自己的触点（我们称之为根节点）。我们可以证明，这样的点必然存在

在 Union 的实现中，我们获取到 p 和 q 的根节点的数值，我们让 p 的根节点数值等于 q 的根节点的数值，这样便实现了 p 与 q 的连通

在我们初始化时，对于每个触点的值都是它本身的名称，也就是说每个触点的链接都指向自己（即每个节点都是根节点）。那么对于一个根节点而言，在执行 Union 前后它都具有此性质，因此我们说这种点必然存在

void Union(int p, int q)//在p和q之间添加一条连接
{
    int pID = find(p);
    int qID = find(q);
    if (pID == qID)
        return;
    id[pID] = qID;
    count--;
}
int find(int p)//p所在连通分量的标识符
{
    while (p != id[p])
        p = id[p];
    return p;
}

​

quick-Union 算法分析

我们给出如下定义：

一棵树的大小是其节点的数量，节点的深度是它到根节点路径上的链接数，数的高度为所有节点当中的最大深度

在 find 算法的实现中，数值读取次数为给定触点的深度加一（最后还需要访问一次来退出循环），写入次数为给定触点的深度

在 Union 算法的实现中，只有两次调用 find 函数的成本（如果两个触点不在同一个连通分量还需要加一）

在这里，我们再次考虑一个极端情况，输入数对为：0-1、0-2、0-3 等（即 0 链接到 1，1 链接到 2，如此这般），执行 \(N-1\) 次 Union 后我们将会得到一个连通分量，我们先在来分析这个过程当中数值的访问次数

一般地，对于数对 \(0-i\) ，触点 0 的深度为 \(i-1\) ，触点 \(i\) 的深度为 0 ，那么执行一次 Union 函数的数组访问次数为 \(2N+1\) （\(find(0)=2(i-1)+1=2i-1\)，\(find(i)=2*0+1=1\)，\(Union(i,0)=(2i-1)+1+1=2i+1\)）

\(N-1\) 次 Union 函数后，数组访问次数为：\(3+5+8+\cdots+(2N-1) \sim N^2\)

​

加权 quick-Union 算法

刚刚的连通过程我们可以认为是将两棵树的根节点之间相连，而算法的时间复杂度部分主要取决于树的高度。因此，如果我们将大树的根节点链接到小树上面，整棵树的高度必然会增加，但如果反过来则不一定

因此，我们可以用另外一个数组来记录每个连通分量的大小，我们总让小树的根节点链接到大树的根节点上，这样便可以降低时间复杂度

class UF
{
private:
	vector<int>id;
	vector<int>sz;
	int count;
public:
	UF(int N)//用整数表示N个触点
	{
		count = N;
		id.assign(N, 0);
		sz.assign(N, 1);
		for (int i = 0; i < N; i++)
			id[i] = i;
	}
	bool connected(int p, int q)//如果p和q是连通的返回true
	{
		return find(p) == find(q);
	}
	int Count()//连通分量的数量
	{
		return count;
	}
	void Union(int p, int q)//在p和q之间添加一条连接
	{
		int pID = find(p);
		int qID = find(q);
		if (pID == qID)
			return;
		if (sz[pID] > sz[qID])
		{
			id[qID] = pID;
			sz[pID] += sz[qID];
		}
		else
		{
			id[pID] = id[qID];
			sz[qID] += sz[pID];
		}
		count--;
	}
	int find(int p)//p所在连通分量的标识符
	{
		while (p != id[p])
			p = id[p];
		return p;
	}
};

关于这个算法的时间复杂度，书中只是说，Union 是 \(logN\) ，find 是 \(logN\)

​

最后

有一说一，这本书讲的实在是太好了，我是昨天晚上十点多开始看的，他一开始抛出了一个算法，然后再一步一步引领我去思考如何去优化这个算法，整个过程十分的顺畅。昨天一上头，看到了一点半，哈哈哈