. The main loop for this algorithm is the while loop in lines 10 - 18....

  

Transcribed Image Text:

. The main loop for this algorithm is the while loop in lines 10 - 18. What is varying with each iteration of the main loop? [Or, what are the loop variants?] [5 points] a. b. C. What color are all of the nodes in queue Q? [5 points] Give a loop invariant statement for the main loop. [Remember that all of the black nodes have already been visited and will never be revisited, all of the gray nodes have been seen but not yet visited, and the white nodes have not been seen yet.] [5 points] What property of a queue ensures we are performing a breadth-first search here? [5 points] How would you change the BFS algorithm to provide a depth-first search? [5 points] Here is the algorithm from the text for breadth-first search. BFS(G, s) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. for each vertex uEG.V-s u.color= WHITE u.d = 00 u.π = NIL GRAY s.color s.d = 0 = S. π = NIL Q = Ø Enqueue(Q, s) while QØ u = Dequeue(Q) for each VEG.Adj[u] if v.color= WHITE v.color= GRAY v.d = u.d + 1 V. π = U Enqueue (Q,v) u.color = BLACK . The main loop for this algorithm is the while loop in lines 10 - 18. What is varying with each iteration of the main loop? [Or, what are the loop variants?] [5 points] a. b. C. What color are all of the nodes in queue Q? [5 points] Give a loop invariant statement for the main loop. [Remember that all of the black nodes have already been visited and will never be revisited, all of the gray nodes have been seen but not yet visited, and the white nodes have not been seen yet.] [5 points] What property of a queue ensures we are performing a breadth-first search here? [5 points] How would you change the BFS algorithm to provide a depth-first search? [5 points] Here is the algorithm from the text for breadth-first search. BFS(G, s) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. for each vertex uEG.V-s u.color= WHITE u.d = 00 u.π = NIL GRAY s.color s.d = 0 = S. π = NIL Q = Ø Enqueue(Q, s) while QØ u = Dequeue(Q) for each VEG.Adj[u] if v.color= WHITE v.color= GRAY v.d = u.d + 1 V. π = U Enqueue (Q,v) u.color = BLACK

Answer rating: 100% (QA)

a Loop Variants The color of the nodes In each iteration the color of nodes is changing Initially al... View the full answer