Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Graphs: adjacency lists and breadth-first reachability

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An adjacency list maps each vertex to its outgoing neighbors. For V vertices and E stored edges, it uses O(V + E) space; an adjacency matrix uses O(V²) space but offers constant-time direct edge checks. Breadth-first search explores vertices in layers from a start vertex. With a visited set, traversal takes O(V + E) time over the reachable subgraph. Mark a vertex when enqueueing, not only after dequeueing, to prevent the same vertex from entering the queue repeatedly through converging paths. Direction and edge meaning must be explicit before interpreting reachability.

Operational case

A depot route map has directed links North to East and West, East to South, and West to South. Starting at North, the queue visits East and West before South. South is enqueued only once despite two incoming paths. The traversal shows reachability, not the cheapest weighted route or a guaranteed physical delivery path; road closures and edge weights would need a richer model. A disconnected depot would remain absent from this result and should not be described as unreachable globally without checking the intended direction.

Working Python program

python
from collections import deque

routes = {"North": ["East", "West"], "East": ["South"], "West": ["South"], "South": []}
frontier = deque(["North"])
visited = {"North"}
order = []
while frontier:
    depot = frontier.popleft()
    order.append(depot)
    for neighbor in routes[depot]:
        if neighbor not in visited:
            visited.add(neighbor)
            frontier.append(neighbor)
print(order)

Output

Output
['North', 'East', 'West', 'South']

Time, space, and tradeoff

Building an adjacency list costs O(V + E) storage when all vertices are represented. BFS adds O(V) worst-case queue and visited storage and scans each stored edge once. For an undirected graph, store both directions or normalize the graph builder; otherwise the implementation silently becomes directed. Neighbor order controls the exact printed traversal order but not the set of reachable vertices. A missing adjacency entry should have an explicit policy instead of raising unexpectedly during a long-running traversal.

Common Mistakes

  • Do not call BFS a weighted shortest-path algorithm.
  • Do not mark visited only after dequeueing when paths converge.
  • Do not infer an undirected edge from a single stored direction.

Connected lessons

Dependency graphs: topological order and cycle rejection continues this operation with mutation checks.

Reachability bitsets: precompute directed paths for a fixed graph adds a related structure with a different operation boundary.

data structures
graphs-and-disjoint-sets
Storage details