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

图 3:读入关系 (a,b) 后并查集状态示意图
合并完成后,并查集状态发生了改变,{a} 和 {b} 合并到了一起,形成新的集合 {a,b},以元素 a 为代表。
同理,读入关系 (a,d) 后,根据将较小集合合并到较大集合中的策略,将集合 {d} 合并到 {a,b},同样以元素 a 为代表,如图 4 所示。

图 4:读入关系 (a,d) 后并查集状态示意图
待所有关系处理完毕,最终形成的并查集结果为 {a,b,c,d}、{e,f} 和 {g,h,i},且全部完成了路径压缩,并查集状态如图 5 所示。

图 5:所有关系处理完毕后并查集状态示意图
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 所示。
图 3:读入关系 (a,b) 后并查集状态示意图
合并完成后,并查集状态发生了改变,{a} 和 {b} 合并到了一起,形成新的集合 {a,b},以元素 a 为代表。
同理,读入关系 (a,d) 后,根据将较小集合合并到较大集合中的策略,将集合 {d} 合并到 {a,b},同样以元素 a 为代表,如图 4 所示。

图 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