查找无向图上的所有路径

Question

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

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

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

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

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