连通性问题

参考：Robert Sedgewick，《算法：C语言实现》第1章

---

问题描述

　　假设给定整数对的一个序列，其中每个整数表示某类型的一个对象，我们想要说明整数对p-q表示“p连接到q”。假设“连通”关系是可传递的：也就是说如果p和q之间连通，q和r之间连通，那么p和r也是连通的。我们的目标是写一个过滤集合中的无关对的程序。程序的输入为整数对p-q，如果已经看到的数对中并不隐含这p连通到q，那么就输出该对。如果前面输入大数对中隐含着p连通到q，那么程序应该忽略p-q，并应该继续输入下一对。如图1-1给出来一个输入输出示例。

 

 

我们的问题是设计能够记录足够多它所看见的数对信息的程序，并能够判断一个新的数对是否是连通的。非形式地，我们称设计这样一个算法的任务叫做连通性问题。

这里，我们首先假设有N个对象，每个对象都与0～N-1之间大一个整数名对应。

由图论的基本结果可以得出结论：所有N个对象是连通的，当且仅当连通算法输出的数对的个数恰好为N-1个。

努力确定算法的基本操作很重要，这使我们为连通性问题设计的算法可以用于许多类似大问题。确切的说，当我们得到一个新对时，我们必须首先确定它是否表示一个新的连接，然后把已经看到的连接信息合并到已得到的对象的连通关系中，使得它能够检查将要看到的连接。我们把这两个任务封装成“查找”和“合并”两个抽象操作，根据这两个操作很容易求解连通性问题。

在从输入中读取一个新的整数对p-q后，对于数对中的每一个数执行查找操作，如果对的成员在同一个集合中，说明它们是连通的，那么考虑下一对；如果它们不在同一个集合中，则执行合并操作，并输出这个对。

---

1 快速查找算法

开发求解给定问题高效算法大过程中，第一步是实现这个问题的一个简单算法。如果我们需要解决几个容易的特定问题的实例，那么，简单实现就能完成这项工作。如果要用更复杂的算法，简单实现可以用于检查小规模例子的正确性，并成为评估算法性能的一个基准。我们总是关注算法的效率，但我们在开发解决问题的第一个程序时，更关注的是确保程序的正确性。

　　首先考虑如何存储所有输入对，然后写一个遍历这些输入的函数，然后检查下一个数对是否是连通的。我们会选用另外一种方法。首先，实际应用中数对的个数可能很大，不能把它们全部放在内存中。其次，更重要的是，即使我们能够把它们放在内存中，也没有一种简单大方法能够由连接关系集合很快地确定两个对象是否连通。在这里我们首先考虑一种简单大方法，因为它们可以求解难度更小大问题，且这些方法不要求村村所有对，因而是更高效的方法。这些方法利用整数数组，每个整数对应一个对象，用于保存实现合并和查找操作时所需要大必要信息。

　　程序1.1是求解连通性问题大“快速-查找算法”(quick-find algorithm)的一种简单实现。算法的基础是一个整数数组，当且仅当第p个元素值与第q个元素的值相等时，说明p和q是连通的。初始化时，先设置第i个元素的值为i，其中0<=i<=N。为了实现p与q的合并操作，我们遍历数组，把所有取值与p元素值相同的元素值改为q，即表示把新对象q加入到之前p对象所在的组（q作为这个组所有对象的新根节点）。同样，我们也可以选择另一种方式，把所有取值为q的元素值改为p，道理是一样的。

　　这个程序从标准输入读取小于N的非负整数对序列（数对p-q表示“把p所在连通集合中的所有对象连接到对象q”），并且输出还未连通的输入对。程序中使用数组id，每个元素表示一个对象，且具有如下性质，当且仅当p和q是连通的，id[p]=id[q]。为简化起见，定义N为编译时的常数。另一方面，也可以从输入得到它，并动态地分配id数组。

/*
@file   quickfind.c
@brief  利用快速查找算法来解决小规模的连通性问题
*/
#include <stdio.h>
#define N 1000

