Graphs: Representation and Traversal

What a graph is

A graph is points and the connections between them. The points are called vertices (or nodes), the connections edges. You use graphs all the time:

• a subway map: stations are vertices, the tracks between them are edges;
• a social network: people are vertices, a friendship is an edge;
• package dependencies: package A requires package B.

Edges come in two kinds:

• Undirected. Friendship is mutual: if Alice is friends with Bob, then Bob is friends with Alice. The edge A — B can be traversed both ways.
• Directed. Following someone on social media is one-way: you follow a blogger, but they don't follow you back. The edge A → B goes in one direction only.

The trees you already know are a special case of a graph: connected and without cycles. So everything you can do with trees comes in handy here. There's just one new worry: cycles.

How to store a graph

A graph is usually given as a list of edges, for example [[0,1],[0,2],[1,3]]. From it you build one of two representations.

Adjacency list — for each vertex, store a list of its neighbors: graph[0] = [1, 2]. Adjacency matrix — an n × n table where m[i][j] = 1 if there's an edge i → j.

	Adjacency list	Adjacency matrix
Memory	O(V + E)	O(V²)
Is there an edge i–j?	O(deg)	O(1)
Iterate over neighbors	O(deg)	O(V)
When to use	almost always	small, dense graph

Here V is the number of vertices, E the number of edges, and deg the number of a vertex's neighbors. In an interview, 9 times out of 10 you want an adjacency list: defaultdict(list) in Python, List<List<Integer>> in Java. If the graph is undirected, add each edge twice: a → b and b → a.

A grid is a graph too

A very common problem format is a 2D grid: a maze, a map of islands, a box of oranges. You don't need to build an adjacency list; the graph is already there:

• a vertex is a cell (r, c);
• edges lead to the neighbors above, below, left and right: (r±1, c) and (r, c±1).

A handy way to iterate over neighbors is a directions array dirs = [(1,0),(-1,0),(0,1),(0,-1)]. Check every neighbor for two things: did we go out of bounds and can we step there, i.e. it's not a wall.

Traversals: DFS and BFS

Traversing a graph means visiting every vertex reachable from the start. The key difference from a tree is that in a graph you can walk in circles: A → B → A → B… So you need a set of visited vertices (visited). Mark a vertex, and never enter it again.

DFS (depth-first search) is like exploring a maze with one hand on the wall: keep going forward as long as you can; hit a dead end, step back. It's implemented with recursion or a stack. Use it when you just need to "reach everything": find connected components, count islands, detect a cycle.

BFS (breadth-first search) is like ripples from a stone thrown into water. First you visit all the start's neighbors, then their neighbors, and so on, layer by layer. It's implemented with a queue.

BFS's superpower

In an unweighted graph, BFS finds the shortest path. Vertices come out of the queue strictly in order of increasing distance: first everything at distance 1, then everything at distance 2, and so on. So the first time BFS reaches a vertex, it got there by the shortest route. DFS gives no such guarantee: it may wander far out of its way.

	DFS	BFS
Structure	stack / recursion	queue
Shortest path	❌	✅ (if all edges are equal)
Code	shorter	a bit longer

If the problem says "minimum number of steps", "shortest path" or "how many minutes until" — it's almost certainly BFS.

Template: BFS on a grid

The template computes the distance from the start cell to every reachable cell. Walls are marked '#'. The dist array doubles as visited here: a value of -1 means "not visited yet".

from collections import deque

def bfs_grid(grid, sr, sc):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]  # -1 = not visited
    dist[sr][sc] = 0
    q = deque([(sr, sc)])
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            # in bounds, not a wall, not visited yet
            if 0 <= nr < rows and 0 <= nc < cols \
                    and grid[nr][nc] != '#' and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1  # mark right when enqueuing
                q.append((nr, nc))
    return dist

Want DFS instead? Swap the queue for a stack, i.e. take elements from the end, or write a recursion with the same neighbor check. Marking visited works exactly the same way.

Complexity

• Graph: time O(V + E), because we look at every vertex and every edge once. Memory O(V) goes to visited and the queue.
• R × C grid: time and memory O(R · C), since every cell has at most 4 neighbors.

How it sounds in an interview

"I'll treat the grid as a graph: cells are vertices, and the neighbors in four directions are edges. We need the minimum number of steps and the edges are unweighted, so it's BFS. I mark cells as visited when I add them to the queue. Complexity is O(R·C) in both time and memory."

Saying why BFS, rather than just "I'll do BFS", is what earns you points.

Common mistakes

• No visited — the traversal loops forever or runs exponentially long.
• Marking visited on dequeue instead of on enqueue. Then the same cell lands in the queue several times. Mark it the moment you put it in the queue.
• Mixing up rows and cols in the bounds check. It's especially easy to slip when the grid isn't square.
• In an undirected graph, the edge is added in only one direction.
• A slow queue: list.pop(0) in Python and shift() in JS are O(n). Use a deque or a head pointer.
• BFS on a weighted graph. If edges have different weights, BFS doesn't give the shortest path. That calls for Dijkstra, which we'll get to later.

You already know the essentials: a graph is vertices and edges, a grid is a graph too, and a traversal is "a queue or a stack + visited". In the practice that follows, this template shows up in almost every problem of the chapter.