给定一个无向循环图，我想通过广度优先搜索或深度优先搜索找到所有可能的遍历。即给定图作为邻接表：查找所有BFS/DFS遍历
A-BC
B-A
C-ADE
D-C
E-C
因此，从根所有BFS路径将是：
{ABCDE,ABCED,ACBDE,ACBED}
和DFS：
{ABCDE,ABCED,ACDEB,ACEDB}
我怎么会产生那些遍历算法有意义的方式？我想可以产生所有字母排列并检查它们的有效性，但这似乎是对我的最后一招。
任何帮助，将不胜感激。
除了其中实际执行所有可能的DFS和BFS遍历你可以试试这个方法的明显的方式：
步骤1. 在DFS遍历从根的起始转变当前访问的邻接表节点如下所示：首先从列表中删除节点的父节点。其次生成在adj列表中其余节点的所有排列。
所以，如果你是在节点C是否来自节点A，你会做：
C -> ADE transform into C -> DE transform into C -> [DE, ED]
步骤2 第1步之后，你有以下转化ADJ列表：
A -> [CB, BC]
B -> []
C -> [DE, ED]
D -> []
E -> []
现在您从（A，0）开始处理，其中对中的第一项是遍历路径，第二项是索引。让我们假设我们有两个队列。一个BFS队列和一个DFS队列。我们把这一对插入队列中。
现在我们重复以下操作，首先为一个队列，直到它为空，然后为另一个队列。
我们弹出队列中的第一对。我们得到（A，0）。节点A映射到[BC，CB]。所以我们生成两条新路径（ACB，1）和（ABC，1）。将这些新路径放入队列中。
从队列中取出第一个（ACB，1）。索引是1，所以我们查看路径字符串中的第二个字符。这是C.节点C映射到[DE，ED]。
我们根据上面的队列根据上面的队列生成新路径并将其放入队列中。所以如果我们正在研究BFS队列（ACBDE，2）和（ACBED，2）。我们队列的内容现在是：（ABC，1），（ACBDE，2），（ACBED，2）。
我们从队列中弹出（ABC，1）。生成（ABC，2），因为B没有孩子。并获得队列： （ACBDE，2），（ACBED，2），（ABC，2）等。在某些情况下，我们最终会得到一堆索引不包含在路径中的对。例如，如果我们得到（ACBED，5），我们知道这是一条完成的路径。
BFS应该非常简单：每个节点都有一定的深度来找到它。在你的例子中，你可以发现深度为0的B，深度为1的B和C以及深度为2的E和D.在每个BFS路径中，你将得到深度为0（A）的元素作为第一个元素，然后是任意排列深度为1（B和C）的元素，然后是深度为2（E和D）的元素的任何置换等等。 如果你看看你的例子，你的4个BFS路径匹配那个模式。 A总是第一个元素，其次是BC或CB，然后是DE或ED。你可以将它推广到深度更深的节点。 为了找到这个，你需要的只是1 Dijkstra搜索，这是非常便宜。
在DFS中，您没有深入分离的好处，这使BFS变得简单明了。我没有立即看到一种与上述算法一样高效的算法。您可以设置图形结构并通过遍历图形和回溯来建立路径。有些情况下效率不高，但对于您的应用程序来说可能已足够。
我认为这也适用于DFS，但如果一个节点有多个潜在父母会发生什么？该OP指出该图是循环的（尽管该示例不是）。假设在B和D之间添加了一条边，它是否仍然会产生所有遍历？孩子排列必须考虑到已经访问过的节点。 – Origin
是的好点。我想OP需要指定遍历是否记得访问节点。假设他们这样做，他想要有限的遍历，我猜在每一步你的索引指向一个节点时，你可以检查这个字母是否包含在索引中的子串中。如果是你删除那封信并尝试下一封信。如果不是，则添加子排列。 – cyon