如何在图形中搜索路径？

Question

说我有一个边列表，每个边包含两个节点（到和从）。找到两个给定节点的边缘的最佳方法是什么？请注意，边缘的节点可能会重复。

假设我在这种格式下具有优势：

1 <-> 5

3 <-> 7

5 <-> 6

2 <-> 6

然后，诸如1 5的查询将返回 true 。

然后，诸如5 2之类的查询将返回 true， 因为5连接6并且6连接至2。

然后，诸如1 7的查询将返回 false 。

然后，诸如7 4之类的查询将返回 false， 因为4不存在，这意味着它是无边节点。

Answer 1

在我看来，您只是在询问无向图中两个顶点之间是否存在路径，但不一定是该路径可能是什么。这与询问两个顶点是否在图形的相同连接组件中相同。

如果您确实只需要知道两个顶点是否在相同的连接组件中，则可以使用不相交集数据结构来简单高效地执行算法。

initialize the disjoint set structure (DSS)
for each edge:
  for each vertex in edge:
    if the vertex does not exist in the DSS:
      create a new subset in the DSS containing only the vertex
  merge the subsets of the two vertices

要确定在处理完所有边后两个顶点之间是否存在路径，只需检查两个顶点是否在同一子集中。如果它们是，则它们之间存在一些路径。

使用DSS的有效实现，该算法的效果仅比线性时间差一点，即使使用简单的DSS链表实现，它的O（n *log（n））也是如此。正如j
_随机_黑客提到的那样，无论是否仅计算传递闭包，Floyd-Warshall的存储时间均为O（n ^ 3）和O（n ^
2），并且使用Dijkstra的算法需要O（n *log（n） ）计算每个查询。