Graphs

How to store a graph, and how BFS and DFS walk it: shortest paths without weights, connected pieces, cycles and dependency order.

Overview

A graph is a set of nodes (also called vertices) joined by edges. It models anything where things connect: people and friendships, cities and roads, tasks and the tasks they wait on. A grid is a graph too, where each cell connects to the cells next to it.

Most graph questions reduce to one of two walks. Breadth-first search (BFS) spreads out one step at a time. Depth-first search (DFS) follows one path as far as it goes, then backs up. Both touch every node and edge once, so both take O(V + E) time, where V is the number of nodes and E the number of edges.

The words you need

Directed — An edge u to v goes one way only (a follow, a prerequisite)
Undirected — An edge works both ways (a friendship, a two-way road)
Weighted — Each edge has a cost (distance, time, price)
Degree — The number of edges touching a node; directed graphs split it into in-degree and out-degree
Cycle — A path that returns to where it started
DAG — A directed graph with no cycle; only a DAG has a dependency order
Connected component — A largest group of nodes that can all reach each other

The first thing to ask: is it directed, is it weighted, and can it have cycles? Those three answers pick the algorithm.

Storing a graph

This page uses one small undirected graph throughout: six nodes and seven edges.

An adjacency list maps each node to its neighbors. For this graph it holds 14 entries: each undirected edge is stored twice, once from each end. That is why the degrees always add up to 2E.

0 — 1, 2, 3 — 3
1 — 0, 3, 4 — 3
2 — 0, 3 — 2
3 — 0, 1, 2, 5 — 4
4 — 1 — 1
5 — 3 — 1

Input usually arrives as an edge list, such as [[0, 1], [0, 2], …]. The first step of almost every solution is to turn it into an adjacency list.

Adjacency list — O(V + E) — O(degree of u) — O(degree of u) — Almost always; most graphs are sparse
Adjacency matrix — O(V²) — O(1) — O(V) — Dense graphs, or many 'is there an edge?' checks
Edge list — O(E) — O(E) — O(E) — Sorting edges by weight (Kruskal's MST)

A graph is sparse when E is close to V (a road map: each junction meets a few roads) and dense when E is close to V² (a complete graph, where every pair is joined).

BFS: one step at a time

The BFS loop uses a queue: it starts with the source, then repeatedly takes the oldest node and adds its unseen neighbors to the back. So it finishes every node one edge away before any node two edges away. The first time BFS reaches a node is along a path with the fewest possible edges, which is why BFS gives shortest paths when edges have no weights.

Here is a trace from node 0, reading neighbors in increasing order.

1 — 0 — 1, 2, 3 (1) — 1, 2, 3
2 — 1 — 4 (2) — 2, 3, 4
3 — 2 — none — 3, 4
4 — 3 — 5 (2) — 4, 5
5 — 4 — none — 5
6 — 5 — none — empty

Every node is taken out once and every adjacency list is read once: O(V + E) time, and O(V) extra space for the queue and the seen set. In Python, use collections.deque for the queue: its popleft() is O(1), while list.pop(0) shifts every element and costs O(n).

DFS: go deep, then back up

DFS follows the first unseen neighbor, then that node's first unseen neighbor, and so on. When a node has no unseen neighbors left, it returns to the node it came from and tries the next one. Recursion does this naturally; an explicit stack does the same without recursion.

Here is a trace from node 0, again reading neighbors in increasing order.

1 — 0 — Visit 0; first unseen neighbor is 1
2 — 0, 1 — Visit 1; 0 is seen, so go to 3
3 — 0, 1, 3 — Visit 3; 0 and 1 are seen, so go to 2
4 — 0, 1, 3, 2 — Visit 2; both neighbors seen, back up to 3
5 — 0, 1, 3, 5 — Visit 5; nothing new, back up to 3, then to 1
6 — 0, 1, 4 — Visit 4; nothing new, back up to 1, then to 0
7 — 0 — 0's other neighbors (2, 3) are seen; done

Visit order: 0, 1, 3, 2, 5, 4. DFS also costs O(V + E) time and O(V) space, but the space is the depth of the path, which can reach V on a long chain. That matters in Python: the interpreter has a recursion limit (sys.getrecursionlimit()), and a deep DFS on a big grid can hit it and raise RecursionError. Use an explicit stack when the input can be large.

Shortest path, no weights — Yes: first arrival is shortest — No: first arrival can be a long way round
Connected components, flood fill — Yes — Yes, often shorter to write
Cycle in a directed graph — Kahn's algorithm (counts what it could order) — Three node states (below)
Dependency order — Kahn's algorithm — Reverse post-order
All paths, or a path with a property — Rarely — Yes, with backtracking
Extra memory — The widest level — The deepest path

Finding cycles

In an undirected graph, every edge leads straight back to the node you came from, so that edge does not count. During DFS, reaching a seen node that is not your parent means a cycle. Union-Find works too: an edge whose two ends are already in the same group closes a cycle.

In a directed graph, 'already seen' is not enough. In the graph 0 to 1, 0 to 2, 1 to 3, 2 to 3, node 3 is reached twice, yet there is no cycle. What matters is whether the node you reach is still on the current path. Give every node one of three states.

Picking the algorithm

Topological sort, Union-Find, shortest paths, minimum spanning trees and grid traversal each have their own topic with more detail; this page covers the ideas they all build on.

Grids are graphs

Each cell is a node, and its neighbors are the cells up, down, left and right (ask whether diagonals count). You never build an adjacency list; you compute the neighbors from the row and column and skip any that fall off the edge.

Up — (r - 1, c) — r > 0
Down — (r + 1, c) — r 0
Right — (r, c + 1) — c < cols - 1

A grid with R rows and C columns has R × C nodes and at most four edges each, so a full traversal is O(R × C).

What you will be able to do

Turn an edge list into an adjacency list and say why a list beats a matrix for sparse graphs.
Trace BFS and DFS by hand and explain why only BFS gives shortest paths without weights.
Detect a cycle in an undirected graph (parent check) and a directed one (three states).
Pick BFS, DFS, topological sort, Union-Find or Dijkstra from the wording of a question.
Treat a grid as a graph and count its connected regions.

When to use it

Counting connected pieces (Number of Islands, Number of Connected Components)
Shortest path when every edge costs the same (BFS)
Detecting a cycle in a directed graph (Course Schedule)
Ordering tasks that depend on each other (topological sort)
Shortest path with non-negative weights (Dijkstra)
Groups that merge as edges arrive (Union-Find)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio