朋友圈—并查集应用实例

朋友圈问题是并查集的一类经典应用。人与人之间的朋友关系可以用并查集结构进行表示和处理，利用并查集结构和基本算法，根据已知的朋友关系，可获取诸如朋友圈数量、朋友圈规模等信息，从而可以从中观察出朋友圈分布情况、社交网络中关键联络人情况、朋友圈中消息发布情况等信息，常用于流量统计、舆情控制等领域。

1. 问题描述

我们来看一个关于朋友圈的具体问题，以及如何应用并查集结构和基本算法解决朋友圈相关的问题。为了方便起见，我们沿用“并查及其应用”一节中亲戚关系中设定的模型。

已知有 9 个人（分别用 a,b,c,d,e,f,g,h,i 表示），他们之间的朋友关系如图 1 所示，即好友关系为：(a,b)、(a,d)、(b,d)、(c,d)、(e,f)、(g,i)、(g,h)。

根据上述条件，解决问题：(a,c) 是否在同一个朋友圈，(b,g) 是否在同一个朋友圈。

2. 问题分析

采用并查集算法解决该问题。利用并查集中的三种基本操作，按步骤构造并查集。

1) 初始化每个节点的代表为其本身（后面，把代表叫作“父节点”）

利用 MAKE-SET 操作，将每个元素的父节点设置为其自身，即 a 的父节点为 a，b 的父节点为 b,…，如图 2 所示。

2) 根据给定的好友关系 (a,b)、(a,d)、(b,d)、(c,d)、(e,f)、(g,i)、(g,h) 更新各个元素的父节点

依次读入各好友关系，利用 UNION 操作，将具备好友关系的两个集合进行合并。为了减少需要查找和更新的元素数量，采用将规模较小的集合合并到规模较大的集合之上的策略。例如读入 (a,b)后，首先获取两元素所在集合的代表元素，对比两者是否相等。在此处，两者不相等，将两元素所在的集合进行合并，如图 3 所示。
合并完成后，并查集状态发生了改变，{a} 和 {b} 合并到了一起，形成新的集合 {a,b}，以元素 a 为代表。

同理，读入关系 (a,d) 后，根据将较小集合合并到较大集合中的策略，将集合 {d} 合并到 {a,b}，同样以元素 a 为代表，如图 4 所示。
待所有关系处理完毕，最终形成的并查集结果为 {a,b,c,d}、{e,f} 和 {g,h,i}，且全部完成了路径压缩，并查集状态如图 5 所示。

3) 并查集构造完成后，可以基于并查集结构解决题目中的问题

确认两个人是否在同一个朋友圈问题，即为确认两个元素是否在一个并查集中。利用 FIND-SET(x) 操作查找两个元素所属并查集的代表元素，若两代表元素相等，则两者在同一个集合中，两个人属于同一个朋友圈；否则，两者不在一个集合，两人不属于同一朋友圈。

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
    # 查看两个元素是不是在一个集合里面
    # 通过判断两个元素所在集合的代表元素（父节点）是否相等可获得结果
    def is_same_set(self, a, b):
        return self.find_set(a) == self.find_set(b)
    # 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', 'h', 'i']
    char_set = Union_Find_Set(char)
    # 输入各朋友关系
    char_set.union('a', 'b')
    char_set.union('a', 'd')
    char_set.union('b', 'd')
    char_set.union('c', 'd')
    char_set.union('e', 'f')
    char_set.union('g', 'i')
    char_set.union('g', 'h')
print('a和c是朋友：%s' %char_set.is_same_set('a', 'c')) # True
print('b和g是朋友：%s' %char_set.is_same_set('b', 'g')) # False

运行结果如下：

a和c是朋友：True
b和g是朋友：False