bfs example

Suppose we have a graph with the following adjacency list:

0: 1, 2
1: 0, 2, 3
2: 0, 1, 4
3: 1, 4
4: 2, 3

We want to perform a Breadth-First Search (BFS) starting from vertex 0.

First, we add vertex 0 to a queue and mark it as visited. The queue now contains [0].

0 (visited)
queue: [0]

Next, we take the first element from the queue (0) and add its neighbors (1 and 2) to the queue if they haven't been visited yet. We mark them as visited.

0 (visited)
queue: [1, 2]

We now take the first element from the queue (1) and add its neighbors (0, 2, and 3) to the queue if they haven't been visited yet. We mark them as visited.

0 (visited), 1 (visited)
queue: [2, 3, 0]

Next, we take the first element from the queue (2) and add its neighbors (0, 1, and 4) to the queue if they haven't been visited yet. We mark them as visited.

0 (visited), 1 (visited), 2 (visited)
queue: [3, 0, 4]

We now take the first element from the queue (3) and add its neighbors (1 and 4) to the queue if they haven't been visited yet. We mark them as visited.

0 (visited), 1 (visited), 2 (visited), 3 (visited)
queue: [0, 4, 1]

Next, we take the first element from the queue (0) and add its neighbors (1 and 2) to the queue if they haven't been visited yet. However, both of these vertices have already been visited, so we skip them.

0 (visited), 1 (visited), 2 (visited), 3 (visited)
queue: [4, 1]

We now take the first element from the queue (4) and add its neighbors (2 and 3) to the queue if they haven't been visited yet. However, both of these vertices have already been visited, so we skip them.

0 (visited), 1 (visited), 2 (visited), 3 (visited), 4 (visited)
queue: [1]

Finally, we take the first element from the queue (1) and add its neighbors (0, 2, and 3) to the queue if they haven't been visited yet. However, all of these vertices have already been visited, so we skip them.

0 (visited), 1 (visited), 2 (visited), 3 (visited), 4 (visited)
queue: []

Since the queue is empty, we have visited all reachable vertices from vertex 0. The order in which we visited the vertices is: 0, 1, 2, 3, 4.