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

标签 python set graph-theory

<分区>

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

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

预期的结果是:

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

应合并所有具有交集(公共(public)组件)的集合。例如:

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

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

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

很遗憾,我没有任何可行的解决方案。

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

最佳答案

实现 connected components algorithm 的有效方法正如 @mkrieger1 在评论中提到的那样,将集合列表转换为一组可散列的卡住集,以便在您遍历它并找到与当前卡住集相交的卡住集时,您可以轻松地将其从池中删除:

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 将变为:

[{1, 2, 3, 4}]

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

[{1, 2}]

关于python - 如何合并具有交集的集合(连通分量算法)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54673308/

相关文章:

python - for 循环内的 dataframe.replace()

python - 如何创建通过迭代运行的累积代码?

python - 多个鼠标指针?

java - TreeSet 只加一个值?

c#属性获取,设置不同类型

arrays - 如何确定数组中的所有对象是否在 Swift 中连接

python - 运行我自制的旋转算法时得到不正确的图片输出

python - 为什么在 python 中从列表中创建一个 freezeset 会转换列表?

graph-theory - ArangoDB AQL 中的不相交子图

algorithm - 计算DFS算法的时间复杂度