Breadth-first traversal

What is a graph?

A graph is a collection of vertices and edges. A vertex, also called a node, represents an item. An edge represents a connection between two items. Edges can have a direction or a weight. Graph traversal visits connected vertices while remembering which have already been visited.

Example: Let A, B, and C be vertices, with edges A–B and B–C. A can reach C through B. A directed edge A → B permits movement from A to B but does not automatically permit movement back.

Helpful before this chapter

If these ideas are new, begin with:

Hash maps and sets Queues and deques Recursion

Understand the idea

Breadth-first search processes vertices by nondecreasing distance from the source. First discovery gives a shortest unweighted path; parent pointers reconstruct one such path.

Work through an example

The lab discovers B,C at distance 1 and D at distance 2. D's chosen parent depends on neighbor order, but distance does not.

Time and space complexity

O(V+E) time/O(V) state for adjacency lists.

Why it works

Before processing distance d+1, all queued distance d vertices are processed.

Common mistakes

Weighted edges invalidate the layer-cost argument.
Unreachable nodes need an explicit infinity or absent representation.

Chapter lab · Python implementation

A graph models entities and connections; edges can be directed or undirected, weighted or unweighted. Our lab uses adjacency lists and marks BFS vertices when enqueuing. The diagram has a cycle A-B-D-C-A, so visited state is essential. Distances count edges because every edge has equal cost.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from collections import deque

def bfs(graph,start):
    distances={start:0}
    parent={start:None}
    queue=deque([start])
    while queue:
        node=queue.popleft()
        for neighbor in graph.get(node,[]):
            if neighbor not in distances:
                distances[neighbor]=distances[node]+1
                parent[neighbor]=node
                queue.append(neighbor)
    return distances,parent

def components(graph):
    seen=set(); count=0
    for start in graph:
        if start in seen: continue
        count+=1; seen.add(start); stack=[start]
        while stack:
            node=stack.pop()
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor); stack.append(neighbor)
    return count

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

g={'A':['B','C'],'B':['A','D'],'C':['A','D'],'D':['B','C'],'E':[]}
d,p=bfs(g,'A'); assert d=={'A':0,'B':1,'C':1,'D':2}
assert p['D'] in ['B','C']
assert components(g)==2
assert bfs({'X':[]},'X')[0]=={'X':0}

CHECK YOUR UNDERSTANDING