BFS(G, S) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:...

 

Transcribed Image Text:

BFS(G, S) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: for each vertex u = G.V - {s} do u.color = WHITE u.d = U.TT = NIL s.color = GRAY s.d = 0 S.TT = NIL Q = 0 Enqueue (Q, s) while Q do u =Dequeue(Q) for each ve G.adj[u] do if v.color == WHITE then v.color = GRAY v.d = u.d + 1 V.TT = U Enqueue(Q, v) u.color BLACK Do you think we can remove the line 18: u.color = BLACK from the algorithm? Explain why. BFS(G, S) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: for each vertex u = G.V - {s} do u.color = WHITE u.d = U.TT = NIL s.color = GRAY s.d = 0 S.TT = NIL Q = 0 Enqueue (Q, s) while Q do u =Dequeue(Q) for each ve G.adj[u] do if v.color == WHITE then v.color = GRAY v.d = u.d + 1 V.TT = U Enqueue(Q, v) u.color BLACK Do you think we can remove the line 18: u.color = BLACK from the algorithm? Explain why.