查找无向图上的所有路径

Question

我有一个无向图，我想列出起始节点的所有可能路径。 2个节点之间的每个连接在列出的路径中是唯一的唯一，例如给出此图形表示：

{A: [B, C, D],
 B: [A, C, D],
 C: [A, B, D],
 D: [A, B, C]}

一些列出的路径从A开始

A, B, C, D, A, C  in this path we have a connection between
A and B but we can't have a connection between B and A 

我不能使用我知道的DFS现有算法来完成它。任何帮助将非常感激。

Answer 1

最简单的方法是递归尝试每个邻居并组合所有结果。

这假定没有循环 - 如果允许循环（如在您的示例中），将存在无限多个路径。在这种情况下，您可以通过限制要检查的路径长度来创建路径生成器，然后循环遍历所有可能的路径长度。

Answer 2

如前所述，可能最直观的方法是迭代每个潜在起点的所有邻居，直到所有路径都耗尽。

但是，这种方法的风险在于，如果图形具有周期，它往往会永远循环。这可以通过使用访问顶点列表（或者，在您的情况下可能更喜欢访问边缘）来减轻

在伪代码中，可能会出现这样的情况：

paths = []
for node in graph
  visited = []
  path = [node]
  add node and path to stack-or-queue
  while node on stack-or-queue
    pop node and path
    for edges of node
      if edge is not visited
        add edge to visited
        add neighbour to path
        add neighbour and path to stack-or-queue
        add path to paths

它产生一个相对较高复杂度的算法，所以一定要测试它以避免crap。

递归地编写它可能更容易，但它消除了在DFS和BFS之间轻松更改的可能性。