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

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

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） ）计算每个查询。