Graphs — Representation and Traversal (BFS vs DFS)

Build the mental model

A graph models any network of relationships as nodes and edges — exactly the shape of 'related lessons' links across a course. There are two standard representations. An adjacency list stores, per node, only the neighbors it actually connects to — O(V + E) space, efficient when the graph is sparse (most real-world graphs are: a lesson doesn't relate to every other lesson). An adjacency matrix stores a V×V grid of booleans — O(V²) space regardless of edge count, but gives O(1) 'are these two connected?' lookups, useful when the graph is dense or that check happens constantly. Traversal order is a separate choice from representation. BFS uses a queue and explores level by level — visit all direct neighbors before any neighbor's neighbors — which guarantees it finds the shortest path (fewest edges) in an unweighted graph, because it can't reach a farther node before exhausting all closer ones. DFS uses a stack (or recursion) and dives as deep as possible down one path before backtracking — cheaper on memory for deep graphs, and natural when you need to explore every reachable node or detect cycles, but gives no shortest-path guarantee.

Connect it to a real scenario

The Tutorial Platform's 'related lessons' feature is naturally a graph: each lesson is a node, and an edge connects lessons that share a topic, reference each other, or form a prerequisite chain. Representing it as an adjacency list fits well because most lessons relate to only a handful of others, not the whole catalog — keeping the structure sparse and memory-light. When a learner clicks 'find a learning path from where I am to this goal lesson,' BFS over that graph finds the shortest chain of related-lesson hops (fewest steps), since edges are initially unweighted. DFS is better suited to a different task on the same graph: recursively walking every lesson reachable from a starting point to build a full topic map, or to detect a prerequisite cycle a content editor accidentally introduced.

Adjacency lists are space-efficient (O(V+E)) for sparse graphs; adjacency matrices cost O(V²) space but give O(1) edge lookup.
BFS (queue-based) guarantees the shortest path in an unweighted graph.
DFS (stack/recursion-based) dives as deep as possible down one path first — well suited to reachability and cycle-detection tasks.

Try the working example

python

from collections import deque

# adjacency list: each lesson lists the lessons it links to as "related"
graph = {
    "python-basics": ["loops", "functions"],
    "loops": ["python-basics", "recursion"],
    "functions": ["python-basics", "recursion"],
    "recursion": ["loops", "functions", "dynamic-programming"],
    "dynamic-programming": ["recursion"],
}

def bfs(graph, start):
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

print(bfs(graph, "python-basics"))

You should see

Prints the BFS traversal order, level by level: ['python-basics', 'loops', 'functions', 'recursion', 'dynamic-programming'].

5-minute try-it

Write a dfs function for this graph using a stack (list.pop()) instead of a queue — compare its traversal order against bfs's output.

One important caution

Marking a node visited when it's dequeued/popped instead of when it's enqueued/pushed — this lets the same node get queued multiple times, causing duplicate work or wrong traversal order.

Using an adjacency list for a dense graph where 'are these connected?' is checked frequently — the linear scan through neighbor lists is slower than a matrix's O(1) lookup.

Wikipedia — Breadth-first search — Data Structures & Algorithms