无向图中的唯一路径

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

来源

2013-12-09 Zhiwen Fang

第二条路是什么意思？第二条路与第一条路共享任何V或E吗？ – dfb

@dfb它们可以共享一些V或E.我们可以通过有序的边缘序列来呈现简单的路径，它们在至少一个边缘应该是不同的 –

方法1：

从源节点做一个定期BFS，但继续下去，直到你已经探索了整个图形，不只是直到你发现了目标。

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

如果您得到多个路径，这些路径的顶点和目标之间没有顶点相同（如果发生这种情况，您可以在此停止）。

现在再从源节点进行搜索。

如果我们当前位于上面找到的路径中的一个节点上，请探索所有邻居（以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时，维护每个路径的所有节点的产品。要检查一个已经访问过的节点是否在同一条路径上，只需检查该产品是否可以被该节点的值整除。

来源

2013-12-09 20:11:29 Dukeling

对于BFS程序，可以多次将一个顶点推入堆栈，如果是，则运行时间不会是O（V + E）。它认为检查的方式是不切实际的。假设有成千上万个顶点，前1000个素数的乘积非常大，它将与计算此产品的顶点数量以及大量内存成线性关系。 –

@notbad一个顶点不能被推入堆栈多次，但是，我想这不会太高效。我用完全不同的方法编辑了我的答案。 – Dukeling

如果所有顶点减去源和目标都被禁止，您可以将它们移除并尝试找到另一条路径。与边缘相同的东西。如果他们可以共享除一个顶点/边以外的所有顶点/边，则可以尝试在时间O(V(V+E))中删除路径中的每个顶点/边，或者干脆继续DFS并计算路径数。

来源

2013-12-09 20:02:31 dfb

继续DFS不会准确地找到路径的数量，因为它不会找到经过已经发现的路径而不需要修改的路径。 –

@Andrey - 取决于你对路径的定义。如果他们只需要一个边缘的差异，这可以很好地工作。 – dfb

我想这取决于你的意思是“计数路径的数量”。一旦找到路径，继续DFS算法是不够的，因为它通常是写入的，其中检查的条件是您与目标顶点相邻。您还需要检查与已发现路径的邻接关系，因为DFS递归条件不会再发送给您。 –

你可以一气呵成，使用任意遍历算法。

您开始遍历顶点s。每当你访问一个新的顶点时，你将它标记为已访问，注意后边缘并像往常一样继续遍历。

当您访问已标记为已访问的顶点时，将其标记为两次访问并从遍历分支中返回。

即使在访问t后，仍继续遍历。遍历结束后，您从t开始，并使用每个顶点中指定的后缘重建路径，这与在找到从s到t的路径时的相同方式。

当你找到至少一个这条道路上两次访问顶点v，则因为至少有两条路s到v，也有至少两条路径从s到t。

如果路径上只有一次访问过的顶点，那么从s到t之间也只有一条路径。

这样的算法有一个运行时间O(|E|)。

来源

2013-12-10 11:09:21 pepo

无向图中的唯一路径

回答

相关问题