BFS 和 DFS 访问的节点序列是否相同？

Question

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

会不会出现BFS和DFS遍历的顶点序列相同的情况？允许这种情况发生的图表的属性(s) 是多少？

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

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

Answer 1

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

Answer 2

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

一般来说，只有最右边的child可以有多个child。但是您可以将链接 "back" 指向图表中之前访问过的任何节点。

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

BFS 和 DFS 访问的节点序列是否相同？

Would sequence of nodes visited by BFS and DFS ever be the same?

algorithm

graph

graph-algorithm