Breadth-First Search

From a start vertex, explore the graph layer by layer using a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours. Visited is checked before enqueue so the queue stays bounded by V.

Algorithm

The canonical input is the 6-vertex undirected graph from graph-adjacency-list (defined inline here). Starting at vertex 1, the deterministic visit order is [1, 2, 3, 4, 5, 6].

Basic Implementation

basic.py

from collections import deque

adj = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3, 5],
    5: [4, 6],
    6: [5],
}

start = 1
visited = {start}
queue = deque([start])
order = []
while queue:
    v = queue.popleft()
    order.append(v)
    for nb in adj[v]:
        if nb not in visited:
            visited.add(nb)
            queue.append(nb)
print(order)

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

Python: collections.deque gives O(1) popleft. A plain list would do O(n) per pop.
The replay shows the dequeued vertex, the queue after, and the visited set after each step, matching the lesson spec.

layered exploration A queue processes the closest vertices first.