BFS idea

Explore layer by layer from a start vertex.

BFS layers

Breadth-first search (BFS) starts at a source vertex and spreads layer by layer outward.

Each layer processes all vertices one step further. This makes BFS give the path with the fewest edges in an undirected graph.

BFS is often used for shortest path and reachability problems; it is implemented with a queue.

Order priority

BFS adds a vertex's neighbors to the queue when processed. First in, first out (FIFO) applies.

This way vertices with smaller distance are always processed first; the order stays intact.

Adding happens at the back, removal at the front; this preserves the layer order.

Exercise Print layers

Write bfs_order(graph, start). List vertices in BFS visit order and return it. Print [0, 1, 2, 3] with print(bfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)).

Show example solution

def bfs_order(graph, start):
    # Return BFS visit order
    visited = []
    queue = [start]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            for nb in graph[node]:
                if nb not in visited:
                    queue.append(nb)
    return visited
print(bfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))

Test yourself

Which data structure does BFS use?
- Stack
- Queue
- Stack and queue
- Heap
Show answer

Queue — Queue.
BFS start
```
queue = [____]
```
Show answer
```
queue = [start]
```
BFS idea: match the terms

BFS

Layer
queue

FIFO
DFS

Deep
heap

Priority

Next lesson: Using a queue

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies