Trace the BFS algorithm on this undirected graph to traverse it starting from vertex 1, and figure out which vertices lead to which other vertices. For reference, the BFS algorithm is shown. Use the adjacency list above for the order of the nodes explored and follow the trace format started below.

0	[1, 2, 3]
1	[0, 4, 5]
2	[0, 3]
3	[0, 2, 4]
4	[1, 3, 5, 6]
5	[1, 4, 6]
6	[4, 5]

Algorithm

"Breadth-first traversal algorithm overview

enqueue the starting vertex, and mark it as visited

loop until queue is empty

dequeue first vertex and add it to iterator

enqueue each unmarked vertex adjacent to the dequeued vertex

mark each vertex enqueued as visited" (Lewis and Chase)

Trace

Initially: queue = [1] visited_vertices = [1] node_container = []

After loop 1: queue = [0, 4, 5] //front is on left visited_vertices = {0, 1, 4, 5} //will be kept sorted for convenience. node_container = [1] //iterable object to record nodes traversed, first item is on left.