枚举图中单个源的所有路径。

Question

我在想，您是否知道一种算法，可以从单个源枚举图中所有可能的简单路径，而不重复任何顶点。请记住，图将非常小(16个节点)和相对稀疏(每个节点2-5条边)。

为了明确我的问题：

顶点: A，B，C

A connects to B, C
B connects to A, C
C connects to A, B

路径(来自A)：

A,B
A,C
A,B,C
A,C,B

顶点: A，B，C，D

A connects to B, C
B connects to A, C, D
C connects to A, B, D

路径(来自A)：

A,B
A,C
A,B,C
A,B,D
A,C,B
A,C,D
A,B,C,D
A,C,B,D

这肯定不是BFS或DFS，尽管其中一个可能的变体可能有效。我在其中看到的大多数类似的问题都是处理一对节点图，所以我的问题略有不同。

这个Find all possible paths from one vertex in a directed cyclic graph in Erlang也是相关的，但是答案与Erlang有关，或者不清楚到底需要做什么。正如我所看到的，该算法也可以被删除，因为为来自单个源的指定数量的跳数找到了所有可能的简单路径。然后，对于跳数(1到N)，我们可以找到所有的解。

我使用Java，但即使是伪代码也足以帮助我。

Answer 1

在Python风格中，它是一个BFS，对已访问的用户具有不同的跟踪：

MultiplePath(path, from):
  from.visited = True
  path.append(from)
  print(path)

  for vertex in neighbors(from):
    if (not vertex.visited):
      MultiplePath(path, vertex)

  from.visited = False
Return