2022-152

Consider the following graph. If there is a decision between multiple neighbor nodes in the Depth-First Search (DFS) or Breadth First-Search (BFS) algorithms, select the node with the smallest number.

In what order will the nodes be visited in both DFS and BFS algorithms starting at node 1?

1. DFS: 1 – 2 – 3 – 7 – 6 – 5 – 8 – 4  and  BFS: 1 – 2 – 4 – 5 – 3 – 7 – 8 – 6.
2. DFS: 1 – 2 – 3 – 5 – 8 – 7 – 6 – 4  and  BFS: 1 – 2 – 4 – 3 – 5 – 7 – 8 – 6.
3. DFS: 1 – 2 – 3 – 5 – 8 – 6 – 7 – 4  and  BFS: 1 – 2 – 4 – 3 – 5 – 7 – 6 – 8.
4. DFS: 1 – 2 – 3 – 5 – 8 – 6 – 7 – 4  and  BFS: 1 – 2 – 4 – 3 – 5 – 7 – 8 – 6.
5. None of the above.

Original idea by: Rubens de Castro Pereira