如何在图表中搜索路径？

假设我有一个边缘列表,每个边包含两个节点(往返).找到两个给定节点的边缘的最佳方法是什么？请注意,边缘中的节点可能会重复.

说我有这种格式的优势:

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不存在,这意味着它是无边节点.

听起来像你只是问一个无向图中两个顶点之间是否存在路径,但不一定是该路径可能是什么.这与询问两个顶点是否在图的同一连通分量中相同.

如果你真的只需要知道这两个顶点是否在同一个连通组件中,那么就有一个使用Disjoint-set数据结构的简单而有效的算法.

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)).正如_随机_黑客提到的那样,Floyd-Warshall无论你是否只计算传递闭包都是O(n ^ 3)时间和O(n ^ 2)存储,并且使用Dijkstra算法需要O(n *log(n)) )计算每个查询.