如何合并具有交集的集合(连通分量算法)?

本文介绍了如何合并具有交集的集合(连通分量算法)?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

是否有任何有效的方法来合并具有交集的集合.例如:

Is there any effective way to merge sets which have intersections. For example:

l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}]

预期结果是:

r = [{1, 2, 3}, {4, 5, 6, 7}, {8, 9}]

应该合并所有有交集(公共组件)的集合.例如:

All sets which have intersection (common components) should be merged. For example:

{1, 3} & {2, 3} # {3}

所以这两个集合应该合并:

So these two sets should be merged:

{1, 3} | {2, 3} # {1, 2, 3}

很遗憾，我没有任何可行的解决方案.

Unfortunately I don't have any working solution.

更新:结果中集合的顺序并不重要.

UPDATE: The order of sets in the result is not important.

推荐答案

实现 连接组件算法 是将集合列表转换为一组可散列的冻结集，以便在您遍历它并找到与当前集合相交的冻结集时，您可以轻松地将其从池中移除:

An efficient way to implement the connected components algorithm as mentioned by @mkrieger1 in the comments is to convert the list of sets to a set of hashable frozensets so that as you iterate through it and find a frozenset that intersects with the current one you can easily remove it from the pool:

pool = set(map(frozenset, l)) groups = [] while pool: groups.append(set(pool.pop())) while True: for candidate in pool: if groups[-1] & candidate: groups[-1] |= candidate pool.remove(candidate) break else: break

给定 l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}], groups 会变成:

[{1, 2, 3}, {4, 5, 6, 7}, {8, 9}]

并且给定 l = [{1, 2}, {3, 4}, {2, 3}]，groups 将变为:

And given l = [{1, 2}, {3, 4}, {2, 3}], groups will become:

[{1, 2, 3, 4}]

并且给定 l = [{1}, {2}, {1, 2}]，groups 将变为:

And given l = [{1}, {2}, {1, 2}], groups will become:

[{1, 2}]