algorithm - 无向图中的唯一路径

Question

判断两个顶点之间是否存在路径是高效的，例如DFS或BFS，它会在O(V+E)内完成。如何确定两个给定顶点之间是否存在多于一条路径？路径应该是简单路径，即没有重复的顶点。它不一定是最短路径。会用O(V+E)完成吗？只说出存在，不需要给出确切的路径。

Answer 1

方法一:

从源节点执行常规 BFS，但要继续，直到您探索了整个图，而不仅仅是找到目标。

这应该为您提供从源到目标的路径。

如果您获得多条路径，这些路径将是除了源和目标之外没有顶点的公共(public)路径(如果发生这种情况，您可以在此处停止)。

现在从源节点开始搜索。

如果我们当前在上面找到的路径中的一个节点上，则探索所有邻居(递归地，以 DFS 方式)除了上面路径中该节点后面的那个。之后探索该节点。

一些伪代码来更好地解释:

path = bfs(source, target)

dfs(n)
  visited[n] = true
  if path.contains(n)
    next = path[path.indexOf(n) + 1]   // next node in path after n
    for each neighbour n2 of n
      if n2 != next and !visited[n2]
        if path.contains(n2)
          found multiple paths
        dfs(n2)
    dfs(next)
  else
    for each neighbour n2 of n
      if path.contains(n2)
        found multiple paths
      dfs(n2)

运行时间应该仍然是O(|V| + |E|)。

方法 2:

(这不是一个好方法，只看运行时间——也许有人看到了一个有效的变体)

使用以下修改从源节点执行 BFS:

继续探索整个图表，而不仅仅是找到目标。

如果您遇到一个已经访问过但不在同一路径上的节点(即会形成一个循环)^[1]，与其简单地跳过它，不如在该节点上设置一个标志。

完成 BFS 后，遍历找到的路径，如果任何节点设置了标志，我们就知道存在多条路径。

运行时间应该仍然是O(|V||E|)。

[1]:检查一个节点是否在同一条路径上并不是一件容易的事情。基本上您需要一组节点。

一个选项是一组文字节点 - 这里的问题是您必须在每一步都复制它，这非常昂贵。

在此基础上，一组节点会更有效。对于 1000 个节点，我们只需要 1000 位来存储一条路径。对于真正稀疏的图(边很少的图)，这实际上比文字集更糟糕。

另一种选择是为每个节点分配一个唯一的质数。在进行 BFS 时，为每条路径维护所有节点的乘积。要检查已访问的节点是否在同一路径上，只需检查产品是否可以被节点的值整除。