BFS和DFS访问的节点的顺序会相同吗

Question

假设深度优先搜索（DFS）和广度优先搜索（BFS）的图遍历分别使用堆栈和队列来实现。

是否存在BFS和DFS遍历的顶点序列相同的情况？允许这种情况发生的图的属性是什么？

为了简单起见，我们还假设这是一个稀疏图，我们的图表示为邻接列表，如图所示：

For example: 
0 -> 1
1 -> 2
2 -> 3 -> 4 -> 1
3 -> 2 -> 4

Answer 1

BFS和DFS以相同顺序访问节点的最简单的图是链表。由于链表只是一个在每个深度只有一个节点的图，因此两种算法都将以相同的顺序访问节点，假设无向图从链表的一个端点开始，或者有向图从因度=0的节点开始。

Answer 2

这只适用于一些非常简单的图。它们看起来都是这样的，根是您访问的第一个节点，遍历的顺序就像图片上一样，从左到右。随意删除任何你想要的节点，我只是画出最复杂的结构。

一般来说，只有最右边的孩子才能生不止一个孩子。但是，您可以有指向"回"图中以前访问过的任何节点的链接。

  r o o t
 /  |...  
1st 2nd  nth
          
          node
            
            ...
              
              node
             / |.. 
            a  b    z
                     
                    ....