首页 > Python算法 > 并查集算法 阅读数:40

朋友圈—并查集应用实例

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

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)。
图算法解决查找亲戚关系示意图
图 1:图算法解决查找亲戚关系示意图

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

2. 问题分析

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

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

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

图 2:初始化后并查集状态示意图

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

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

合并完成后,并查集状态发生了改变,{a} 和 {b} 合并到了一起,形成新的集合 {a,b},以元素 a 为代表。

同理,读入关系 (a,d) 后,根据将较小集合合并到较大集合中的策略,将集合 {d} 合并到 {a,b},同样以元素 a 为代表,如图 4 所示。
读入关系(a,d)后并查集状态示意图
图 4:读入关系 (a,d) 后并查集状态示意图

待所有关系处理完毕,最终形成的并查集结果为 {a,b,c,d}、{e,f} 和 {g,h,i},且全部完成了路径压缩,并查集状态如图 5 所示。
所有关系处理完毕后并查集状态示意图
图 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