python - 如何将点连接成组

Question

有n个点。 n = 7。我有关于连接点的信息。

import numpy as np
connect = np.array([[0, 0], [0, 4], [0, 5], [1, 1], [2, 2], [3, 3], 
              [4, 0],[4, 4],[5, 0], [5, 5], [6, 6]])

例如 [0, 1] 表示点 0 和点 1 相连。我怎样才能将点分组，以便在组内，点是连接的。在这个例子中，[0, 4], [0, 5]是连通的，但是[4, 5]是不连通的，但它们仍然属于同一个组。结果应该是这样的

groups = [[0, 4, 5], [1], [2], [3], [6]]

编辑:这是我目前的方法。

data = np.full((7, 7), 0)

for c in connect:
    data[c[0], c[1]] = 1

for c in connect:
    data[c[0], :] = data[c[0], :] + data[:, c[1]]
    data[:, c[1]] = data[c[0], :] + data[:, c[1]]

data[np.where(data != 0)] = 1
result = np.vstack({tuple(row) for row in data})
print ([np.where(row != 0)[0] for row in result])

Answer 1

有两种类似的方法可以用来解决这个问题:

1. 不相交集(更多信息和实现见:https://en.wikipedia.org/wiki/Disjoint-set_data_structure)

最初将每个点视为自己的一组，对于每对连接的点，如果节点位于不同的集合中，则尝试组合该集合。如果您不熟悉不相交集，请引用上面的链接，因为它可能会有点长。

组数将是剩余的集合数，成员在集合内描述。

1. 图表

将每个点视为一个节点，将连接视为一条边。您的目标是找到图形的连通分量(整个点)。每个连通分量都是一个组，连通分量的成员是同一组的成员。

有关连通分量 (https://en.wikipedia.org/wiki/Connected_component_(graph_theory)) 的更多信息，您可以使用 BFS 或 DFS (https://en.wikipedia.org/wiki/Graph_traversal) 遍历图形。