Could someone explain the problem below? part 2a and b. I just wasn\'t sure what
ID: 3572605 • Letter: C
Question
Could someone explain the problem below? part 2a and b. I just wasn't sure what they meant by listing vertices in reverse postorder for 2a as well as what dequeued from FIFO queue in PART 2B. The answer is given just not sure why it is what it is. Picture is below thanks
2. Graph search. (8 oints Consider the following acyclic digraph. Assume the adjacency lists are in sorted order: for example, when iterating through the edges pointing from 0, consider the edge 0 1 before 0-6 or 0-7. (7 (a) Compute the topological order by running the DFS-based algorithm and listing the vertices in reverse postorder. (b) Run breadth first search on the digraph, starting from vertex 2. List the vertices in the order in which they ard dequeued from the FIFO queue.)Explanation / Answer
In searching Algos
DFS use STACK
BFS use QUEUE
a) For DFS:
1) Start with source node i.e starting node. Here its 2.
2) Adjacent nodes for 2- 0,1,8 and add the 1st sequential node to stack. Output- 2 0
3) Adjacent nodes for 0- 1,6,7 and add the 1st sequential node to stack. Output- 2 0 1
4) Adjacent nodes for 1- 4,6 and add the 1st sequential node to stack. Output- 2 0 1 4
5) Adjacent nodes for 4- NULL, backtrack the stack and check the unvisited node for 1. Output- 2 0 1 4 6
6) Adjacent nodes for 6- 3,4 and add the 1st sequential node to stack. Output- 2 0 1 4 6 3
7) Adjacent nodes for 3- 5 and add the 1st sequential node to stack. Output- 2 0 1 4 6 3 5
8) Adjacent nodes for 5-all visited, backtrack the stack and check the unvisited node for 0. Output- 2 0 1 4 6 3 5
9) Adjacent nodes for 7-8 and add the 1st sequential node to stack. Output- 2 0 1 4 6 3 5 7 8
b) As the starting node is '2' you need to find all the adjacent nodes to '2' and keep them in a FIFO queue.