Graphs

Representing graphs, traversing them, and recognising when no traversal is needed at all

A graph is nodes connected by edges. Trees are a special case — a graph with no cycles and one path between any two nodes — so everything here generalises what you already know about trees, with one addition: you must track visited nodes, because a graph can lead you in circles.

What a Graph Actually Looks Like

A tree node points down at its children, and every node has exactly one parent. Remove both of those restrictions — let anything point at anything — and you have a graph.

A graph of six nodes

Six nodes, seven edges. No top, no bottom, no root — just things and the connections between them.

Notice A→B→D and A→C→D: two different routes to the same node. A tree can never do this.

The vocabulary

Word	Means
Node (or vertex)	A thing. A city, a person, a web page.
Edge	A connection between two nodes. A road, a friendship, a link.
Neighbour	Any node one edge away. `A`'s neighbours are `B` and `C`.
Degree	How many edges touch a node. `C` has degree 3.
Path	A sequence of nodes joined by edges. `A → C → E → F` is a path.
Cycle	A path that returns to where it started. `A → B → D → C → A` is one.
Connected	Every node is reachable from every other. Not all graphs are.
Directed	Edges are one-way arrows. Undirected edges go both ways.
Weighted	Each edge carries a number — distance, cost, time.

The two properties that decide everything

Before touching a graph problem, answer two questions. They change which algorithm is even correct.

Directed or undirected? A friendship is mutual — if you are my friend I am yours, so the edge goes both ways. "Follows on social media" is not mutual, so it needs an arrow. Get this wrong and you either invent connections that do not exist or lose half of them.

Same three nodes, two meanings

Directed: A can reach C by going through B. But C can reach nobody — every arrow points away from it.

If these edges were undirected, C could reach A just as easily. One property, opposite answers.

Cyclic or acyclic? This is the one that bites. A graph can lead you in a circle, so a walk that does not remember where it has been will loop forever.

Why a graph walk needs a memory

visited{A}

Start at A and walk to B.

1 / 4

A tree cannot do this, which is why tree code needs no visited set. In a graph it is not optional.

This is the single biggest difference from tree code

Tree traversal and graph traversal are the same algorithm, except graph traversal asks one extra question first: have I been here already?

Forget it and the program does not return a wrong answer — it hangs, or crashes with a stack overflow. That failure looks like a bug in your loop, and people spend a long time looking in the wrong place.

Where the graph comes from

In real problems you are rarely handed a picture. You are handed a list of pairs, and the graph is something you build.

n = 4,  edges = [[0,1], [0,2], [1,3]]

Becomes:
  0  →  [1, 2]
  1  →  [0, 3]
  2  →  [0]
  3  →  [1]

That mapping — node → list of its neighbours — is the adjacency list below. It is the shape almost every graph algorithm wants, because the question they ask over and over is "where can I go from here?"

Many problems are graphs in disguise

The word "graph" often never appears. These are all graphs:

Problem says	Nodes are	Edges are
A grid where you move up/down/left/right	Cells	Neighbouring cells
Courses with prerequisites	Courses	"must be taken before"
Words differing by one letter	Words	A single-letter change
Flights between airports	Airports	Routes

Spotting this is most of the work. Once it is a graph, the traversal is standard — a grid needs no adjacency list at all, since a cell's neighbours are just (r±1, c) and (r, c±1).

Representing a Graph

Representation	Space	"Is there an edge `u→v`?"	"List `u`'s neighbours"
Adjacency list	`O(V + E)`	`O(degree)`	`O(degree)`
Adjacency matrix	`O(V²)`	`O(1)`	`O(V)`
Edge list	`O(E)`	`O(E)`	`O(E)`

The adjacency list is the default. Matrices only pay off on dense graphs or when you constantly ask about specific pairs.

from collections import defaultdict


def build_graph(n: int, edges: list[list[int]]) -> dict[int, list[int]]:
    """Adjacency list for an undirected graph with nodes 0..n-1."""
    graph: defaultdict[int, list[int]] = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)   # drop this line for a directed graph

    return graph

Traversal

Both DFS and BFS work exactly as they do on trees, plus a visited set.

Here they are on the same graph, so the difference is visible rather than described.

BFS from A — closest first

queue[B, C]distance0

Start at A. Put both neighbours in the queue. Mark them visited NOW, as they go in — not when they come out.

1 / 6

Order visited: A, B, C, D, E, F — grouped by distance from the start.

DFS from A — one branch to the end

pathA

Start at A, take the first neighbour B. C is ignored for now — DFS commits to one direction.

1 / 6

Order visited: A, B, D, F, E, C. Same graph, same start, and C went from second to last.

Read those two side by side

	BFS	DFS
Container	Queue — oldest first	Stack / recursion — newest first
C is visited	3rd, at distance 1	6th, at distance 5
Shortest paths	Yes, on unweighted graphs	No
Memory used	Up to the widest level	Up to the longest path
Natural for	Fewest steps, level grouping	Connectivity, cycles, topological order

Both visit every reachable node exactly once, so both are O(V + E). They differ only in the order — and that order is the whole reason you pick one.

Mark nodes visited when you enqueue, not when you dequeue

In BFS, a node can be reached by several neighbours before it is processed. Marking it only on dequeue lets it enter the queue multiple times, which wastes work and can blow up exponentially on dense graphs. Mark it the moment you add it.

BFS finds the shortest path in an unweighted graph, because it explores in order of distance
DFS is the tool for connectivity, cycle detection and topological ordering

Not Every Graph Problem Needs a Traversal

Some problems are stated in graph language but answered by counting degrees — how many edges enter or leave each node.

Find the Town Judge — the judge is the unique node with in-degree n-1 and out-degree 0, found by one pass over the edges

Recognising this saves you from writing a traversal you did not need. When a problem describes a property in terms of "everyone trusts…", "nobody points to…", or "exactly one node has…", check whether degree counting settles it first.

All Problems

Problem	Difficulty	Pattern
Find the Town Judge	Easy	Degree Counting
Flood Fill	Easy	DFS on a grid
Number of Islands	Medium	Flood fill, repeated
Rotting Oranges	Medium	Multi-source BFS
Clone Graph	Medium	DFS with an identity map
Number of Provinces	Medium	Union-Find
Redundant Connection	Medium	Union-Find
Course Schedule	Medium	Topological sort

Suggested order

Flood Fill first — it is a grid traversal with nothing else going on, so the "mark it visited on arrival" rule is impossible to miss.

Then Number of Islands, which is that same fill run repeatedly. Rotting Oranges forces BFS specifically, because the answer is a distance. Clone Graph shows where a visited set is not enough and a visited map is required.

Binary Tree Level Order Traversal — BFS in its simplest setting
N-ary Tree Preorder Traversal — DFS, recursive and iterative
Jump Game II — BFS levels computed implicitly, with no queue at all

Graphs

On this page