python - 高效的连接分组算法或python实现

Question

我正在寻找一种有效的连接分组(我不确定这是正确的名称..)算法或 python 实现。

例如，我有这个嵌套列表:

connection_data = [
   ...:     ["A", "B", "C"],
   ...:     ["B", "D"],
   ...:     ["A", "C"],
   ...:     ["E", "F"],
   ...:     ["C", "D"],
   ...:     ]

此数据意味着嵌套列表中的每个列表都显示连接。例如第一个连接["A", "B", "C"]表示A和B和C 彼此有联系。嵌套列表有多个连接信息。

我想从嵌套列表中计算连接分组。例如，当我有上层connection_data时，我想得到

grouped_connection = [
   ...:     ["A", "B", "C", "D"],
   ...:     ["E", "F"],
   ...:     ]

因为A、B、C、D在中的这些连接数据中有连接>connection_data: ["A", "B", "C"], ["B", "D"], ["A", "C"], ["C", "D"]、E 和F 通过["E", "F"] 连接。

总结一下我的问题:

1. 这类问题一般叫什么？
2. 我认为我可以实现许多基于 for 循环的求解器。但是，对于此类问题，python 中是否有任何有效的算法或实现？

Answer 1

Networkx 提供联合查找数据结构的实现 [ 1 ] [ 2 ] 有效地解决了这个问题:

from networkx.utils.union_find import UnionFind

groups = [
    ["A", "B", "C"],
    ["B", "D"],
    ["A", "C"],
    ["E", "F"],
    ["C", "D"],
]

ds = UnionFind()
for gp in groups:
  ds.union(*gp)
for s in ds.to_sets():
  print(s)

# {'B', 'C', 'D', 'A'}
# {'E', 'F'}