int main(void)
{
    int i, p, q, t;
    int id[N];
    //初始化对象集合中元素的初始值
    for (i = 0; i < N; i++) id[i] = i;
    //循环读入整数对
    while (scanf("%d-%d", &p, &q) == 2)
    {
        //如果对象p与q是连通的，则从标准输入读取下一对整数对
        if (id[p] == id[q]) continue;
        //如果id[p]与id[q]的值不相等，则说明p-q是新对
        //则将所有原本与id[p]元素值相等的所有元素连接到q
        for (t = id[p], i = 0; i < N; i++)
        {
            if (id[i] == t)
                id[i] = id[q];
        }
        //因为p-q是新对,所以输出这个对
        printf("New pair: %d-%d
", p, q);
    }

    return 0;
}

程序的运行效果如下：

　　可以看出，为了实现查找操作，只需要测试指定数组元素的值是否相等就行，因此称之为快速查找；而合并操作对于每一对输入都需要遍历整个数组元素，因此为慢速合并。

性质1.1 求解N个对象的连通性问题，如果执行M次合并操作，那么快速查找算法至少要执行M*N条指令。

 

2 快速合并算法

 

　　接下来，我们考虑一个快速查找的补算法。它是基于同一个数据结构，即通过对象名引用数组元素，但数组元素表达大含义不同（快速查找中元素值表示的是连接到根节点的索引值），具有更复杂的抽象结构。在一个没有环的结构中，每个对象指向同一个集合中的另一个对象。要确定两个对象是否在同一个集合中，只需要跟随每个对象的指针，直到到达指向自身的一个对象（根节点）。当且仅当这个过程使两个对象到达同一个对象时，这两个对象在同一个集合中。如果两个对象不在同一个集合中，最终一定达到不同的对象（每个对象都指向自身）。为了构造合并操作，我们只需要将一个对象链接到另一个对象以执行合并操作，因此，此算法命名为快速合并(quick-union algorithm)。

　　对于合并-查找操作，使用树的结构是很有用的，因为它可以快速建立，并且具有性质：当且仅当两个对象在输入中是连通时，这两个对象在树中连通。沿着树向上，可以很容易地找到包含每个对象的树的根，于是我们就有了一种查找它们是否连通的方法。每棵树只有一个对象指向它自己，这个对象称为树的根(root)。当我们从树中的任意对象开始，并移到它指向的对象，然后指向那个对象指向的对象，如此反复，最终总会在根节点结束。

　　快速合并算法与快速查找算法的不同之处在于，在快速查找树中，所有的节点只需要一个链接就可以到达根节点；而在快速合并算法中，可能需要经过好几个链接才能够到达根节点。

 

此连通性问题的快速合并算法实现代码如下：

/*
@file   quickfind.c
@brief  利用快速查找算法/快速合并算法来解决小规模的连通性问题
*/
#include <stdio.h>
#define N 1000
//#define USE_QUICK_FIND
#define USE_QUICK_UNION

int main(void)
{
    int i, p, q, t;
    int id[N];
    //初始化对象集合中元素的初始值
    for (i = 0; i < N; i++) id[i] = i;
    //循环读入整数对
    while (scanf("%d-%d", &p, &q) == 2)
    {
    #ifdef USE_QUICK_FIND
        //如果对象p与q是连通的，则从标准输入读取下一对整数对
        if (id[p] == id[q]) continue;
        //如果id[p]与id[q]的值不相等，则说明p-q是新对
        //则将所有原本与id[p]元素值相等的所有元素连接到q
        for (t = id[p], i = 0; i < N; i++)
        {
            if (id[i] == t)
                id[i] = id[q];
        }
    #endif // USE_QUICK_FIND

    #ifdef USE_QUICK_UNION
        //查找p的根节点
        for (i = p; i != id[i]; i = id[i]);
        //查找q的根节点
        for (t = q; t != id[t]; t = id[t]);
        //如果p和q指向同一个根节点，则从标准输入读取下一对整数对
        if (i == t) continue;
        //否则，则让p所在树的根节点指向q，让q作为新树的根节点
        id[i] = t;
    #endif // USE_QUICK_UNION
        //因为p-q是新对,所以输出这个对
        printf("New pair: %d-%d
", p, q);
    }

    return 0;
}

此代码与快速查找算法框架基本相同，只是while循环体内部有所不同而已。

　　我们可以看出，快速合并算法似乎要比快速查找算法要快，因为对于每个输入它并不是总要遍历整个数组。现在，我们可以认为快速合并算法是一种改进，因为它去掉了快速查找算法的主要局限性（对N个对象执行M次合并操作，程序至少需要M*N条指令）。