从集合中找到不连通图的算法

Question

目标: 希望从大量集合中高效地找到所有的不连通图形

例如， 我有一个如下所示的数据文件:

A, B, C
C, D, E
A, F, Z
G, J
...

每个条目代表一组元素。 第一项 A，B，C = {A，B，C} 这也表明 A 和 B，A 和 C，B 和 C 之间有边。

我最初想到的算法如下：

1.parse all the entries into a list:
[
{A,B,C}
{C,D,E}
...
]
2.start with the first element/set of the list can called start_entry, {A,B,C} in this case
3.traverse other element in the list and do the following:
     if the intersection of the element and start_entry is not empty
          start_entry = start_entry union with the element
          remove element from the list
4.with the updated start_entry, traverse the list again until there is not new update

上述算法应该返回一个连通图的顶点列表。然而，由于数据集大小的问题，我遇到了运行时问题。数据集包含大约100000个条目。

因此，我想知道是否有更有效的方法来查找连通图。

数据结构也可以改为以下形式（如果更容易）

A,B
B,C
E,F
...

每个条目表示图的一条边。

- Junwei su

Answer 1

这似乎是使用不相交集数据结构的理想情况。

这可以让您在几乎线性的时间内将集合合并在一起。

示例Python代码

from collections import defaultdict

data=["A","B","C"],["C","D","E"],["F","G"]

# Prepare mapping from data element to index
S = {}
for a in data:
    for x in a:
        if x not in S:
            S[x] = len(S)

N = len(S)
rank=[0]*N
parent=range(N)

def Find(x):
    """Find representative of connected component"""
    if  parent[x] != x:
        parent[x] = Find(parent[x])
    return parent[x]

def Union(x,y):
    """Merge sets containing elements x and y"""
    x = Find(x)
    y = Find(y)
    if x == y:
        return
    if rank[x]<rank[y]:
        parent[x] = y
    elif rank[x]>rank[y]:
        parent[y] = x
    else:
        parent[y] = x
        rank[x] += 1

# Merge all sets
for a in data:
    x = a[0]
    for y in a[1:]:
        Union(S[x],S[y])

# Report disconnected graphs
V=defaultdict(list)
for x in S:
    V[Find(S[x])].append(x)

print V.values()

打印

[['A', 'C', 'B', 'E', 'D'], ['G', 'F']]

- Peter de Rivaz

---

可能更简单的方法是使用深度优先搜索或广度优先搜索。 - user2357112

虽然我经常在Python中尝试DFS或BFS时遇到堆栈溢出，但我仍然会将代码转换为非递归形式。 - Peter de Rivaz

话说，真要夸一下你使用了一个合适的带路径压缩和按秩合并的不相交集合森林，而不是那些经常出现的无法工作的“set”和“union”等东西。 - user2357112

我认为在最后构建连通组件时，您可能想要使用Find(S[x])而不是parent[S[x]]。 - user2357112

Answer 2

使用 networkx 模块，该模块专门设计用于高效处理图形：

import networkx as nx
sets = [{'A','B','C'}, {'C','D','E'}, {'F','G','H'}, ...]

创建一个图形并向其中添加一些边：

G = nx.Graph()
for s in sets:
    l = list(s)
    G.add_edges_from(zip(l, l[1:]))

提取连接组件（在您的术语中称为“不连通的图形”）：

print(list(nx.connected_components(G)))
# [{'D', 'C', 'E', 'B', 'A'}, {'F', 'H', 'G'}]

- DYZ

---

itertools.combinations 对于三元素集合来说还好，但是它会添加比必要更多的边缘，如果集合变得更大，那么它会添加非常多的边缘。 - user2357112

Answer 3

请查看Rosetta Code任务Set consolidation。

给定两个项目集，如果任何一个项目在任何一个集合中都是共同的，则将合并应用于这些集合的结果是一组集合，其内容为：

如果两个输入项目集之间不存在共同项，则为两个输入集。如果它们共享一个公共项，则为单个集合，即两个输入集的并集。

给定N个项目集（其中N>2），则结果与重复替换所有两个集合的组合的合并相同，直到无法再对集合对进行合并为止。如果N<2，则合并没有严格的含义，可以返回输入。

- Paddy3118