Summary - BFS

Run BFS on a graph and print the order in a mini task.

Summary - BFS

BFS is layer-by-layer search using a queue, a visited set and a neighbor loop. It yields the shortest step count.

In this mini task you will run BFS and print the visit order; combine all the pieces.

BFS discovers all reachable vertices in layer order; this is ideal for shortest path.

Exercise Print BFS

Write bfs_print(graph, start). Print the BFS visit order with print(). Output: [0, 1, 2, 3].

Show example solution

def bfs_print(graph, start):
    # Print BFS 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)
    print(visited)
bfs_print({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)

Test yourself

Summary - BFS: match the terms

BFS

Queue
layer

Step
visited

No repeat
neighbor

Loop
Loop condition
```
while ____:
```
Show answer
```
while queue:
```
What is BFS's time complexity?
- O(log V)
- O(V * E)
- O(V^2)
- O(V + E)
Show answer

O(V + E) — O(V + E).

Next lesson: DFS idea

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies