Trees and Graphs

Graphs, BFS, and DFS

Nodes, edges, and the two ways to explore them

~13 minLesson 12 of 25Written by Claude Opus 4.8

Model anything as dots and lines, store it two ways, and explore it with two loops that differ by a single word: queue or stack.

Friend networks, road maps, web links, the dependency tree of your build - they are all the same shape: things and the connections between them. That shape is a graph, and two tiny algorithms - BFS and DFS - are enough to explore any of them. The whole difference between the two is whether you remember where to go next with a queue or a stack.

What a graph is

A graph is a set of vertices (nodes) joined by edges. Edges can be undirected (a friendship - it goes both ways) or directed (a one-way link,

A \to B

), and each edge can carry a weight (a distance, a cost, a probability). That is the entire vocabulary. Everything else is a choice about how you store it and how you walk it.

Two ways to store the same graph

Before you can traverse a graph you have to represent it in memory. There are two standard choices, and the demo below lets you flip the same seven-node graph between them. The trade-off is space versus edge-lookup speed:

	Adjacency list	Adjacency matrix
Space	O(V + E)	O(V²)
"Is there an edge u-v?"	O(deg u)	O(1)
List a node's neighbors	O(deg u)	O(V)
Best when the graph is…	sparse (few edges)	dense / needs fast edge tests

Traverse it: BFS and DFS

Both traversals grow a frontier of discovered-but-not-yet-visited nodes. Press BFS or DFS, then step (or hit Play). Watch the frontier panel: BFS keeps it in a queue and fans out level by level; DFS keeps it in a stack and dives deep down one branch. Flip the representation to see which row the algorithm reads to find a node's neighbors.

Graph traversal - BFS / DFS. Watch the frontier: BFS fans out level by level, DFS dives deep down one branch.

Show

Queue · FIFO: take from the front, add to the back

Visit order

nothing visited yet

Start at A: enqueue it and mark it discovered. We always dequeue from the front of the queue.

A: B C

B: A D E

C: A F G

D: B

E: B F

F: C E

G: C

Each node stores only its own neighbors → O(V+E) space. The highlighted row is the one the traversal reads right now.

The queue vs. the stack is the whole trick

A queue serves nodes in the order they were found - first in, first out - so BFS finishes an entire distance-layer before touching the next: level by level. Swap the queue for a stack and the newest node is served first, so DFS plunges down one branch to the bottom, then backtracks. The visited set is what stops either one from looping forever around a cycle like

A \to B \to E \to F \to C \to A

The matrix, the handshake, and shortest paths

An adjacency matrix is an $n \times n$ matrix $A$ with

A_{ij} = {10 if there is an edge i \to j otherwise.

Replace the $1$ s with weights, $A_{ij} = w_{ij}$ , and you have a weighted adjacency matrix. It costs $O (n^{2})$ space even when edges are rare; an adjacency list costs only $O (V + E)$ . Both let a traversal touch every vertex once and every edge once, so BFS and DFS run in $O (V + E)$ time - a consequence of the handshake lemma, $\sum_{v} de g (v) = 2∣ E ∣$ . And because BFS drains its frontier first-in-first-out, it reaches every vertex by a fewest-edge path: on an unweighted graph it computes shortest paths for free.

The code is almost identical

Here is the punchline. BFS and DFS are the same loop; the only real difference is one call - popleft() (take from the front, a queue) versus pop() (take from the back, a stack). Everything else, including the visited set that tames cycles, is shared.

from collections import deque

def traverse(graph, start, mode="bfs"):
    frontier = deque([start])           # bfs: use as a queue · dfs: use as a stack
    seen     = {start}                    # visited set: never enqueue a node twice
    order    = []
    while frontier:
        node = frontier.popleft() if mode == "bfs" else frontier.pop()
        order.append(node)                 # "visit" the node
        nbrs = graph[node] if mode == "bfs" else reversed(graph[node])
        for nb in nbrs:                    # explore neighbors (reversed for dfs = recursion order)
            if nb not in seen:            # skip seen nodes -> no infinite loop on cycles
                seen.add(nb)
                frontier.append(nb)
    return order                         # bfs -> level order · dfs -> deep-first

One loop, one swap: popleft() is a queue (BFS), pop() is a stack (DFS).

Don't forget the visited set

Drop the seen check and any graph with a cycle sends the traversal into an infinite loop - it will keep re-discovering nodes it already reached. The visited set is also what turns DFS into a tool for cycle detection and lets you count connected components: start a fresh traversal from every still-unvisited node, and the number of restarts is the number of components.

Check yourself

Which frontier structure makes a graph traversal explore level by level?

For a large, sparse graph, why favor an adjacency list over a matrix?

Recall: which structure does each traversal use, and what is each one good at?

Tie the frontier structure to what each traversal buys you. Try to state it, then check.

Lock it in

A graph is just vertices and edges; edges may be directed and weighted.
Adjacency list is O(V+E) space; adjacency matrix is O(V²) but O(1) edge tests.
BFS (queue, FIFO) fans out level by level; DFS (stack, LIFO) dives deep.
The visited set tames cycles and powers cycle detection and connected components.

Primary source

Watch BFS and DFS animate on graphs you build yourself at VisuAlgo - Graph Traversal (visualgo.net/en/dfsbfs). For the rigorous treatment - traversal correctness, the

O (V + E)

analysis, and BFS shortest paths - see MIT 6.006, Introduction to Algorithms (Spring 2020).

Ask your teacher

Here is the connection that makes this lesson matter for LLMs: an attention layer is a graph. Every token is a node, the attention weight from one token to another is a directed, weighted edge, and the full

n \times n

attention matrix is exactly a weighted adjacency matrix - the through-line traced in graphs and adjacency matrices to attention in the LLM course. The same BFS/DFS you just watched also power GraphRAG retrieval, where the system walks a knowledge graph to gather context. Want to layer on cycle detection, topological sort, or weighted shortest paths (Dijkstra)? Ask and I'll build the follow-up.