在填写组件时,在每个阶段都需要考虑三种情况(因为您 匹配重叠的组):
我们可以使用内置的set
帮助。 (请参阅@jwpat和@DSM的更复杂的示例) :
def connected_components(lst):
components = [] # list of sets
for (x,y) in lst:
i = j = set_i = set_j = None
for k, c in enumerate(components):
if x in c:
i, set_i = k, c
if y in c:
j, set_j = k, c
#case1 (or already in same set)
if i == j:
if i == None:
components.append(set([x,y]))
continue
#case2
if i != None and j != None:
components = [components[k] for k in range(len(components)) if k!=i and k!=j]
components.append(set_i | set_j)
continue
#case3
if j != None:
components[j].add(x)
if i != None:
components[i].add(y)
return components
lst = [(1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2)]
connected_components(lst)
# [set([8, 1, 2, 3, 4]), set([5, 6, 7])]
map(list, connected_components(lst))
# [[8, 1, 2, 3, 4], [5, 6, 7]]
connected_components([(1, 2), (4, 3), (2, 3), (5, 6), (6, 7), (8, 2)])
# [set([8, 1, 2, 3, 4]), set([5, 6, 7])] # @jwpat's example
connected_components([[1, 3], [2, 4], [3, 4]]
# [set([1, 2, 3, 4])] # @DSM's example
这当然不是最有效的方法,但是可能与他们期望的方法类似。 正如乔恩·克莱门茨(Jon Clements)所指出的那样,有一个用于这些类型的计算的库: networkx,在该库中它们会更加高效。