Question

Please answer all three parts. And show step-by-step answers for each part. Draw anything if necessary. And please don't copy other answers to be at risk being downvoted. Thank you.

Question 1 (50 POINTS): Given a graph G and the Breadth First Search (BFS) and Depth First Search (DFS) traversal algorithms as follows: BFSG) 1 for each vertex u € G.V – {3} 1 2 u.color = WHITE 3 u.d = 0 4 un = NIL 3 5 S.color = GRAY 6 s.d = 0 7 S.1 = NIL 5 6 7 8 Q = 0 9 ENQUEUE (Q, S) 10 while Q +9 8 10 11 11 u = DEQUEUE(Q) 12 for each v e G. Adj[u] 13 if v.color == WHITE 12 13 14 V.color = GRAY 15 v.d = u.d +1 16 V.1 = u 17 ENQUEUEQ,V) 18 u.color = BLACK

Answer 1

Here is the answer,

I have tried my best to help you explain the answer, if you face any difficulty then do let me know I would try to explain that to you and update my answer.

1. BFS: No. of steps required: 6 steps

LI L2 L3 12 BES Initial Queue → 4151617 8910 Now, since we found our target 6, we stop & return here.

2. DFS: No. of steps required: 17 steps + 2 steps(for returning from recursive calls)

20 DES 9 @ 18 113 FOUND (retum) 19 12

The 1,2,3 marked in red without circle are the steps.

3. The DFS traversal will take more steps than BFS since in DFS we would have to move to the leaf node and backtrack from there. But in BFS we will be moving level by level.

But keep in mind, it depends. Suppose node 6 would have been in the place of node 2 then no. of steps would have been equal. Another case can be if node 6 would have been in the place of node 8 then DFS would take lesser no. of steps than the other.

I hope it answers your problem. Do let me know in the comments if you face any issue, also do upvote the solution.

Thank you