Graph Representations & Traversal — Algorithms Course

What you'll learn

A graph models anything with relationships — roads, friendships, dependencies, the web. This module covers how to store one and the two fundamental ways to explore it: breadth-first and depth-first search, the foundation of nearly every graph algorithm to come.

By the end you'll be able to:

Choose between an adjacency list and a matrix
Run BFS and DFS
Find connected components and shortest unweighted paths

Representations

A graph is vertices plus edges. Two standard storage schemes trade space for lookup speed. The adjacency list keeps each vertex's neighbors — compact for the sparse graphs that dominate practice. The adjacency matrix is a V×V grid — O(1) to test an edge, but O(V²) space:

Two ways to store the same graph

Adjacency list

A: [B, D]
B: [A, C, E]
C: [B, F]
D: [A, E]
E: [B, D, F]
F: [C, E]

Space O(V + E). Great for sparse graphs.

Adjacency matrix

   A B C D E F
A  0 1 0 1 0 0
B  1 0 1 0 1 0
C  0 1 0 0 0 1
D  1 0 0 0 1 0
E  0 1 0 1 0 1
F  0 0 1 0 1 0

Space O(V²). O(1) edge lookup.

Breadth-first search

BFS explores in rings: all vertices one edge away, then two, and so on, using a queue. Because it reaches nearer vertices first, it finds the shortest path in edges from the start:

BFS from A

Breadth-first search

1/14BFS from A: put A in the queue. The frontier (yellow) is what's waiting.

A FIFO queue holds the frontier (yellow); BFS visits level by level.

Depth-first search

DFS dives as deep as it can before backtracking, using a stack (or recursion). It's the engine behind cycle detection, topological sort, and finding connected components:

DFS from A

Depth-first search

1/8DFS from A: dive as deep as possible before backtracking.

DFS follows one path to its end, then backtracks and tries the next.

In code

Language

bfs.py

from collections import deque

def bfs(adj, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        u = queue.popleft()          # FIFO: nearest first
        order.append(u)
        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
    return order

Language

dfs.py

def dfs(adj, u, visited=None):
    if visited is None:
        visited = set()
    visited.add(u)
    order = [u]
    for v in adj[u]:
        if v not in visited:
            order += dfs(adj, v, visited)   # dive deep first
    return order

Key idea

BFS uses a queue (FIFO) and explores widest-first; DFS uses a stack (LIFO, or the call stack) and explores deepest-first. Both visit every vertex and edge once — O(V + E) with an adjacency list.

Components & shortest paths

Connected components: run BFS/DFS from each unvisited vertex; each traversal marks one component.
Shortest unweighted path: BFS from the source gives the fewest-edges path to every reachable vertex — record each vertex's parent to reconstruct the route.

	BFS	DFS
`Data structure`	Queue (FIFO)	Stack / recursion (LIFO)
`Explores`	Nearest first	Deepest first
`Finds`	Shortest unweighted path	Cycles, topo order, components
`Time`	O(V + E)	O(V + E)

Recap & quick check

Key takeaways

Adjacency list: O(V+E) space, great for sparse graphs; matrix: O(V²), O(1) edge test.
BFS uses a queue and explores level by level — shortest unweighted paths.
DFS uses a stack/recursion and dives deep — cycles, topo sort, components.
Both run in O(V + E) with an adjacency list.
Run traversal from each unvisited vertex to find all connected components.

Quick check

1. Which data structure does BFS use?

2. What does BFS find in an unweighted graph?

3. Which representation uses O(V²) space?

4. What is the time complexity of DFS with an adjacency list?

Traversal unlocks deeper structure: ordering, cycles, and the graph's skeleton. Next up: Module 25 — Connectivity: Topological Sort, SCC & Bridges.