BFS for reachability

Find reachable cities with BFS.

BFS for reachability

Now we will find which cities are reachable from a city with BFS. Discover all reachable cities.

BFS works with a queue and a visited set; it spreads layer by layer.

We will return the sorted list of reachable cities; the output is deterministic.

Sorted output

We sort results with sorted() for deterministic output; every run gives the same result.

BFS output is already deterministic but sorting adds a guarantee; this matters for testing.

The sorted list makes output readable; cities appear in alphabetical order.

Exercise Reachable cities

Write bfs_reachable(graph, start). Return the sorted list of cities reachable via BFS. Print ['A', 'B', 'C', 'D'] with print(bfs_reachable(build_cities(), "A")).

Show example solution

def build_cities():
    # Define the city graph
    return {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
def add_neighbor(graph, city, neighbor):
    # Add neighbor
    graph[city].append(neighbor)
    return graph
def bfs_reachable(graph, start):
    # Reachable cities
    visited = set()
    queue = [start]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            for nb in graph[node]:
                if nb not in visited:
                    queue.append(nb)
    return sorted(visited)
print(bfs_reachable(build_cities(), "A"))

Test yourself

Queue init
```
queue = [____]
```
Show answer
```
queue = [start]
```
BFS for reachability: match the terms

BFS

Layer
queue

Queue
visited

No repeat
sorted

Alphabetical
What does sorting BFS output ensure?
- Faster execution
- Deterministic result
- Fewer edges
- Less memory
Show answer

Deterministic result — Deterministic result.

Next lesson: Print the result

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies