集合联合查找算法

问题内容：

我有成千上万的1到100个数字的行，每行定义一组数字以及它们之间的关系。我需要获取相关数字集。

小例子：如果我有这7行数据

T1 T2
T3 
T4
T5
T6 T1
T5 T4
T3 T4 T7

我需要一个不太慢的算法来知道这里的设置是：

T1 T2 T6 (because T1 is related with T2 in the first line and T1 related with T6 in the line 5)
T3 T4 T5 T7 (because T5 is with T4 in line 6 and T3 is with T4 and T7 in line 7)

但是当您有非常大的集合时，很难在每个大集合中搜索T（x）并进行集合的并集…等等。

您是否有暗示以不太暴力的方式执行此操作？

我正在尝试在Python中执行此操作。

问题答案：

一旦建立了数据结构，您想对它执行什么查询？向我们展示您现有的代码。什么是T（x）？您说的是“数字组”，但样本数据显示了T1，T2等。请解释。

您是否已阅读以下内容：http :
//en.wikipedia.org/wiki/Disjoint-
set_data_structure

尝试查看以下Python实现：http : //code.activestate.com/recipes/215912-union-find-data-
structure/

或者您可以自己抨击一些简单易懂的事情，例如

[更新：全新代码]

class DisjointSet(object):

    def __init__(self):
        self.leader = {} # maps a member to the group's leader
        self.group = {} # maps a group leader to the group (which is a set)

    def add(self, a, b):
        leadera = self.leader.get(a)
        leaderb = self.leader.get(b)
        if leadera is not None:
            if leaderb is not None:
                if leadera == leaderb: return # nothing to do
                groupa = self.group[leadera]
                groupb = self.group[leaderb]
                if len(groupa) < len(groupb):
                    a, leadera, groupa, b, leaderb, groupb = b, leaderb, groupb, a, leadera, groupa
                groupa |= groupb
                del self.group[leaderb]
                for k in groupb:
                    self.leader[k] = leadera
            else:
                self.group[leadera].add(b)
                self.leader[b] = leadera
        else:
            if leaderb is not None:
                self.group[leaderb].add(a)
                self.leader[a] = leaderb
            else:
                self.leader[a] = self.leader[b] = a
                self.group[a] = set([a, b])

data = """T1 T2
T3 T4
T5 T1
T3 T6
T7 T8
T3 T7
T9 TA
T1 T9"""
# data is chosen to demonstrate each of 5 paths in the code
from pprint import pprint as pp
ds = DisjointSet()
for line in data.splitlines():
    x, y = line.split()
    ds.add(x, y)
    print
    print x, y
    pp(ds.leader)
    pp(ds.group)

这是最后一步的输出：

T1 T9
{'T1': 'T1',
 'T2': 'T1',
 'T3': 'T3',
 'T4': 'T3',
 'T5': 'T1',
 'T6': 'T3',
 'T7': 'T3',
 'T8': 'T3',
 'T9': 'T1',
 'TA': 'T1'}
{'T1': set(['T1', 'T2', 'T5', 'T9', 'TA']),
 'T3': set(['T3', 'T4', 'T6', 'T7', 'T8'])}

集合联合查找算法

微信关注