如何搜索路线图？ [英] How can I search a graph for a path?

问题描述

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

说我有这种格式的边缘：

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

解决方案

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

如果你真的只需要知道两个顶点是否在相同的连接组件中，那么有一个简单而有效的算法使用不相交的数据结构。

 为每个边缘初始化不相交集合结构（DSS）
：边缘中每个顶点的
： 
如果顶点不存在于DSS中：
在DSS中创建仅包含顶点的新子集
合并两个顶点的子集
  

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

通过DSS的高效实现，该算法实现的仅仅是线性时间的差，甚至连一个简单的链接列出DSS的实现，它是O（n * log（n））。作为j _ 随机 _ 骇客提到，Floyd-Warshall是O（n ^ 3）时间和O（n ^ 2）存储，无论您是否只计算传递闭包，并且使用Dijkstra的算法需要为每个查询计算一个O（n * log（n））。 p>

Say I have a list of edges each containing two nodes (to and from). What is the best way to find the edge two given nodes? Note that nodes in the edge may repeat.

Say I have edge in this format:

1 <-> 5

3 <-> 7

5 <-> 6

2<-> 6

Then query such as 1 5 will return true.

Then query such as 5 2 will return true because 5 connects 6 and 6 connects to 2.

Then query such as 1 7 will return false.

Then query such as 7 4 will return false since 4 doesnt exist, it means it is edge-less node.

解决方案

It sounds to me like you are just asking if a path exists between two vertices in an undirected graph, but not necessarily what that path might be. This is the same as asking if the two vertices are in the same connected component of the graph.

If you really do only need to know if the two vertices are in the same connected component, then there is a simple and efficient algorithm using a Disjoint-set data structure.

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

To determine if a path exists between two vertices after processing all the edges, just check if the two vertices are in the same subset. If they are, then some path exists between them.

With an efficient implementation of the DSS, this algorithm achieves just slightly worse than linear time, and even with a simple linked-list implementation of the DSS it's O(n*log(n)). As j_random_hacker mentions, Floyd-Warshall is O(n^3) time and O(n^2) storage no matter if you are only calculating transitive closure or not, and using Dijkstra's algorithm requires an O(n*log(n)) calculation for each query.

这篇关于如何搜索路线图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！