algorithm - 双向图中的传递闭包

Question

我有一个包含项目和项目之间关系的大型结构。我需要找到所有项目的所有传递关系。我复制所有链接并使用传递闭包。例如:

A --- B --- C     E --- F --- G
      |
      |
      D

因此我需要得到这些对:

A-B, A-C, A-D, B-A, B-C, B-D, C-A, C-B, C-D, D-A, D-B, D-C,
E-F, E-G, F-E, F-G, G-E, G-F

为了使用传递闭包，我应该使用对 [A-B、B-A、B-C、C-B、B-D、D-B、E-F、F-E、F-G、G-F]。这对我来说是个大问题，因为数据集非常大。解决我的问题的最佳方法是一种算法，它允许仅使用单边链接(A-B、B-C、C-D、E-F、F-G)获取所有关系。是否有任何算法可以在没有重复链接的情况下获取图中每个元素的所有关系？

Answer 1

您可以将此问题建模为图形问题，并使用 DFS(深度优先搜索)或 BFS(广度优先搜索)遍历您拥有的整个数据集。在遍历过程中，您可以为您正在调查的森林中的每棵树分配一个组件编号，因此，您可以找到这个所有连接的组件您拥有的数据的 em>图表。然后对于每个连接的组件，您可以简单地使用其成员组成 2 组，并使用它们来描述关系。如果元素数量为奇数，您可以选择一个已使用的项目并将其链接到最后一个剩余的项目。

这显然假设您的目标是单独找到连接的组件，而不是像您所说的那样以特定方式打印关系。例如，如果您尝试打印链接以使项目之间的最大距离尽可能小，那么问​​题就会变得复杂得多。

与我上面提到的相同假设的另一种方法是使用联合查找的方法，也称为称为不相交集的数据结构。您可以从 N 套开始，其中有 N 件元素。然后，当您遍历这些关系时，对于每个关系 (x, y)，您将包含项目 x 和 y 的集合联合起来。最后，所有连通分量都在同一个集合中。

第一种方法具有 O(V + E) 时间复杂度，V 和 E 是数据中项目和关系的数量， 分别。第二种方法具有 O(V + E . k(V)) 时间复杂度，其中 k 是一个称为 Inverse Ackermann 的函数，它增加得非常缓慢。 (即比对数函数还要慢)