Graphs

Nodes, edges, and not visiting anything twice.

The idea

A graph is nodes joined by edges. Trees are the special case with no cycles; the general case is where the visited set becomes mandatory, because without it a cycle means traversal never terminates.

Representation matters more than it first appears. An adjacency list — each node mapped to its neighbours — is O(V + E) space and iterating a node's neighbours is proportional to how many it has. An adjacency matrix is O(V²) regardless of edge count, but answers "is there an edge?" in constant time. Sparse graphs, which is most real ones, want the list.

The two traversals answer different questions:

Depth-first goes as deep as possible before backtracking. Natural recursively. Good for connectivity, cycle detection, topological order.
Breadth-first explores by distance from the start. Needs a queue. It is the only one of the two that finds the shortest path in an unweighted graph, because it reaches every node in order of distance.

Reaching for DFS when the question asks for a shortest path is the single most common graph mistake.

Walkthrough

Breadth-first over a row of cells: 1 is open, 0 is a wall. Each cell flips to 2 as it is reached, so the frontier is visible spreading outward until the wall stops it.

What it costs

time: O(V + E) for either traversal
space: O(V) for the visited set, plus the stack or queue

Every node and edge is examined at most once — but only because of the visited set. Without it, a single cycle makes the traversal infinite.

When to reach for it

The data is a network: friends, routes, dependencies, links.
The question is about reachability, connectivity, or a path between two things.
There are prerequisites or ordering constraints, which is a topological sort.
It looks like a tree problem but the structure can contain cycles.

Rather than the obvious alternative

Union-Find

Near-constant time for "same group?" but it cannot give you a path or a distance. Use it when connectivity is all you need; use a traversal when the route matters.

A tree

Simpler and needs no visited set — but only valid when the structure genuinely has no cycles. One cycle makes a tree traversal run forever.

A matrix of distances

Adjacency matrices cost O(V²) memory regardless of how many edges exist. For a sparse graph an adjacency list is dramatically smaller.

How to spot it

The data is a network: friends, routes, dependencies, links.
The problem asks about reachability, connectivity, or a path.
There are prerequisites or ordering constraints, which is topological sort.
It looks like a tree problem but the structure can contain cycles.

Where it goes wrong

No visited set

The defining difference from a tree. One cycle and the traversal never ends.

Marking visited too late

Mark on enqueue, not on dequeue. Otherwise the same node is queued several times before any of them is processed.

DFS for shortest paths

Depth-first finds *a* path, not the shortest. Unweighted shortest path is BFS; weighted is Dijkstra.

Practise it

Count Connected Componentsmedium
Number of Islandsmedium