2022-158

Concerning the Breadth First Search (BFS) algorithm with a queue, observe the oriented graph below, and assume that the adjacency lists are arranged in decreasing order.

Suppose you start a BFS in this graph from node 3.  Select the option representing the order of node numbers loaded into the queue during this operation.

1. 3 – 4 – 6 – 5 – 7 – 8 – 2 – 1 – 10
2. 3 – 6 – 5 – 4 – 8 – 7 – 2 – 1
3. 3 – 4 – 5 – 6 – 2 – 8 – 7 – 10 – 1
4. 3 – 6 – 5 – 4 – 8 – 7 – 2 – 1 – 10
5. None of the above.

Original idea by: Rubens de Castro Pereira