算法(4th ed)(199):基础——案例研究:union-find 算法 7.1

阅读数:21 2019 年 11 月 9 日 15:51

算法(4th ed)(199):基础——案例研究:union-find 算法 7.1

(动态连通性)

首先我们详细地说明一下问题:问题的输入是一列整数对,其中每个整数都表示一个某种类型的对象,一对整数 p q 可以被理解为“pq 是相连的”。我们假设“相连”是一种等价关系,这也就意味着它具有:

  • 自反性pp 是相连的;
  • 对称性:如果pq 是相连的,那么qp 也是相连的;
  • 传递性:如果 pq 是相连的且 qr 是相连的,那么 pr 也是相连的。

等价关系能够将对象分为多个等价类。在这里,当且仅当两个对象相连时它们才属于同一个等价类。我们的目标是编写一个程序来过滤掉序列中所有无意义的整数对(两个整数均来自于同一个等价类中)。换句话说,当程序从输入中读取了整数对 p q 时,如果已知的所有整数对都不能说明 pq 是相连的,那么则将这一对整数写入到输出中。如果已知的数据可以说明pq 是相连的,那么程序应该忽略 p q 这对整数并继续处理输入中的下一对整数。图 1.5.1 用一个例子说明了这个过程。为了达到所期望的效果,我们需要设计一个数据结构来保存程序已知的所有整数对的足够多的信息,并用它们来判断一对新对象是否是相连的。我们将这个问题通俗地叫做动态连通性问题。这个问题可能有以下应用。

算法(4th ed)(199):基础——案例研究:union-find 算法 7.1

图 1.5.1 动态连通性问题

评论

发布