. The main loop for this algorithm is the while loop in lines 10 – 18. What is varying…

. The main loop for this algorithm is the while loop in lines 10 – 18. What is varying…

Question:

  

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

Expert Answer:

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