Java Reference
In-Depth Information
A
C
E
Initial call to BFS on A.
Mark A and put on the queue.
Dequeue A.
Process (A, C).
Mark and enqueue C. Print (A, C).
Process (A, E).
Mark and enqueue E. Print(A, E).
E
B
D
F
B
D
F
Dequeue C.
Process (C, A). Ignore.
Process (C, B).
Mark and enqueue B. Print (C, B).
Process (C, D).
Mark and enqueue D. Print (C, D).
Process (C, F).
Mark and enqueue F. Print (C, F).
Dequeue E.
Process (E, A). Ignore.
Process (E, F). Ignore.
D
F
F
Dequeue B.
Process (B, C). Ignore.
Process (B, F). Ignore.
Dequeue D.
Process (D, C). Ignore.
Process (D, F). Ignore.
Dequeue F.
Process (F, B). Ignore.
Process (F, C). Ignore.
Process (F, D). Ignore.
BFS is complete.
Figure11.12
A detailed illustration of the BFS process for the graph of Fig-
ure 11.11(a) starting at Vertex A. The steps leading to each change in the queue
are described.
