连通子图—并查集应用实例

查找识别图的子元素（连通子图）是图算法中常用的操作，在现实中有广泛的应用，如欧拉提出的哥尼斯堡七桥问题，或者判断不同地理区域的连通性问题等，实质上都是确定图的子元素的问题。

1. 问题描述

某公司中标了一个扶持贫困山区的道路畅通工程，需要把该地区附近未通车区域的道路进行铺设拓宽，打通整个地区的所有区域，使该地区各村庄之间彻底实现通车。

假设该地区的村庄数为 N，可通车道路数为 M，道路均为双向通车道路。该公司前期在做成本估算时，需要勘察整个区域，根据各个区域的道路连接情况确定需要铺设道路的数量。

给定 N 的取值为 7，分别用 A、B、C、D、E、F 和 G 表示该地区的 7 个村庄；M 取值为 3，具有可通车道路的村庄为 (A,C)、(C,E) 和 (D,F)，采用并查集结构求解该公司最少需要铺设的道路的数量。

2. 问题分析

该问题要求解连通任意两村庄所需铺设道路的最少条数，实质上是一个求解无向图的连通子图问题。该图以村庄为节点，以村庄之间的道路为边组成，最终求解的问题是要获取该图的连通子图个数。

若整个图为一个连通子图，即所有节点之间均相互可达，则表示各个村庄之间已经实现相互通车，此时不需要新修道路；若整个图由两个连通子图构成，则表示此区域中有两块子区域之间相互不能通车，此时需要在这两个子区域中修建一条道路即可打通所有村庄之间的通车道路。

以此类推，可以归纳出，若图中有n(n≥1)个连通子图，则至少需要构建n-1条道路，可以实现整个区域的通车。

根据以上分析，首先构建并查集。

1) 在初始阶段，通过 MAKE-SET 操作，将每个元素分别构造为一个集合，并查集状态如图 1 所示。
2) 读入第一条边 (A,C) 之后，将元素 C 所在的集合合并到元素 A 所在的集合中，以 A 为新集合的代表，并查集状态如图 2 所示。
3) 读入第二条边 (C,E) 之后，将元素 E 所在的集合合并到集合 {A,C} 中，以 A 为新集合的代表，并查集状态如图 3 所示。
4) 读入第三条边 (D,F) 之后，将元素 F 所在的集合合并到元素 D 所在的集合中，以 D 为新集合的代表，并查集状态如图 4 所示。
至此，并查集结构构造完毕。

基于并查集状态信息，我们可以计算目前该图中的连通子图个数。

分析构建过程可知，在初始阶段，该图中的每个节点相互独立，此时图的连通子图个数即为图中节点数。每次新录入一条边，若此次新边的读入导致了 UNION 过程的发生，即可看作完成了两个独立的连通子图之间的连接，对应该状态的图中连通子图就应该减少一个。

从上文中 UNION 过程的实现中我们知道，每次 UNION 操作，规模较小的集合的代表对应的 sizeList 值均会重置为 0，表示该节点不再是集合的代表。对应的，sizeList 值不为 0 的元素，仍为某集合的代表，可以标识一个连通子图。

因此，根据并查集构造完成时对应的 sizeList 值，可以确定连通子图的数量。获得连通子图数量 n 后，需要修路的数目即为 n-1。

3. 代码

图的子元素的代码如下：

class Union_Find_Set(object):
    # 初始化
    def __init__(self, input):
        # 初始化两个列表
        self.fatherList = {} # 保存元素所属集合的代表元素
        self.sizeList = {} # 保存集合的元素个数
        for x in input:
            self.make_set(x)
    # MAKE-SET操作
    # 将节点的父节点设为自身，size设为1
    def make_set(self, x):
        self.fatherList[x] = x
        self.sizeList[x] = 1
    # FIND-SET操作
    # 采用递归的策略定位父节点
    # 在父节点查找过程中，将当前节点连接到父节点上，进行路径压缩
    def find_set(self, x):
        father = self.fatherList[x]
        if(x != father): # 递归定位父节点
            father = self.find_set(father)
        self.fatherList[x] = father # 路径压缩
        return father
    # 根据sizeList取值计算图的子图个数
    # 通过累加sizeList的中取值大于0的元素数量可获得图的子图个数
    def get_component_count(self):
        count = 0
        for x in self.sizeList:
            if(self.sizeList[x] > 0):
                count += 1
        return count
    # UNION操作
    # 将a和b两个集合合并在一起
    def union(self, a, b):
        if a is None or b is None:
            return
        a_father = self.find_set(a) # 获取两元素所在集合的代表元素
        b_father = self.find_set(b)
        if(a_father != b_father):
            a_size = self.sizeList[a_father] # 获取两元素所在集合的大小
            b_size = self.sizeList[b_father]
        if(a_size >= b_size): # 将规模较小的集合合并到规模较大的集合下面
            self.fatherList[b_father] = a_father
            self.sizeList[a_father] = a_size + b_size
            self.sizeList[b_father] = 0
        else:
            self.fatherList[a_father] = b_father
            self.sizeList[b_father] = a_size + b_size
            self.sizeList[a_father] = 0
if __name__ == '__main__':
    # 输入各元素
    char = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
    char_set = Union_Find_Set(char)
    # 输入各朋友关系
    char_set.union('A', 'C')
    char_set.union('C', 'E')
    char_set.union('D', 'F')
print('需要修%d条路' %(char_set.get_component_count()-1))

运行结果如下：

需要修3条路