Graphs

In many areas of life, we come across systems where elements are deeply interconnected, whether through physical routes, digital networks, or abstract relationships. Graphs offer a flexible way to represent and make sense of these connections.

The reason graphs matter isn’t that they describe connections, it’s that they let you reason about them. Once you turn a messy “web of relationships” into a graph, you can start asking precise questions: What’s the fastest route? What’s the weakest link? Who or what is most connected? What happens if this node fails? That’s why we say that graphs are a useful tool.

Some real-world examples include:

Underground tunnel networks (subways and transportation systems below the city surface)
Railway maps (train routes connecting different towns and cities)
Cities linked by flights (air travel routes between global destinations)
Networks of pipes (piping systems transporting water, gas, or oil)
Electrical grids (networks distributing electricity across regions)
Carbon atoms in a molecule (chemical compounds and the bonds between their constituent atoms)
Internet (webpages interlinked through hyperlinks or networks of computers)
Task scheduling (dependencies among tasks that determine their sequence or priority)
Spread of a disease (understanding how diseases propagate through populations)
Social networks (people connected through friendships, family ties, or professional relationships)
Countries and their political alliances (diplomatic ties, trade partnerships, or defense pacts between nations)

Viewing these systems as graphs lets us dig deeper into how they work, optimize them better, and even predict their behavior more accurately. In fields like computer science and math, graphs are a powerful tool that helps us model and understand these systems effectively.

A helpful way to think about this is: graphs are a “universal adapter.” They don’t care whether your nodes are cities, atoms, or tasks. If you can describe “things” and “relationships,” you can model it as a graph, and suddenly a huge library of algorithms becomes available to you.

Throughout the algorithm sections, $V$ and $E$ denote the numbers of vertices and edges in complexity bounds, while $V(G)$ and $E(G)$ denote the sets themselves. Space bounds exclude the input graph unless stated otherwise. Examples use explicit edge lists as the source of truth for weights and directions.

Graph Terminology

Graph theory has its own language, full of terms that make it easier to talk about and define different types of graphs and their features. Here's an explanation of some important terms:

This vocabulary isn’t just academic; it’s how you avoid confusion later. Graph problems often look similar on the surface, but one word, directed, weighted, connected, can completely change which algorithms work and which ones fail. Learning the terms is like learning traffic signs before driving.

A graph $G$ is a mathematical structure composed of vertices (also known as nodes or points), forming the set $V(G)$, and edges (also called links or lines), forming the set $E(G)$. In a simple undirected graph, an edge is an unordered pair ${x,y}$ of distinct vertices. Directed edges are ordered pairs $(x,y)$; more general graphs may allow self-loops and parallel edges.
When two vertices, say $x$ and $y$, share an edge, they are termed adjacent. In a simple undirected graph, its degree counts its neighbors. More generally, degree counts incident edge ends, with a self-loop counted twice, so the degree sum is $2|E|$. Directed graphs instead have indegree and outdegree, each summing to $|E|$.
A path of length $n$ is a sequence of vertices $v_1 \sim v_2 \sim \cdots \sim v_{n+1}$, each consecutively connected by edges, with no vertex repeated.
A cycle is a closed sequence of edges where the first and last vertices are identical, forming a closed loop, and no other vertex is repeated within the cycle.
Distance in a graph refers to the shortest path length between two vertices. In an unweighted graph this is the minimum number of edges. In a weighted graph, distance minimizes the sum of edge weights, when a finite shortest distance exists.
A simple graph is characterized by the absence of self-loops, edges that connect vertices to themselves, and contains no more than one edge between any two distinct vertices.
A directed graph (or digraph) includes edges with specific directions, known as arcs, represented as ordered pairs of vertices. Conversely, an undirected graph treats connections symmetrically, meaning the connection between vertices $A$ and $B$ is identical to the one from $B$ to $A$.
A weighted graph assigns numerical values (weights) to edges, which may be positive, zero, or negative and may be nonintegral. An unweighted adjacency matrix uses 0 and 1 for absence and presence; these indicators differ from genuine edge weights of 0 and 1. Numeric weights quantify costs or strengths; and normalized weights scale outgoing connections from a vertex to sum to one, commonly used in probability models.
Regarding connectivity, an undirected graph is connected if there's a path linking any pair of vertices. For directed graphs, weak connectivity means the graph becomes connected when edge directions are ignored, while strong connectivity demands a path in both directions between every vertex pair.
Two vertices connected by an edge are called neighbors, and the edge itself is said to be incident to these vertices. Edges sharing a common vertex are described as adjacent edges.
An isolated vertex refers to a vertex with no connecting edges, hence having a degree of zero and no neighbors.
Subgraphs are smaller structures derived from selecting subsets of vertices and edges from a larger graph. Formally, a subgraph $H$ of a graph $G$ has vertex and edge sets entirely contained within those of $G$.
A spanning tree of a graph $G$ is a subgraph that connects all vertices using the minimal number of edges required, specifically $|V| - 1$ edges, and contains no cycles.
Bipartite graphs partition vertices into two distinct groups such that no edges connect vertices within the same group. Formally, a graph is bipartite if it can be split into sets $V_1$ and $V_2$ where each edge links vertices across the two sets only.
A complete graph, denoted by $K_n$, is a simple graph with an edge between every possible pair of vertices. Thus, a complete graph with $n$ vertices contains exactly $\frac{n(n-1)}{2}$ edges.
Planar graphs are graphs that can be drawn on a flat plane without edge intersections except at vertices. Such graphs can be embedded clearly onto a two-dimensional surface without visual confusion.
An Eulerian trail (often called an Eulerian path) uses every edge exactly once and may revisit vertices. In an undirected graph with at least one edge, all non-isolated vertices must belong to one connected component. Under that condition, a circuit exists exactly when all degrees are even; an open trail exists exactly when two degrees are odd. Directed graphs require separate indegree/outdegree conditions.
A Hamiltonian path traverses every vertex exactly once. If such a path returns to its starting vertex, it becomes a Hamiltonian circuit. The decision about the existence of Hamiltonian paths or circuits is notably difficult and classified as an NP-complete problem.
Graph isomorphism describes two graphs, $G$ and $H$, that are structurally identical despite potentially different vertex or edge labels. Formally, an isomorphism is a one-to-one correspondence preserving adjacency between their vertex sets.
The degree sequence of a graph lists all vertex degrees, typically ordered from highest to lowest. This sequence serves as a graph invariant, meaning it is consistent across isomorphic graphs.
Graph coloring involves assigning different labels or "colors" to adjacent vertices. The minimum number of colors required to color a graph without adjacent vertices sharing the same color is called the chromatic number.
A tree is a connected graph with no cycles. It possesses a unique path between every pair of vertices, and adding any extra edge will inevitably create a cycle. Trees are important in many computational applications, especially algorithms and data structures.
A forest consists of multiple disconnected trees. It's essentially an acyclic graph that isn't necessarily connected, serving as a generalization of trees.
Regarding connectivity, a vertex whose removal increases the number of disconnected parts is an articulation vertex (or cut vertex). Similarly, an edge whose removal disconnects the graph is called a bridge or cut edge.
A matching in a graph is a set of edges with no shared vertices. A maximum matching is the largest possible such set.
An independent set is a vertex set with no edges connecting any two vertices. The largest size of such a set is known as the independence number.
A clique is a subset of vertices in which each vertex connects directly to all others. The largest clique size is called the clique number.
A vertex cover is a collection of vertices such that every graph edge touches at least one vertex from the collection.
These notions are related through graph complementation: a clique in $G$ is an independent set in its complement. A set is a vertex cover exactly when the remaining vertices form an independent set.
Planarity testing checks if a graph can be drawn without intersecting edges. Kuratowski’s theorem states that non-planarity occurs precisely when a graph contains a subdivision of $K_5$ (complete graph of five vertices) or $K_{3,3}$ (complete bipartite graph).
Common algorithms on graphs include methods for finding shortest paths (Bellman-Ford, Dijkstra's algorithm), discovering minimum spanning trees (Kruskal’s, Prim’s algorithm), and graph traversal (DFS, BFS). These algorithms help solve important graph-related problems in computing and operations research.

A quick “do/don’t” that saves a lot of pain: always decide early whether your edges are directed and/or weighted. Many beginner mistakes come from using the right algorithm on the wrong kind of graph (for example, treating one-way roads as two-way, or ignoring weights when “shortest” actually means “cheapest,” not “fewest steps”).

Representation of Graphs in Computer Memory

Graphs show how things are connected. To work with them on a computer, we need a good way to store and update those connections. The “right” choice depends on what the graph looks like (dense or sparse, directed or undirected, weighted or not) and what you plan to do with it. In practice, most people use one of two formats: an adjacency matrix or an adjacency list.

This choice matters because it quietly determines performance. Two programs can run the same algorithm and get the same answers, but one finishes in milliseconds while the other crawls, purely because the graph was stored in a form that made common operations expensive.

Adjacency Matrix

An adjacency matrix represents a graph $G$ with $V$ vertices as a two-dimensional matrix $A$ of size $V \times V$. The rows and columns correspond to vertices, and each cell $A_{ij}$ holds:

1 if there is an edge between vertex $i$ and vertex $j$ (or specifically $i \to j$ in a directed graph)
0 if no such edge exists
For weighted graphs, $A_{ij}$ contains the weight of the edge; use ∞ or None for “no edge” if zero-weight edges are allowed

Same graph used throughout (undirected 4-cycle A–B–C–D–A):

(A)------(B)
 |        |
 |        |
(D)------(C)

Matrix (table form):

	A	B	C	D
A	0	1	0	1
B	1	0	1	0
C	0	1	0	1
D	1	0	1	0

Here, the matrix indicates a graph with vertices A to D. For instance, vertex A connects with vertices B and D, hence the respective 1s in the matrix.

Matrix:

4x4
            Columns →
          A   B   C   D
        +---+---+---+---+
Row   A | 0 | 1 | 0 | 1 |
↓     B | 1 | 0 | 1 | 0 |
      C | 0 | 1 | 0 | 1 |
      D | 1 | 0 | 1 | 0 |
        +---+---+---+---+

Notes & Variants

When an undirected graph is represented, the adjacency matrix is symmetric because the connection from node $i$ to node $j$ also implies a connection from node $j$ to node $i$; if this property is omitted, the matrix will misrepresent mutual relationships, such as a road existing in both directions between two cities.
In the case of a directed graph, the adjacency matrix does not need to be symmetric since an edge from node $i$ to node $j$ does not guarantee a reverse edge; without this rule, one might incorrectly assume bidirectional links, such as mistakenly treating a one-way street as two-way.
A self-loop appears as a nonzero entry on the diagonal of the adjacency matrix, indicating that a node is connected to itself; if ignored, the representation will overlook scenarios like a website containing a hyperlink to its own homepage.

Benefits

An edge existence check in an adjacency matrix takes constant time $O(1)$ because the presence of an edge is determined by directly inspecting a single cell; if this property is absent, the lookup could require scanning a list, as in adjacency list representations where finding whether two cities are directly connected may take longer.
With simple, compact indexing, the adjacency matrix aligns well with array-based structures, which makes it helpful for GPU optimizations or bitset operations; without this feature, algorithms relying on linear algebra techniques, such as computing paths with matrix multiplication, become less efficient.

Drawbacks

The space requirement of an adjacency matrix is always $O(V^2)$, meaning memory usage grows with the square of the number of vertices even if only a few edges exist; if this property is overlooked, sparse networks such as social graphs with millions of users but relatively few connections will be stored inefficiently.
For neighbor iteration, each vertex requires $O(V)$ time because the entire row of the matrix must be scanned to identify adjacent nodes; without recognizing this cost, tasks like finding all friends of a single user in a large social network could become unnecessarily slow.

Common Operations (Adjacency Matrix)

Operation	Time
Check if edge $u\leftrightarrow v$	$O(1)$
Add/remove edge	$O(1)$
Iterate neighbors of $u$	$O(V)$
Compute degree of $u$ (undirected)	$O(V)$
Traverse all edges	$O(V^2)$

Space Tips

Using a boolean or bitset matrix allows each adjacency entry to be stored in just one bit, which reduces memory consumption by a factor of eight compared to storing each entry as a byte; if this method is not applied, representing even moderately sized graphs, such as a network of 10,000 nodes, can require far more storage than necessary.
The approach is most useful when the graph is dense, the number of vertices is relatively small, or constant-time edge queries are the primary operation; without these conditions, such as in a sparse graph with millions of vertices, the $V^2$ bit requirement remains wasteful and alternative representations like adjacency lists become more beneficial.

A good way to “feel” adjacency matrices is to imagine a spreadsheet of all possible connections. That’s why they shine when you constantly ask “Is there an edge between u and v?”, but also why they get expensive when most of the spreadsheet is empty.

Adjacency List

An adjacency list stores, for each vertex, the list of its neighbors. It’s usually implemented as an array/vector of lists (or vectors), hash sets, or linked structures. For weighted graphs, each neighbor entry also stores the weight.

Same graph (A–B–C–D–A) as lists:

A -> [B, D]
B -> [A, C]
C -> [B, D]
D -> [A, C]

“In-memory” view (array of heads + per-vertex chains):

Vertices (index) →   0     1     2     3
Names              [ A ] [ B ] [ C ] [ D ]
                     |     |     |     |
                     v     v     v     v
A-list:  head -> [B] -> [D] -> NULL
B-list:  head -> [A] -> [C] -> NULL
C-list:  head -> [B] -> [D] -> NULL
D-list:  head -> [A] -> [C] -> NULL

Variants & Notes

In an undirected graph stored as adjacency lists, each edge is represented twice, once in the list of each endpoint, so that both directions can be traversed easily; if this duplication is omitted, traversing from one node to its neighbor may be possible in one direction but not in the other, as with a friendship relation that should be mutual but is stored only once.
For a directed graph, only out-neighbors are recorded in each vertex’s list, meaning that edges can be followed in their given direction; without a separate structure for in-neighbors, tasks like finding all users who link to a webpage require inefficient scanning of every adjacency list.
In a weighted graph, each adjacency list entry stores both the neighbor and the associated weight, such as $(\text{destination}, \text{distance})$; if weights are not included, algorithms like Dijkstra’s shortest path cannot be applied correctly.
The order of neighbors in adjacency lists may be arbitrary, though keeping them sorted allows faster checks for membership; if left unsorted, testing whether two people are directly connected in a social network could require scanning the entire list rather than performing a quicker search.

Benefits

The representation is space-efficient for sparse graphs because it requires $O(V+E)$ storage, growing only with the number of vertices and edges; without this property, a graph with millions of vertices but relatively few edges, such as a road network, would consume far more memory if stored as a dense matrix.
For neighbor iteration, the time cost is $O(\deg(u))$, since only the actual neighbors of vertex $u$ are examined; if this benefit is absent, each query would need to scan through all possible vertices, as happens in adjacency matrices when identifying a node’s connections.
In edge traversals and searches, adjacency lists support breadth-first search and depth-first search efficiently on sparse graphs because only existing edges are processed; without this design, traversals would involve wasted checks on non-edges, making exploration of large but sparsely connected networks, like airline routes, much slower.

Drawbacks

An edge existence check in adjacency lists requires $O(\deg(u))$ time in the worst case because the entire neighbor list may need to be scanned; if a hash set is used for each vertex, the expected time improves to $O(1)$, though at the cost of extra memory and overhead, as seen in fast membership tests within large social networks.
With respect to cache locality, adjacency lists often rely on pointers or scattered memory, which reduces their efficiency on modern hardware; without this drawback, as in dense matrix storage, sequential memory access patterns make repeated operations such as matrix multiplication more beneficial.

Common Operations (Adjacency List)

Operation	Time (typical)
Check if edge $u\leftrightarrow v$	$O(\deg(u))$ (or expected $O(1)$ with hash)
Add edge	Amortized $O(1)$ (append to list(s))
Remove edge	$O(\deg(u))$ directed; $O(\deg(u)+\deg(v))$ undirected
Iterate neighbors of $u$	$O(\deg(u))$
Traverse all edges	$O(V + E)$

The choice between these (and other) representations often depends on the graph's characteristics and the specific tasks or operations envisioned.

Choosing an adjacency matrix is helpful when the graph is dense, the number of vertices is moderate, and constant-time edge queries or linear-algebra formulations are beneficial; if this choice is ignored, operations such as repeatedly checking flight connections in a fully connected air network may become slower or harder to express mathematically.
Opting for an adjacency list is useful when the graph is sparse or when neighbor traversal dominates, as in breadth-first search or shortest-path algorithms; without this structure, exploring a large but lightly connected road network would waste time scanning nonexistent edges.

A simple “do”: pick the representation that makes your most common operation cheap. If your algorithm spends most of its time iterating neighbors, adjacency lists are usually the happy path. If it spends most of its time checking whether edges exist, matrices can be surprisingly effective.

Hybrids/Alternatives:

With CSR/CSC (Compressed Sparse Row/Column) formats, all neighbors of a vertex are stored contiguously in memory, which improves cache locality and enables fast traversals; without this layout, as in basic pointer-based adjacency lists, high-performance analytics on graphs like web link networks would suffer from slower memory access.
An edge list stores edges simply as $(u,v)$ pairs, making it convenient for graph input, output, and algorithms like Kruskal’s minimum spanning tree; if used for queries such as checking whether two nodes are adjacent, the lack of structure forces scanning the entire list, which becomes inefficient in large graphs.
In hash-based adjacency structures, each vertex’s neighbor set is managed as a hash table, enabling expected $O(1)$ membership tests; without this tradeoff, checking connections in dense social networks requires linear scans, while the hash-based design accelerates lookups at the cost of extra memory.

Planarity

Planarity asks: can a graph be drawn on a flat plane so that edges only meet at their endpoints (no crossings)?

Why it matters: layouts of circuits, road networks, maps, and data visualizations often rely on planar drawings.

Planarity is one of those ideas that sounds like “just drawing,” but it has real consequences. If a graph is non-planar, then any attempt to draw it cleanly in 2D will eventually hit unavoidable clutter. For things like circuit design, that clutter can mean extra layers, extra cost, and harder debugging, so planarity becomes a practical constraint, not a visual preference.

What is a planar graph?

A graph is planar if it has some drawing in the plane with no edge crossings. A messy drawing with crossings doesn’t disqualify it, if you can redraw it without crossings, it’s planar.

A crossing-free drawing of a planar graph is called a planar embedding (or plane graph once embedded).
In a planar embedding, the plane is divided into faces (regions), including the unbounded outer face.

Euler’s Formula (connected planar graphs):

$$ |V| - |E| + |F| = 2 $$

$$ \text{(for (c) connected components: } |V|-|E|+|F|=1+c) $$

Euler’s formula is more than a neat identity: it’s a quick reality check. If your counts can’t possibly satisfy it (given the constraints for planar graphs), you already know something must give, either your assumption of planarity is wrong, or your representation is incomplete.

Kuratowski’s & Wagner’s characterizations

According to Kuratowski’s Theorem, a graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ or $K_{3,3}$; if this condition is not respected, as in a network with five nodes all mutually connected, the graph cannot be drawn on a plane without edge crossings.
By Wagner’s Theorem, a graph is planar if and only if it has no $K_5$ or $K_{3,3}$ minor, meaning such structures cannot be formed through edge deletions, vertex deletions, or edge contractions; without ruling out these minors, a graph like the complete bipartite structure of three stations each linked to three others cannot be embedded in the plane without overlaps.

These are equivalent “forbidden pattern” views.

The “do” here is to look for structure, not literal pictures. You don’t need to see a perfect $K_5$ sitting in your graph; you need to spot the ways a graph can collapse into one via contractions or subdivisions. That’s why these theorems are powerful: they tell you exactly what kind of complexity ruins planarity.

Handy planar edge bounds (quick tests)

For a simple planar graph with $|V|\ge 3$:

$|E| \le 3|V| - 6$.
If the graph is bipartite, then $|E| \le 2|V| - 4$.

These give fast non-planarity proofs:

$K_5$: $|V|=5, |E|=10 > 3\cdot5-6=9$ ⇒ non-planar.
$K_{3,3}$: $|V|=6, |E|=9 > 2\cdot6-4=8$ ⇒ non-planar.

These bounds are the “quick detective test.” They won’t prove a graph is planar, but they can often prove it’s not planar instantly, especially when graphs get dense. That’s incredibly useful when you want a fast answer before investing time in more complex checks.

Examples

I. Cycle graphs $C_n$ (always planar)

A 4-cycle $C_4$:

A───B
│   │
D───C

No crossings; faces: 2 (inside + outside).

II. Complete graph on four vertices $K_4$ (planar)

A planar embedding places one vertex inside a triangle:

      A
     /|\
    / D \
   / / \ \
  B-------C

All edges meet only at vertices; no crossings.

III. Complete graph on five vertices $K_5$ (non-planar)

No drawing of all ten edges avoids crossings. An explicit edge list prevents a partial sketch from hiding missing edges:

AB, AC, AD, AE, BC, BD, BE, CD, CE, DE

The edge bound $10>9$ (above) certifies non-planarity.

IV. Complete bipartite graph $K_{3,3}$ (non-planar)

The complete bipartite graph $K_{3,3}$ consists of two disjoint vertex sets ${u_1, u_2, u_3}$ and ${v_1, v_2, v_3}$. Every vertex $u_i$ is connected to every vertex $v_j$, and there are no edges within a set.

Structure of (K_{3,3})

u1      u2      u3
|  \  /  |  \  / |
|   \    |   \   |
| /   \  | /   \ |
v1      v2      v3

This diagram represents all 9 edges:

(u_1)–(v_1, v_2, v_3)
(u_2)–(v_1, v_2, v_3)
(u_3)–(v_1, v_2, v_3)

(Edge crossings are unavoidable in any planar drawing.)

Proof of non-planarity

Number of vertices:

$$ v = 6 $$

Number of edges:

$$ e = 9 $$

Because $K_{3,3}$ is bipartite, it has no odd cycles. For any planar bipartite graph with $v \ge 3$, the edge bound is:

$$ e \le 2v - 4 $$

Substituting $v = 6$:

$$e \le 2(6) - 4 = 8$$

But $K_{3,3}$ has $e = 9$, so:

$$9 > 8$$

These examples also build intuition: some graphs “want” to live on a plane (cycles, $K_4$), while others contain too much cross-connection pressure ($K_5$, $K_{3,3}$). When you feel that pressure, you start recognizing non-planarity before doing any formal proof.

How to check planarity in practice

For small graphs

Rearrange vertices and try to remove crossings.
Look for $K_5$ / $K_{3,3}$ (or their subdivisions/minors).
Apply the edge bounds above for quick eliminations.

For large graphs (efficient algorithms)

The Hopcroft–Tarjan algorithm uses a depth-first search approach to decide planarity in linear time; without such an efficient method, testing whether a circuit layout can be drawn without wire crossings would take longer on large graphs.
Boyer–Myrvold can test planarity and produce a combinatorial embedding or a non-planarity certificate in linear time for simple graphs. An embedding specifies cyclic edge order around vertices; assigning drawing coordinates is a separate task. See the Boost Graph documentation.

Both are widely used in graph drawing, EDA (circuit layout), GIS, and network visualization.

The key practical point is that planarity testing isn’t just theoretical, it’s something real tools rely on. If software can quickly decide planarity (and even produce an embedding), it can automatically generate cleaner diagrams and layouts instead of leaving you to manually untangle crossings.

Traversals

What does it mean to traverse a graph?

Graph traversal can be done in a way that visits all vertices and edges (like a full DFS/BFS), but it doesn’t have to.

From one source, DFS or BFS visits the vertices reachable from it. In an undirected graph this is its connected component; in a directed graph it need not be an entire weak or strong component.
Some algorithms (like shortest path searches, A*, or even partial DFS) intentionally stop early, meaning not all vertices or edges are visited.
In weighted or directed graphs, you may also skip certain edges depending on the traversal rules.

So the precise way to answer that question is:

Graph traversal is a systematic way of exploring vertices and edges, often ensuring complete coverage of the reachable part of the graph: but whether all vertices/edges are visited depends on the algorithm and stopping conditions.

Traversal is the heartbeat of graph algorithms. Almost everything you do on a graph, finding components, shortest paths, detecting cycles, building spanning trees, starts with “walk the graph in a disciplined way.” If graphs are the map, traversal is how you actually move through the territory.

Graphs, unlike trees, don’t have a single starting point like a root. This means we either need to be given a starting vertex or pick one randomly.
Let’s say we start from a specific vertex, like $i$. From there, the traversal explores all connected vertices according to the rules of the chosen method.
In both breadth-first search (BFS) and depth-first search (DFS), the order of visiting vertices depends on how the algorithm is implemented.
For example, if the starting vertex A has three neighbors, like $C, F,$ and $G$, the algorithm doesn’t have a fixed rule for which neighbor to visit first. It could choose any of them based on the way it’s programmed.
Because of this flexibility, we talk about a result of BFS or DFS, rather than the result, since different implementations might visit vertices in different orders.

A useful “do” before you choose BFS vs DFS: decide what “close” means in your problem. If “close” means fewest edges, BFS naturally fits. If “close” means “go deep and explore structure,” DFS often fits better. Choosing the traversal is choosing the shape of your exploration.

Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level from a specified start vertex. It first visits all vertices at distance 1 from the start, then all vertices at distance 2, and so on. This makes BFS the natural choice whenever “closest in number of edges” matters.

First step: Build an adjacency list from the edge list, adding both directions if the graph is undirected. Decide whether you need only reachability, the distance in edges (keep a dist map), or the actual path (keep a parent map), and mark the start as visited before the loop begins.

To efficiently keep track of the traversal, BFS employs two primary data structures:

A queue (often named queue or unexplored) that stores vertices pending exploration in first-in, first-out (FIFO) order.
A visited set (or boolean array) that records which vertices have already been discovered to prevent revisiting.

Useful additions in practice:

An optional parent map to reconstruct shortest paths (store parent[child] = current when you first discover child).
An optional dist map to record the edge-distance from the start (dist[start] = 0, and when discovering v from u, set dist[v] = dist[u] + 1).

BFS feels like ripples in water: start at one node and expand outward in rings. That “ripple” behavior is exactly why BFS gives shortest paths in unweighted graphs, because the first time you reach a node is guaranteed to be via the fewest edges.

Algorithm Steps:

Pick a start vertex $i$.
Set visited = {i}, parent[i] = None, optionally dist[i] = 0, and enqueue $i$ into queue.
While queue is nonempty, repeat steps 4–5.
Dequeue the front vertex u.
For each neighbor v of u, if v is not in visited, add it to visited, set parent[v] = u (and dist[v] = dist[u] + 1 if tracking), and enqueue v.
Stop when the queue is empty.

Marking nodes as visited at the moment they are enqueued (not when dequeued) is crucial: it prevents the same node from being enqueued multiple times in graphs with cycles or multiple incoming edges.

Reference pseudocode (adjacency-list graph):

BFS(G, i):
    visited = {i}
    parent  = {i: None}
    dist    = {i: 0}            # optional
    queue   = deque([i])

    order = []                  # optional: visitation order

    while queue:
        u = queue.popleft()
        order.append(u)

        for v in G[u]:          # iterate neighbors
            if v not in visited:
                visited.add(v)
                parent[v] = u
                dist[v] = dist[u] + 1   # if tracking
                queue.append(v)

    return order, parent, dist

Sanity notes:

The time complexity of breadth-first search is $O(V+E)$ because each vertex is enqueued once and each edge is examined once; if this property is overlooked, one might incorrectly assume that exploring a large social graph requires quadratic time rather than scaling efficiently with its size.
The space requirement is $O(V)$ since the algorithm maintains a queue and a visited array, with optional parent or distance arrays if needed; without accounting for this, applying BFS to a network of millions of nodes could be underestimated in memory cost.
The order in which BFS visits vertices depends on the neighbor iteration order, meaning that traversal results can vary between implementations; if this variation is not recognized, two runs on the same graph, such as exploring a road map, may appear inconsistent even though both are correct BFS traversals.

Example

Graph (undirected) with start at A:

#
   ┌─────┐
   │  A  │
   └──┬──┘
  ┌───┘ └───┐
┌─▼─┐     ┌─▼─┐
│ B │     │ C │
└─┬─┘     └─┬─┘
┌─▼─┐     ┌─▼─┐
│ D │     │ E │
└───┘     └───┘

Edges: A–B, A–C, B–D, C–E

Queue/Visited evolution (front → back):

Step | Dequeued | Action                                    | Queue            | Visited
-----+----------+-------------------------------------------+------------------+----------------
0    | ,         | enqueue A                                 | [A]              | {A}
1    | A        | discover B, C; enqueue both               | [B, C]           | {A, B, C}
2    | B        | discover D; enqueue                       | [C, D]           | {A, B, C, D}
3    | C        | discover E; enqueue                       | [D, E]           | {A, B, C, D, E}
4    | D        | no new neighbors                          | [E]              | {A, B, C, D, E}
5    | E        | no new neighbors                          | []               | {A, B, C, D, E}

BFS tree and distances from A:

dist[A]=0
A → B (1), A → C (1)
B → D (2), C → E (2)

Parents: parent[B]=A, parent[C]=A, parent[D]=B, parent[E]=C
Shortest path A→E: backtrack E→C→A  ⇒  A - C - E

Applications

In shortest path computation on unweighted graphs, BFS finds the minimum number of edges from a source to all reachable nodes and allows path reconstruction via a parent map; without this approach, one might incorrectly use Dijkstra’s algorithm, which adds unnecessary priority-queue overhead for unweighted networks such as social connections.
For identifying connected components in undirected graphs, BFS is run repeatedly from unvisited vertices, with each traversal discovering one full component; without this method, components in a road map or friendship network may remain undetected.
When modeling broadcast or propagation, BFS naturally mirrors wavefront-like spreading, such as message distribution or infection spread; ignoring this property makes it harder to simulate multi-hop communication in networks.
During BFS-based cycle detection in undirected graphs, encountering a visited neighbor that is not the current vertex’s parent signals a cycle; without this check, cycles in structures like utility grids may be overlooked.
For bipartite testing, BFS alternates colors by level, and the appearance of an edge connecting same-colored nodes disproves bipartiteness; without this strategy, verifying whether a task-assignment graph can be split into two groups becomes more complicated.
In multi-source searches, initializing the queue with several start nodes at distance zero allows efficient nearest-facility queries, such as finding the closest hospital from multiple candidate sites; without this, repeated single-source BFS runs would be less efficient.
In topological sorting of DAGs, a BFS-like procedure processes vertices of indegree zero using a queue, producing a valid ordering; a DFS-based topological sort has the same $O(V+E)$ asymptotic time.

Implementation:

C++
Python

Implementation tip: For dense graphs or when memory locality matters, an adjacency matrix can be used, but the usual adjacency list representation is more space- and time-efficient for sparse graphs.

A practical “do” for BFS code: use a real queue (like collections.deque in Python) instead of pop(0) on a list, because list dequeues are $O(n)$. The algorithm stays BFS either way, but performance can change drastically on large graphs.

Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Starting from a source vertex, it dives down one neighbor, then that neighbor’s neighbor, and so on, only backing up when it runs out of new vertices to visit.

First step: Build the adjacency list and decide what the DFS has to report: reachability, a component label, a cycle, or a post-order. If the graph can be a long chain (around $10^4$ vertices or more), plan for the iterative form or a raised recursion limit before you start.

To track the traversal efficiently, DFS typically uses:

A call stack via recursion or an explicit stack data structure (LIFO).
A visited set (or boolean array) to avoid revisiting vertices.

Useful additions in practice:

A parent map to reconstruct paths and build the DFS tree (parent[child] = current on discovery).
Optional timestamps (tin[u] on entry, tout[u] on exit) to reason about edge types, topological order, and low-link computations.
Optional order lists: pre-order (on entry) and post-order (on exit).

DFS is the explorer’s walk: pick a direction, go until you can’t, then backtrack and try the next path. That “go deep first” behavior is why DFS is so useful for structure: it naturally builds trees, reveals cycles, and powers classic algorithms like topological sort and strongly connected components.

Algorithm Steps:

Pick a start vertex $i$.
Initialize visited[v]=False for all $v$; optionally set parent[v]=None; set a global timer t=0.
Start a DFS from $i$ (recursive or with an explicit stack).
On entry to a vertex $u$: set visited[u]=True, record tin[u]=t++ (and keep parent[u]=None if $u=i$).
Scan neighbors $v$ of $u$; whenever visited[v]=False, set parent[v]=u and visit $v$ (recurse/push), then resume scanning $u$’s neighbors.
After all neighbors of $u$ are processed, record tout[u]=t++ and backtrack (return or pop).
When the DFS from $i$ finishes, if any vertex remains unvisited, choose one and repeat steps 4–6 to cover disconnected components.
Stop when no unvisited vertices remain.

The recursive version marks on entry. The stack-only version below marks on pop and discards duplicate pending entries. To reproduce recursive discovery and finish events with $O(V)$ stack space, store neighbor iterators in explicit stack frames.

The following DFS examples explore the source's reachable vertices. To cover the entire graph, repeat from unvisited vertices while keeping the same visited set. In a directed graph, this produces a DFS forest rather than identifying strongly connected components by itself.

Pseudocode (recursive, adjacency list):

DFS(G, i):
    time = 0
    visited = set()
    parent  = {i: None}
    tin     = {}
    tout    = {}
    pre     = []       # optional: order on entry
    post    = []       # optional: order on exit

    def explore(u):
        nonlocal time
        visited.add(u)
        time += 1
        tin[u] = time
        pre.append(u)               # preorder

        for v in G[u]:
            if v not in visited:
                parent[v] = u
                explore(v)

        time += 1
        tout[u] = time
        post.append(u)              # postorder

    explore(i)
    return pre, post, parent, tin, tout

Pseudocode (iterative, traversal order only):

DFS_iter(G, i):
    visited = set()
    parent  = {i: None}
    order   = []
    stack   = [(i, None)]

    while stack:
        u, predecessor = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        parent[u] = predecessor
        order.append(u)

        # Push neighbors in reverse of desired visiting order
        for v in reversed(G[u]):
            if v not in visited:
                stack.append((v, u))

    return order, parent

Sanity notes:

The time complexity of DFS is $O(V+E)$ because every vertex and edge is processed a constant number of times; if this property is ignored, one might incorrectly assume exponential growth when analyzing networks like citation graphs.
Recursive DFS uses $O(V)$ auxiliary space for marks and the call stack. The simple iterative version shown can hold $O(E)$ pending entries, so its bound is $O(V+E)$. A stack of neighbor iterators avoids duplicates and uses $O(V)$ space. Deep recursive traversals can exceed the language's stack limit.

Example

Same graph as the BFS section, start at A; assume neighbor order: B before C, and for B the neighbor D; for C the neighbor E.

#
           ┌─────────┐
           │    A    │
           └───┬─┬───┘
               │ │
     ┌─────────┘ └─────────┐
     ▼                     ▼
┌─────────┐           ┌─────────┐
│    B    │           │    C    │
└───┬─────┘           └───┬─────┘
    │                     │
    ▼                     ▼
┌─────────┐           ┌─────────┐
│    D    │           │    E    │
└─────────┘           └─────────┘

Edges: A–B, A–C, B–D, C–E  (undirected)

Recursive DFS trace (pre-order):

call DFS(A)
  visit A
    -> DFS(B)
         visit B
           -> DFS(D)
                visit D
                return D
         return B
    -> DFS(C)
         visit C
           -> DFS(E)
                visit E
                return E
         return C
  return A

Discovery/finish times (one valid outcome):

Vertex | tin | tout | parent
-------+-----+------+---------
A      |  1  | 10   | None
B      |  2  |  5   | A
D      |  3  |  4   | B
C      |  6  |  9   | A
E      |  7  |  8   | C

Stack/Visited evolution (iterative DFS, top = right):

Step | Action                       | Stack                 | Visited
-----+------------------------------+-----------------------+-----------------
0    | push A                       | [A]                   | {}
1    | pop A; visit                 | []                    | {A}
     | push C, B                    | [C, B]                | {A}
2    | pop B; visit                 | [C]                   | {A, B}
     | push D                       | [C, D]                | {A, B}
3    | pop D; visit                 | [C]                   | {A, B, D}
4    | pop C; visit                 | []                    | {A, B, D, C}
     | push E                       | [E]                   | {A, B, D, C}
5    | pop E; visit                 | []                    | {A, B, D, C, E}

DFS tree (tree edges shown), with preorder: A, B, D, C, E

A
├── B
│   └── D
└── C
    └── E

Applications

In path existence and reconstruction, DFS records parent links so that after reaching a target node, the path can be backtracked to the source; without this, finding an explicit route through a maze-like graph would require re-running the search.
For topological sorting of DAGs, running DFS and outputting vertices in reverse postorder yields a valid order; if this step is omitted, dependencies in workflows such as build systems cannot be properly sequenced.
During cycle detection, DFS in undirected graphs reports a cycle when a visited neighbor is not the parent, while in directed graphs the discovery of a back edge to an in-stack node reveals a cycle; without these checks, feedback loops in control systems or task dependencies may go unnoticed.
To identify connected components in undirected graphs, DFS is launched from every unvisited vertex, with each traversal discovering one component; without this method, clusters in social or biological networks remain hidden.
Using low-link values in DFS enables detection of bridges (edges whose removal disconnects the graph) and articulation points (vertices whose removal increases components); if these are not identified, critical links in communication or power networks may be overlooked.
In strongly connected components of directed graphs, algorithms like Tarjan’s and Kosaraju’s use DFS to group vertices where every node is reachable from every other; ignoring this method prevents reliable partitioning of web link graphs or citation networks.
For backtracking and state-space search, DFS systematically explores decision trees and reverses when hitting dead ends, as in solving puzzles like Sudoku or N-Queens; without DFS, these problems would be approached less efficiently with blind trial-and-error.
With edge classification in directed graphs, DFS timestamps allow edges to be labeled as tree, back, forward, or cross, which helps analyze structure and correctness; without this classification, reasoning about graph algorithms such as detecting cycles or proving properties becomes more difficult.

Implementation:

C++
Python

Implementation tips:

For very deep or skewed graphs, prefer the iterative form to avoid recursion limits.
If neighbor order matters (e.g., lexicographic traversal), control push order (push in reverse for stacks) or sort adjacency lists.
For sparse graphs, adjacency lists are preferred over adjacency matrices for time/space efficiency.

Common BFS and DFS Patterns

Most interview graph problems are a plain BFS or DFS with one twist. The twist is usually in what counts as a node, where the search starts, or what extra information travels with each node. The patterns below are the twists that come up again and again.

First step: Before writing the loop, write down in one line what a node is (a vertex, a grid cell, a word, a (vertex, mask) pair), how its neighbors are produced, and which nodes go into the queue or stack at the start.

Grids are the most common disguise. Each cell is a node with 4 or 8 neighbors, and the only extra work is the bounds check. Number of islands, flood fill, and shortest paths on a maze are worked through in the "Grids as Graphs" part of the matrices notes, and every pattern below applies to grids unchanged.

Multi-source BFS by levels. When the question asks how many minutes something takes to spread, or how far each cell is from the nearest source, put every source in the queue before the loop starts. Then process one level at a time by reading len(queue) at the start of each round. In 994 Rotting Oranges every rotten orange is a source and each round is one minute. In 542 01 Matrix every zero cell is a source and the BFS distance is the answer for every cell.

queue = deque(rotten_cells)              # all sources start together
minutes = 0
while queue and fresh > 0:
    for _ in range(len(queue)):          # exactly one level per round
        r, c = queue.popleft()
        for nr, nc in four_neighbors(r, c):
            if in_bounds(nr, nc) and grid[nr][nc] == FRESH:
                grid[nr][nc] = ROTTEN
                fresh -= 1
                queue.append((nr, nc))
    minutes += 1
return minutes if fresh == 0 else -1

Search backwards from the targets. If many starting points share a small set of goals, reverse the question and start from the goals. In 417 Pacific Atlantic Water Flow, searching from every cell is quadratic, so instead run one search from all Pacific border cells and one from all Atlantic border cells, moving only to neighbors of equal or greater height, and return the cells reached by both. In 130 Surrounded Regions, search from every O on the border and mark what you reach; every unmarked O is surrounded and gets flipped.

BFS on an implicit graph. Sometimes the graph is never given and you generate neighbors on the fly. In 127 Word Ladder a node is a word and its neighbors are words in the dictionary that differ in one letter; try all 26 letters at each position and look them up in a set. The answer counts words, so the start word has distance 1. In 752 Open the Lock a node is a 4-digit string with 8 neighbors (each wheel up or down). Add the dead ends to visited before starting, and return -1 at once if "0000" is itself a dead end.

BFS over states. When the same node can be visited again with different progress, the node alone is not enough. In 847 Shortest Path Visiting All Nodes the state is (node, mask), where the mask records visited nodes. Start from every (i, 1 << i) at once and stop when the mask is full. There are $n \cdot 2^n$ states, which is fine for $n \le 12$. The same idea with a different state appears in 1293 Shortest Path in a Grid with Obstacles Elimination, where the state is (row, col, removals left).

Copying a graph. In 133 Clone Graph keep a map from each original node to its copy. Create the copy and store it in the map before visiting the neighbors, so a cycle finds the existing copy instead of recursing forever.

def clone(node, copies):
    if node in copies:
        return copies[node]
    copy = Node(node.val)
    copies[node] = copy                  # register before recursing
    for nb in node.neighbors:
        copy.neighbors.append(clone(nb, copies))
    return copy

Peeling leaves. In 310 Minimum Height Trees the best roots are the centers of the tree. Put every leaf (degree 1) in a queue, remove one layer of leaves at a time while lowering their neighbors' degrees, and stop when at most two vertices remain. Handle $n = 1$ separately, where the answer is [0].

Three-color DFS. Give each vertex a state: 0 unvisited, 1 on the current DFS path, 2 finished. Reaching a state-1 vertex means a directed cycle, which is how 207 Course Schedule can be solved with DFS. In 802 Find Eventual Safe States a node is safe exactly when every path from it avoids cycles, so a node is safe when all of its neighbors are safe; nodes left in state 1 are unsafe for good.

def is_safe(u):                          # state: 0 new, 1 on path, 2 safe
    if state[u] != 0:
        return state[u] == 2
    state[u] = 1
    for v in G[u]:
        if not is_safe(v):
            return False                 # u stays 1, so it stays unsafe
    state[u] = 2
    return True

0-1 BFS. When every edge costs 0 or 1, a deque replaces Dijkstra's heap. Relax edges as in Dijkstra, push the neighbor to the front for a 0-cost edge and to the back for a 1-cost edge. This runs in $O(V+E)$ and fits problems such as 1368 Minimum Cost to Make at Least One Valid Path in a Grid and 2290 Minimum Obstacle Removal to Reach Corner.

dist = {s: 0}
dq = deque([s])
while dq:
    u = dq.popleft()
    for v, w in G[u]:                    # w is 0 or 1
        if dist[u] + w < dist.get(v, INF):
            dist[v] = dist[u] + w
            if w == 0:
                dq.appendleft(v)
            else:
                dq.append(v)

Validating a tree. An undirected graph on $n$ vertices is a tree exactly when it has $n-1$ edges and is connected. For 261 Graph Valid Tree, check the edge count first, then run one BFS, DFS, or union-find pass and confirm that all $n$ vertices were reached.

Building the edges yourself. In 269 Alien Dictionary the graph is hidden in the word order. Compare each pair of adjacent words, and the first position where they differ gives one edge from the earlier letter to the later one; ignore the rest of the pair. If there is no differing position and the first word is longer (as in "abc" before "ab"), the input is invalid. Every letter that appears anywhere must be a vertex, even with no edges, and a topological order shorter than the number of letters means a cycle.

Weighted relations. In 399 Evaluate Division, the equation $a / b = k$ becomes an edge $a \to b$ with weight $k$ and an edge $b \to a$ with weight $1/k$. A query $x / y$ is the product of the weights along any path from $x$ to $y$, found with BFS or DFS. If either variable never appeared the answer is -1.0, and $x / x$ is 1.0 only if $x$ appeared.

All of these keep the $O(V+E)$ cost of the underlying search, measured on whatever graph the nodes and edges really are (for example $n \cdot 2^n$ states in 847). The most common mistake in the plain BFS patterns is marking a node visited when it is popped instead of when it is pushed, which lets the same node enter the queue many times and can blow up both time and memory (0-1 BFS is the exception, since it relaxes distances like Dijkstra).

Once you can represent a problem as a graph and you’re fluent in storing it (matrix/list) and traversing it (BFS/DFS), you’ve unlocked the foundation for almost every other graph technique, shortest paths, minimum spanning trees, flows, matchings, connectivity analysis, and more. Graphs are the doorway; traversal is the first step through it.

Graph Coloring

Coloring gives each vertex a color so that the two ends of every edge differ. In programming problems it rarely says "color". It says "split the people into two groups so that no two who dislike each other are together" or "give each garden a flower type different from its neighbors".

First step: Build an undirected adjacency list (a dislike or conflict goes in both directions) and a color array filled with -1 for uncolored. Plan an outer loop over every vertex, because nothing promises the graph is connected.

Two colors is the bipartite check. A graph can be 2-colored exactly when it has no odd cycle. Start a BFS or DFS at an uncolored vertex with color 0, give each newly discovered neighbor the opposite color, and fail as soon as an edge joins two vertices of the same color. The trap is that the graph may be disconnected, so one search from vertex 0 can miss a whole component with an odd cycle. 785 Is Graph Bipartite gives the adjacency list directly, and 886 Possible Bipartition gives dislike pairs on labels 1 to n.

def is_bipartite(n, G):
    color = [-1] * n
    for s in range(n):                   # start from every uncolored vertex
        if color[s] != -1:
            continue
        color[s] = 0
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in G[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False         # odd cycle
    return True

With more colors, a simple greedy rule often suffices. Visit the vertices in any order and give each the smallest color not used by its already-colored neighbors. A vertex has at most $\Delta$ neighbors, where $\Delta$ is the maximum degree, so among $\Delta + 1$ colors one is always free. That is why 1042 Flower Planting With No Adjacent needs no search at all: every garden has at most 3 paths, so 4 flower types always work and greedy never gets stuck.

Greedy does not find the minimum number of colors in general, and deciding whether a graph can be colored with 3 colors is NP-complete. So interview coloring problems always come with special structure: exactly two colors, a degree bound like in 1042, or a graph small enough for backtracking. The backtracking version is the "K-Colorable Configurations" exercise in the backtracking notes.

Both the bipartite check and greedy coloring run in $O(V+E)$ time with $O(V)$ extra space. The most common mistake is searching only from vertex 0 and reporting "bipartite" while another component still contains an odd cycle.

Bridges, Articulation Points, and Strongly Connected Components

A bridge is an edge whose removal disconnects the graph, and an articulation point is a vertex whose removal does the same. Problems phrase this as "critical connections" or "which link, if cut, splits the network". Removing each edge and running a fresh BFS costs $O(E(V+E))$, which is far too slow for 1192 Critical Connections in a Network with $n$ up to $10^5$. One DFS with low-link values finds all of them.

During the DFS, tin[u] is the time $u$ was discovered. low[u] is the smallest tin reachable from $u$'s DFS subtree using tree edges downward and at most one back edge. If a child $v$ has low[v] > tin[u], nothing below $v$ can climb back to $u$ or above, so the edge $u - v$ is a bridge. For articulation points the test is low[v] >= tin[u] for some child $v$, except that the DFS root is an articulation point only when it has two or more DFS children.

First step: Build an undirected adjacency list, set up tin and low arrays plus a timer, and decide how to skip the edge back to the parent: by parent vertex for simple graphs, by edge id when parallel edges may exist.

def bridges(n, G):
    tin = [-1] * n
    low = [0] * n
    timer = 0
    result = []

    def dfs(u, parent):
        nonlocal timer
        tin[u] = low[u] = timer
        timer += 1
        for v in G[u]:
            if v == parent:
                continue                 # skip the edge we arrived by
            if tin[v] == -1:             # tree edge
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > tin[u]:
                    result.append((u, v))
            else:                        # back edge
                low[u] = min(low[u], tin[v])

    for s in range(n):
        if tin[s] == -1:
            dfs(s, -1)
    return result

This runs in $O(V+E)$ time and $O(V)$ space, but the recursion can be $V$ deep, so in Python an input with $10^5$ vertices needs an iterative version or a raised recursion limit. The most common mistake is mixing up the two tests: bridges use the strict low[v] > tin[u], articulation points use low[v] >= tin[u].

In a directed graph the matching idea is the strongly connected component (SCC): a maximal set of vertices where each one can reach every other. Kosaraju's algorithm runs one DFS to record finishing order, reverses every edge, and then runs DFS on the reversed graph in decreasing finishing time; each tree of that second pass is one SCC. Tarjan's algorithm does it in a single DFS with the same low values plus a stack, closing a component when low[u] == tin[u], and it only lowers low[u] through vertices still on the stack. Both are $O(V+E)$. Collapsing each SCC to a single vertex always gives a DAG, so a problem with cycles can often be reduced to topological sort or DP on that smaller graph.

Union-Find (Disjoint Set Union)

Union-Find keeps elements split into groups and answers two questions quickly: which group is $x$ in (find), and merge the groups of $x$ and $y$ (union). Each group is a tree of parent pointers, and the root is the group's representative. Recognize it when edges or "these two belong together" facts arrive one at a time, and you only need to know whether two things are connected or how many groups exist, never the actual path. It cannot remove edges.

Two tricks keep the trees flat. Path compression points nodes closer to the root while find walks up, and union by size (or rank) always hangs the smaller tree under the larger root. Kruskal's algorithm below uses this same structure.

First step: Map every element to an integer id from 0 to n-1, using a dictionary when the elements are strings such as emails. Then create parent[i] = i, size[i] = 1, and a component counter equal to n.

parent = list(range(n))
size = [1] * n
components = n

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]    # path halving, a form of compression
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False                     # already connected: edge closes a cycle
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra                      # smaller tree under larger root
    size[ra] += size[rb]
    components -= 1                      # needs nonlocal or global in real code
    return True

The typical uses follow directly from union returning False and from the counter:

Counting components, as in 323 Number of Connected Components in an Undirected Graph and 547 Number of Provinces: union every edge and read components.
Finding the redundant edge in 684 Redundant Connection: process edges in input order, and the first one whose union returns False closes the only cycle, which makes it the last cycle edge in the input as the problem requires.
1319 Number of Operations to Make Network Connected: if there are fewer than $n-1$ cables the answer is -1; otherwise every extra cable can be moved, so the answer is components - 1.
721 Accounts Merge: give each email an id the first time you see it, union every email of an account with that account's first email, then group emails by find(id), sort each group, and put the owner's name in front.

With both path compression and union by size, a sequence of operations costs $O(\alpha(n))$ amortized each, where $\alpha$ is the inverse Ackermann function and is at most 4 for any practical $n$; space is $O(n)$. The most common mistake is comparing parent[a] == parent[b] instead of find(a) == find(b), or linking a under b directly instead of linking their roots.

Shortest paths

A common task when dealing with weighted graphs is to find the shortest route between two vertices, such as from vertex $A$ to vertex $B$. Note that there might not be a unique shortest path, since several paths could have the same length.

Dijkstra’s Algorithm

Dijkstra’s algorithm computes shortest paths from a specified start vertex in a graph with non-negative edge weights. It grows a “settled” region outward from the start, always choosing the unsettled vertex with the smallest known distance and relaxing its outgoing edges to improve neighbors’ distances.

First step: Confirm that every edge weight is non-negative, build a weighted adjacency list of (neighbor, weight) pairs, and fill dist with infinity except dist[source] = 0. Decide up front whether you can stop as soon as the target is popped.

To efficiently keep track of the traversal, Dijkstra’s algorithm employs two primary data structures:

A min-priority queue (often named pq, open, or unexplored) keyed by each vertex’s current best known distance from the start.
A dist map storing the best known distance to each vertex (∞ initially, except the start), a visited/finalized set to mark vertices whose shortest distance is proven, and a parent map to reconstruct paths.

Useful additions in practice:

A target-aware early stop allows Dijkstra’s algorithm to halt once the target vertex is extracted from the priority queue, saving work compared to continuing until all distances are finalized; without this optimization, computing the shortest route between two cities would require processing the entire network unnecessarily.
With decrease-key or lazy insertion strategies, priority queues that lack a decrease-key operation can still work by inserting updated entries and discarding outdated ones when popped; without this adjustment, distance updates in large road networks would be inefficient or require a more complex data structure.
Adding optional predecessor lists can support reconstruction of multiple optimal paths; if these lists are not maintained, applications like enumerating all equally fast routes between transit stations cannot be supported.

Algorithm Steps:

Pick a start vertex $i$.
Set dist[i] = 0 and parent[i] = None; for all other vertices $v \ne i$, set dist[v] = ∞.
Push $i$ into a min-priority queue keyed by dist[·].
While the priority queue is nonempty, repeat steps 5–8.
Extract the vertex $u$ with the smallest dist[u].
If $u$ is already finalized, continue to step 4; otherwise mark $u$ as finalized.
For each neighbor $v$ of $u$ with edge weight $w(u,v) \ge 0$, test whether dist[u] + w(u,v) < dist[v].
If true, set dist[v] = dist[u] + w(u,v), set parent[v] = u, and push $v$ into the priority queue keyed by the new dist[v].
Stop when the queue is empty (all reachable vertices finalized) or, if you have a target, when that target is finalized.
Reconstruct any shortest path by following parent[·] backward from the target to $i$.

Vertices are finalized when their first current entry is removed from the priority queue. Later stale entries are ignored. Non-negative weights make the finalized distance optimal. Before reconstructing a target path, check that the target has finite distance; an unreachable target has no path to reconstruct.

Reference pseudocode (adjacency-list graph):

Dijkstra(G, i, target=None):
    INF = +infinity
    dist   = defaultdict(lambda: INF)
    parent = {i: None}
    dist[i] = 0

    pq = MinPriorityQueue()
    pq.push(i, 0)

    finalized = set()

    while pq:
        u, du = pq.pop_min()                 # smallest current distance
        if u in finalized:                   # ignore stale entries
            continue

        finalized.add(u)

        if target is not None and u == target:
            break                            # early exit: target finalized

        for (v, w_uv) in G[u]:               # w_uv >= 0
            alt = du + w_uv
            if alt < dist[v]:
                dist[v]   = alt
                parent[v] = u
                pq.push(v, alt)              # decrease-key or lazy insert

    return dist, parent

# Reconstruct path i -> t (if t reachable):
reconstruct(parent, t):
    path = []
    while t is not None:
        path.append(t)
        t = parent.get(t)
    return list(reversed(path))

Sanity notes:

The time complexity of Dijkstra’s algorithm depends on the priority queue: $O((V+E)\log V)$ with a binary heap, $O(E+V\log V)$ with a Fibonacci heap, and $O(V^2)$ with a plain array; without this distinction, one might wrongly assume that all implementations scale equally on dense versus sparse road networks.
An indexed priority queue uses $O(V)$ auxiliary space. The lazy duplicate-entry version shown can use $O(V+E)$ space and $O(V+E\log(E+2))$ time. On a simple graph this gives the usual $O((V+E)\log V)$ upper bound.
The precondition is that all edge weights must be nonnegative, because non-negative weights guarantee that a finalized distance cannot later be improved; if negative weights exist, as in certain financial models with losses, the computed paths can be incorrect and Bellman–Ford must be used instead.
In terms of ordering, the sequence in which neighbors are processed does not affect correctness, only the handling of ties and slight performance differences; without recognizing this, variations in output order between implementations might be mistakenly interpreted as errors.

Example

Weighted, undirected graph; start at A. Edge weights are on the links.

A --4-- B --1-- E
 \     /        |
  1   2         3
   \ /          |
    C ----4---- D

Edges: A–B(4), A–C(1), C–B(2), B–E(1), C–D(4), D–E(3)

Priority queue / Finalized evolution (front = smallest key):

Step | Pop (u,dist) | Relaxations (v: new dist, parent)          | PQ after push                    | Finalized
-----+--------------+--------------------------------------------+----------------------------------+----------------
0    | ,             | init A: dist[A]=0                          | [(A,0)]                          | {}
1    | (A,0)        | B:4←A  , C:1←A                             | [(C,1), (B,4)]                   | {A}
2    | (C,1)        | B:3←C  , D:5←C                             | [(B,3), (B,4), (D,5)]            | {A,C}
3    | (B,3)        | E:4←B                                      | [(E,4), (B,4), (D,5)]            | {A,C,B}
4    | (E,4)        | D:7 via E  (no improve; current 5)         | [(B,4), (D,5)]                   | {A,C,B,E}
5    | (B,4) stale  | (ignore; B already finalized)              | [(D,5)]                          | {A,C,B,E}
6    | (D,5)        | ,                                           | []                               | {A,C,B,E,D}

Distances and parents (final):

dist[A]=0 (, )
dist[C]=1 (A)
dist[B]=3 (C)
dist[E]=4 (B)
dist[D]=5 (C)

Shortest path A→E: A → C → B → E  (total cost 4)

Big-picture view of the expanding frontier:

   Settled set grows outward from A by increasing distance.
   After Step 1: {A}
   After Step 2: {A, C}
   After Step 3: {A, C, B}
   After Step 4: {A, C, B, E}
   After Step 6: {A, C, B, E, D}  (all reachable nodes done)

Applications

In single-source shortest paths with non-negative edge weights, Dijkstra’s algorithm efficiently finds minimum-cost routes in settings like roads, communication networks, or transit systems; without it, travel times or costs could not be computed reliably when distances vary.
For navigation and routing, stopping the search as soon as the destination is extracted from the priority queue avoids unnecessary work; without this early stop, route planning in a road map continues exploring irrelevant regions of the network.
In network planning and quality of service (QoS), Dijkstra selects minimum-latency or minimum-cost routes when weights are additive and non-negative; without this, designing efficient data or logistics paths becomes more error-prone.
As a building block, Dijkstra underlies algorithms like A* (with zero heuristic), Johnson’s algorithm for all-pairs shortest paths in sparse graphs, and $k$-shortest path variants; without it, these higher-level methods would lack a reliable core procedure.
In multi-source Dijkstra, initializing the priority queue with several starting nodes at distance zero solves nearest-facility queries, such as finding the closest hospital; without this extension, repeated single-source runs would waste time.
As a label-setting baseline, Dijkstra provides the reference solution against which heuristics like A*, ALT landmarks, or contraction hierarchies are compared; without this baseline, heuristic correctness and performance cannot be properly evaluated.
For grid pathfinding with terrain costs, Dijkstra handles non-negative cell costs when no admissible heuristic is available; without it, finding a least-effort path across weighted terrain would require less efficient exhaustive search.

Implementation:

C++
Python

Implementation tip: If your PQ has no decrease-key, push duplicates on improvement and, when popping a vertex, skip it if it’s already finalized or if the popped key doesn’t match dist[u]. This “lazy” approach is simple and fast in practice.

Dijkstra Variants: Minimax Paths and Maximum Probability

Dijkstra is not tied to adding weights. It works whenever extending a path can never make its cost better, because then the first time a node is popped its cost is final. Two common variants use this. The first minimizes the largest edge on the path instead of the sum. The second maximizes a product of probabilities, each between 0 and 1.

First step: Write down how the path cost changes when you add one edge, for example max(cost, w) or cost * p, and check that adding an edge can never improve it. Then reuse Dijkstra with that combine step and the right heap direction.

In 1631 Path With Minimum Effort the effort of a path is the largest height difference between neighboring cells on it. In 778 Swim in Rising Water the time needed is the largest elevation on the path, including the starting cell. Both are minimax problems: the relaxation becomes max(d, w) instead of d + w.

def minimax_path(G, s, t, start_cost=0):     # 778: start_cost = grid[0][0]
    best = {s: start_cost}
    heap = [(start_cost, s)]
    while heap:
        d, u = heappop(heap)
        if u == t:
            return d
        if d > best[u]:
            continue                         # stale entry
        for v, w in G[u]:
            nd = max(d, w)                   # bottleneck instead of sum
            if nd < best.get(v, INF):
                best[v] = nd
                heappush(heap, (nd, v))
    return INF

There is a second way to solve minimax problems. "Can I reach the target using only edges of weight at most $L$?" gets easier as $L$ grows, so binary search on $L$ and answer each question with a BFS or DFS that ignores heavier edges. Adding edges in increasing weight order with union-find until source and target join also works, which is Kruskal's idea.

For 1514 Path with Maximum Probability, multiplying by a probability $p \le 1$ never increases the product, so Dijkstra works with a max-heap (push the negated probability with Python's heapq). Start with probability 1 at the source and 0 everywhere else, and relax with prob[u] * p > prob[v]. This is the same as ordinary Dijkstra on weights $-\log p$, which are non-negative.

Both variants keep Dijkstra's $O((V+E)\log V)$ time and $O(V+E)$ space, and the binary-search version costs $O((V+E)\log W)$ for a weight range $W$. The most common mistake in 1514 is using a min-heap, which pops the worst probability first, and in 1631 it is summing the differences instead of taking their maximum.

Bellman–Ford Algorithm

Bellman–Ford computes shortest paths from a start vertex in graphs that may have negative edge weights (but no negative cycles reachable from the start). It works by repeatedly relaxing every edge; each full pass can reduce some distances until they stabilize. A final check detects negative cycles: if an edge can still be relaxed after $(V-1)$ passes, a reachable negative cycle exists.

First step: Put all edges in one flat list of (u, v, w) triples, adding both directions for undirected edges (an undirected negative edge is already a negative cycle). Initialize dist with infinity except the source, and decide whether you need negative-cycle detection or a limit on the number of edges.

To efficiently keep track of the computation, Bellman–Ford employs two primary data structures:

A dist map (or array) with the best-known distance to each vertex (initialized to ∞ except the start).
A parent map to reconstruct shortest paths (store parent[v] = u when relaxing edge $u!\to!v$).

Useful additions in practice:

With an edge list, iterating directly over edges simplifies implementation and keeps updates fast, even if the graph is stored in adjacency lists; without this practice, repeatedly scanning adjacency structures adds unnecessary overhead in each relaxation pass.
Using an early exit allows termination once a full iteration over edges yields no updates, improving efficiency; without this check, the algorithm continues all $V-1$ passes even on graphs like road networks where distances stabilize early.
For negative-cycle extraction, if an update still occurs on the $V$-th pass, backtracking through parent links reveals a cycle; without this step, applications such as financial arbitrage detection cannot identify opportunities caused by negative cycles.
Adding a reachability guard skips edges from vertices with infinite distance, avoiding wasted work on unreached nodes; without this filter, the algorithm needlessly inspects irrelevant edges in disconnected parts of the graph.

Algorithm Steps:

Pick a start vertex $i$.
Set dist[i] = 0 and parent[i] = None; for all other vertices $v \ne i$, set dist[v] = ∞.
Do up to $V-1$ passes: in each pass, scan every directed edge $(u,v,w)$; if dist[u] + w < dist[v], set dist[v] = dist[u] + w and parent[v] = u. If a full pass makes no changes, stop early.
Detect reachable negative cycles before trusting finite distances: if an edge from a finite-distance vertex can still be relaxed, a reachable negative cycle exists. To extract a cycle, perform a full additional relaxation pass, updating distances and parents, remember a vertex updated on that pass, and follow its parent chain for $V$ steps before collecting the repeated cycle. The detection-only pseudocode below does not perform that extraction pass.
To get a shortest path to a target $t$ (when no relevant negative cycle exists), follow parent[t] backward to $i$.

Reference pseudocode (edge list):

BellmanFord(V, E, i):                 # V: set/list of vertices
    INF = +infinity                   # E: list of (u, v, w) edges
    dist   = {v: INF for v in V}
    parent = {v: None for v in V}
    dist[i] = 0

    # (V-1) relaxation passes
    for _ in range(len(V) - 1):
        changed = False
        for (u, v, w) in E:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                changed = True
        if not changed:
            break

    # Negative-cycle check
    cycle_vertex = None
    for (u, v, w) in E:
        if dist[u] != INF and dist[u] + w < dist[v]:
            cycle_vertex = v
            break

    return dist, parent, cycle_vertex     # cycle_vertex=None if no neg cycle

# Reconstruct shortest path i -> t (if safe):
reconstruct(parent, t):
    path = []
    while t is not None:
        path.append(t)
        t = parent[t]
    return list(reversed(path))

Sanity notes:

The time complexity of Bellman–Ford is $O(VE)$ because each of the $V-1$ relaxation passes scans all edges; without this understanding, one might underestimate the cost of running it on dense graphs with many edges.
The space complexity is $O(V)$, needed for storing distance estimates and parent pointers; if this is not accounted for, memory use may be underestimated in large-scale applications such as road networks.
The algorithm handles negative weights correctly and can also detect negative cycles that are reachable from the source; without this feature, Dijkstra’s algorithm would produce incorrect results on graphs with negative edge costs.
When a reachable negative cycle exists, shortest paths to nodes that can be reached from it are undefined, effectively taking value $-\infty$; without recognizing this, results such as infinitely decreasing profit in arbitrage graphs would be misinterpreted as valid finite paths.

Example

Directed, weighted graph; start at A. (Negative edges allowed; no negative cycles here.)

A -> B (4)     A -> C (2)
B -> C (-1)    B -> D (2)
C -> B (1)     C -> D (5)     C -> E (3)
D -> E (-3)

Edges list:

A→B(4), A→C(2), B→C(-1), B→D(2), C→B(1), C→D(5), C→E(3), D→E(-3)

Relaxation trace (dist after each full pass; start A):

Init (pass 0):
  dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞, dist[E]=∞

After pass 1:
  A=0, B=3, C=2, D=6, E=3
    (B→D sets D=6 before C→B lowers B to 3; D→E then sets E=3)

After pass 2:
  A=0, B=3, C=2, D=5, E=2
    (B→D improved D to 5; D→E improved E to 2)

After pass 3:
  A=0, B=3, C=2, D=5, E=2   (no changes → early stop)

Parents / shortest paths (one valid set):

parent[A]=None
parent[C]=A
parent[B]=C
parent[D]=B
parent[E]=D

Example shortest path A→E:
A → C → B → D → E   with total cost 2 + 1 + 2 + (-3) = 2

Negative-cycle detection (illustration): If we add an extra edge E→C(-4), the cycle C → D → E → C has total weight 5 + (-3) + (-4) = -2 (negative). Bellman–Ford would perform a $V$-th pass and still find an improvement (e.g., relaxing E→C(-4)), so it reports a reachable negative cycle.

Applications

In shortest path problems with negative edges, Bellman–Ford is applicable where Dijkstra or A* fail, such as road networks with toll credits; without this method, these graphs cannot be handled correctly.
For arbitrage detection in currency or financial markets, converting an exchange rate $r$ into weight $-\log r$ makes profit loops appear as negative cycles; without Bellman–Ford, such opportunities cannot be systematically identified.
In solving difference constraints of the form $x_v - x_u \leq w$, the algorithm checks feasibility by detecting whether any negative cycles exist; without this check, inconsistent scheduling or timing systems may go unnoticed.
As a robust baseline, Bellman–Ford verifies results of faster algorithms or initializes methods like Johnson’s for all-pairs shortest paths; without it, correctness guarantees in sparse-graph all-pairs problems would be weaker.
For graphs with penalties or credits, where some transitions decrease accumulated cost, Bellman–Ford models these adjustments accurately; without it, such systems, like transport discounts or energy recovery paths, cannot be represented properly.

Implementation:

C++
Python

Implementation tip: For all-pairs on sparse graphs with possible negative edges, use Johnson’s algorithm: run Bellman–Ford once from a super-source to reweight edges (no negatives), then run Dijkstra from each vertex.

Shortest Paths With at Most k Edges

The passes of Bellman–Ford have an exact meaning if every pass reads only the distances left by the previous pass. After pass $i$, dist[v] is then the cheapest cost of reaching $v$ with at most $i$ edges. The in-place version above can chain several edges inside a single pass, because it reads values written earlier in the same pass. That is harmless when you only want the final shortest paths, but it breaks any limit on the number of edges.

787 Cheapest Flights Within K Stops is this situation. $k$ stops means $k+1$ flights, so run exactly $k+1$ passes, and in each pass relax from a copy of dist taken at the start of the pass.

First step: Translate the limit into edges (k stops means k + 1 edges), then make sure each pass reads from a frozen copy of dist and writes into the live array.

def cheapest_within_k_stops(n, flights, src, dst, k):
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):                   # k stops = k + 1 edges
        prev = dist[:]                       # freeze the last pass
        for u, v, w in flights:
            if prev[u] != INF and prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return dist[dst] if dist[dst] != INF else -1

This takes $O(k(V+E))$ time, counting the copy in each pass, and $O(V)$ space. The most common mistake is relaxing in place without the copy, which lets one pass use several flights and silently exceeds the stop limit. Plain Dijkstra on the node alone is also wrong here, because a cheap route with too many stops can finalize a node before a pricier route with fewer stops arrives; Dijkstra over (node, stops used) states does work.

A* (A-Star) Algorithm

A* is a best-first search that finds a least-cost path from a start to a goal by minimizing

$$ f(n) = g(n) + h(n), $$

where:

$g(n)$ = cost from start to $n$ (so far),
$h(n)$ = heuristic estimate of the remaining cost from $n$ to the goal.

First step: Check that edge costs are non-negative and pick a heuristic that never overestimates the remaining cost, such as Manhattan distance on a 4-direction grid with unit steps. If no such heuristic is available, plain Dijkstra is the safer choice.

Assume a finite graph, non-negative edge costs, and $h(goal)=0$. With a consistent heuristic, A* is optimal without reopening expanded nodes. With an admissible but inconsistent heuristic, reopen a node whenever a better path reaches it. These guarantees apply when the goal is removed from the queue with a current entry, not when it is first discovered. Berkeley CS 188 notes.

Core data structures

The open set is a min-priority queue keyed by the evaluation function $f=g+h$, storing nodes pending expansion; without it, selecting the next most promising state in pathfinding would require inefficient linear scans.
The closed set contains nodes already expanded and finalized, preventing reprocessing; if omitted, the algorithm may revisit the same grid cells or graph states repeatedly, wasting time.
The $g$ map tracks the best known cost-so-far to each node, ensuring paths are only updated when improvements are found; without it, the algorithm cannot correctly accumulate and compare path costs.
The parent map stores predecessors so that a complete path can be reconstructed once the target is reached; if absent, the algorithm would output only a final distance without the actual route.
An optional heuristic cache and tie-breaker (such as preferring larger $g$ or smaller $h$ when $f$ ties) can improve efficiency and consistency; without these, the search may expand more nodes than necessary or return different paths under equivalent conditions.

Algorithm Steps:

Put start in open (a min-priority queue by f); set g[start]=0, f[start]=h(start), parent[start]=None; initialize closed = ∅.
While open is nonempty, repeat steps 3–7.
Pop the node u with the smallest f(u) from open.
If u is the goal, reconstruct the path by following parent back to start and return it.
Add u to closed.
For each neighbor v of u with edge cost $w(u,v) \ge 0$, set tentative = g[u] + w(u,v).
If v not in g or tentative < g[v], set parent[v]=u, g[v]=tentative, f[v]=g[v]+h(v), and push v into open (even if it was already there with a worse key).
If the loop ends because open is empty, no path exists.

Store the best known g when enqueuing a neighbor, but allow later improvements. Skip stale queue entries before expanding a node or accepting the goal. With a consistent heuristic, the first current entry popped for a node finalizes its distance.

Reference pseudocode

A_star(graph, start, goal, heuristic):
    frontier = MinPriorityQueue()
    frontier.push((start, 0), heuristic(start))
    best_cost = {start: 0}
    parent = {start: None}
    closed = set()

    while frontier:
        (current, stored_cost), priority = frontier.pop_min()
        if stored_cost != best_cost[current] or current in closed:
            continue
        if current == goal:
            return reconstruct_path(parent, goal), stored_cost

        closed.add(current)
        for neighbor, edge_cost in graph.neighbors(current):
            candidate = stored_cost + edge_cost
            if candidate < best_cost.get(neighbor, +infinity):
                best_cost[neighbor] = candidate
                parent[neighbor] = current
                closed.discard(neighbor)
                frontier.push(
                    (neighbor, candidate),
                    candidate + heuristic(neighbor)
                )

    return None, +infinity

reconstruct_path(parent, t):
    path = []
    while t is not None:
        path.append(t)
        t = parent[t]
    return list(reversed(path))

Sanity notes:

On an explicit finite graph with a consistent heuristic, each vertex is expanded at most once; a binary heap gives bounds comparable to Dijkstra. For implicit state spaces, the number of states can be exponential in solution depth. Inconsistent heuristics can also cause repeated expansions, so these are different complexity models.
With consistency and an indexed queue, auxiliary space is $O(V)$; lazy duplicate entries can raise it to $O(V+E)$. With reopening, pending entries depend on the number of improvements. Large implicit state spaces can make memory the limiting resource.
In special cases, A* reduces to Dijkstra’s algorithm when $h \equiv 0$, and further reduces to BFS when all edges have cost 1 and $h \equiv 0$; without this perspective, one might overlook how A* generalizes these familiar shortest-path algorithms.

Visual walkthrough (grid with 4-neighborhood, Manhattan $h$)

Legend: S start, G goal, # wall, . free, ◉ expanded (closed), • frontier (open), × final path

Row/Col →    1  2  3  4  5  6  7  8  9
           ┌────────────────────────────┐
         1 │ S  .  .  .  .  #  .  .  .  │
         2 │ .  #  #  .  .  #  .  #  .  │
         3 │ .  .  .  .  .  .  .  #  .  │
         4 │ #  .  #  #  .  #  .  .  .  │
         5 │ .  .  .  #  .  .  .  #  G  │
           └────────────────────────────┘
Movement cost = 1 per step; 4-dir moves; h = Manhattan distance

Early expansion snapshot (conceptual):

Step 0:
Open: [(S, g=0, h=|S-G|, f=g+h)]         Closed: {}
Grid: S is • (on frontier)

Step 1: pop S → expand neighbors
Open: [((1,2), g=1, h=?, f=?), ((2,1), g=1, h=?, f=?)]
Closed: {S}
Marks: S→ ◉, its valid neighbors → •

Step 2..k:
A* keeps popping the lowest f, steering toward G.
Nodes near the straight line to G are preferred over detours around '#'.

When goal is reached, reconstruct the path:

One shortest path (row, column; one-based coordinates):
(1,1) -> (1,2) -> (1,3) -> (1,4) -> (2,4) -> (3,4)
      -> (3,5) -> (3,6) -> (3,7) -> (4,7) -> (4,8)
      -> (4,9) -> (5,9)

S  ×  ×  ×  .  #  .  .  .
.  #  #  ×  .  #  .  #  .
.  .  .  ×  ×  ×  ×  #  .
#  .  #  #  .  #  ×  ×  ×
.  .  .  #  .  .  .  #  G

There are 13 path vertices and 12 moves, so g(G) = 12.

Priority queue evolution (toy example)

Step | Popped | New entries (g, h, f)                     | Tie choice
0    | —      | S: (0, 12, 12)                            | S = (1,1)
1    | S      | (1,2): (1,11,12), (2,1): (1,11,12)       | choose (2,1)
2    | (2,1)  | (3,1): (2,10,12)                         | choose (3,1)
3    | (3,1)  | (3,2): (3,9,12); (4,1) is a wall         | both branches remain possible

These Manhattan values follow directly from the displayed coordinates. Equal priorities leave the expansion order dependent on tie-breaking.

Heuristic design

For grids:

4-dir moves: $h(n)=|x_n-x_g|+|y_n-y_g|$ (Manhattan).
8-dir (diag cost √2): Octile: $h=\Delta_{\max} + (\sqrt{2}-1)\Delta_{\min}$.
Euclidean when motion is continuous and diagonal is allowed.

For sliding puzzles (e.g., 8/15-puzzle):

Misplaced tiles, excluding the blank (admissible, weak).
Manhattan sum over numbered tiles, excluding the blank (stronger).
Linear conflict / pattern databases (even stronger).

Admissible vs. Consistent

An admissible heuristic satisfies $h(n) \leq h^*(n)$, meaning it never overestimates the true remaining cost, which guarantees optimality for the graph-search version only with an appropriate reopening policy and goal-pop termination; without admissibility, the algorithm may return a suboptimal route, such as a longer-than-necessary driving path.
A consistent (monotone) heuristic obeys $h(u) \leq w(u,v) + h(v)$ for every edge, ensuring that $f$-values do not decrease along paths and that once a node is removed from the open set, its $g$-value is final; without consistency, nodes may need to be reopened, increasing complexity in searches like grid navigation.

Applications

In pathfinding for maps, games, and robotics, A* computes shortest or least-risk routes by combining actual travel cost with heuristic guidance; without it, movement planning in virtual or physical environments becomes slower or less efficient.
For route planning with road metrics such as travel time, distance, or tolls, A* incorporates these costs and constraints into its evaluation; without heuristic search, navigation systems must fall back to slower methods like plain Dijkstra.
In planning and scheduling tasks, A* serves as a general shortest-path algorithm in abstract state spaces, supporting AI decision-making; without it, solving resource allocation or task sequencing problems may require less efficient exhaustive search.
In puzzle solving domains such as the 8-puzzle or Sokoban, A* uses problem-specific heuristics to guide the search efficiently; without heuristics, the state space may grow exponentially and become impractical to explore.
For network optimization problems with nonnegative edge costs, A* applies whenever a useful heuristic is available to speed convergence; without heuristics, computations on communication or logistics networks may take longer than necessary.

Variants & practical tweaks

Viewing Dijkstra as A* with $h \equiv 0$ shows that A* generalizes the classic shortest-path algorithm; without this equivalence, the connection between uninformed and heuristic search may be overlooked.
In Weighted A*, the evaluation function becomes $f = g + \varepsilon h$ with $\varepsilon > 1$, trading exact optimality for faster performance with bounded suboptimality; without this variant, applications needing quick approximate routing, like logistics planning, would run slower.
An anytime A* approach begins with $\varepsilon > 1$ for speed and gradually reduces it to converge toward optimal paths; without this strategy, incremental refinement in real-time systems like navigation aids is harder to achieve.
With IDA* (Iterative Deepening A*), the search is conducted by gradually increasing an $f$-cost threshold, greatly reducing memory usage but sometimes increasing runtime; without it, problems like puzzle solving could exceed memory limits.
RBFS and Fringe Search are memory-bounded alternatives that manage recursion depth or fringe sets more carefully; without these, large state spaces in AI planning can overwhelm storage.
In tie-breaking, preferring larger $g$ or smaller $h$ when $f$ ties reduces unnecessary re-expansions; without careful tie-breaking, searches on uniform-cost grids may explore more nodes than needed.
For the closed-set policy, when heuristics are inconsistent, nodes must be reopened if a better $g$ value is found; without allowing this, the algorithm may miss shorter paths, as in road networks with varying travel times.

Pitfalls & tips

The algorithm requires non-negative edge weights because A* assumes $w(u,v) \ge 0$; without this, negative costs can cause nodes to be expanded too early, breaking correctness in applications like navigation.
If the heuristic overestimates actual costs, A* loses its guarantee of optimality; without enforcing admissibility, a routing system may return a path that is faster to compute but longer in distance.
For floating-point weights, keep a consistent total ordering in the priority queue, for example by adding a unique tie-break counter. An epsilon-based heap comparator can violate transitivity. Relaxation tolerances may discard small improvements and must be treated as an approximation policy, not an automatic correctness fix.
In state hashing, equivalent states must hash identically so duplicates are merged properly; without this, search in puzzles or planning domains may blow up due to treating the same state as multiple distinct ones.
While neighbor order does not affect correctness, it influences performance and the aesthetics of the returned path trace; without considering this, two identical problems might yield very different expansion sequences or outputs.

Implementation:

C++
Python

Implementation tip: If your PQ lacks decrease-key, push duplicates with improved keys and ignore stale entries when popped (check if popped g matches current g[u]). This is simple and fast in practice.

Floyd–Warshall Algorithm

Floyd–Warshall computes the shortest distance between every pair of vertices at once. It keeps an $n \times n$ matrix and, for each vertex $k$ in turn, asks whether going through $k$ shortens the path from $i$ to $j$:

$$ dist[i][j] = \min(dist[i][j],\ dist[i][k] + dist[k][j]) $$

After the outer loop has handled $k$, dist[i][j] is the shortest path whose intermediate vertices all come from the first $k+1$ vertices. That invariant only holds if $k$ is the outermost loop. Negative edges are fine, and a negative cycle shows up as dist[i][i] < 0 at the end.

Reach for it when the problem asks about many pairs and $n$ is small. With $n = 400$ the triple loop does $6.4 \times 10^7$ steps, which is fine in compiled languages and about the practical limit in Python. In 1334 Find the City With the Smallest Number of Neighbors at a Threshold Distance, $n \le 100$: run Floyd–Warshall, count for each city how many others are within the threshold, and return the city with the smallest count, breaking ties by the larger index. The boolean version, with or and and in place of min and +, answers reachability queries such as 1462 Course Schedule IV.

First step: Build an $n \times n$ matrix with 0 on the diagonal, the edge weight for each edge (both directions if undirected, keeping the smaller weight for parallel edges), and infinity elsewhere. Check that $n^3$ fits the time limit before going further.

def floyd_warshall(n, edges):
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)
    for k in range(n):                       # intermediate vertex, outermost
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Time is $O(V^3)$ and space is $O(V^2)$. The most common mistake is putting k in an inner loop, which still runs without errors but returns wrong distances.

Minimum Spanning Trees

Suppose we have a graph that represents a network of houses. Weights represent the distances between vertices, which each represent a single house. All houses must have water, electricity, and internet, but we want the cost of installation to be as low as possible. We need to identify a subgraph of our graph with the following properties:

There are no cycles in the graph.
All vertices are connected.
The total sum of weights is minimum.

Such a subgraph is called a minimum spanning tree (MST). It minimizes total edge weight, not the distance from a chosen source to every other vertex. A disconnected graph has a minimum spanning forest, with one tree for each connected component.

Prim’s Algorithm

Prim’s algorithm builds a minimum spanning tree (MST) of a weighted, undirected graph by growing a tree from a start vertex. At each step it adds the cheapest edge that connects a vertex inside the tree to a vertex outside the tree.

First step: Confirm the graph is undirected, build a weighted adjacency list with both directions, and decide what a disconnected input should return. For a complete graph given as points, as in 1584 Min Cost to Connect All Points, skip the adjacency list and use the $O(V^2)$ array version that computes distances on the fly.

To efficiently keep track of the construction, Prim’s algorithm employs two primary data structures:

A min-priority queue (often named pq, open, or unexplored) keyed by a vertex’s best known connection cost to the current tree.
A in_mst/visited set to mark vertices already added to the tree, plus a parent map to record the chosen incoming edge for each vertex.

Useful additions in practice:

A key map stores, for each vertex, the lightest edge weight connecting it to the current spanning tree, initialized to infinity except for the starting vertex at zero; without this, Prim’s algorithm cannot efficiently track which edges should be added next to grow the tree.
With lazy updates, when the priority queue lacks a decrease-key operation, improved entries are simply pushed again and outdated ones are skipped upon popping; without this adjustment, priority queues become harder to manage, slowing down minimum spanning tree construction.
For component handling, if the graph is disconnected, Prim’s algorithm must either restart from each unvisited vertex or seed exactly one representative per connected component to produce a spanning forest; without this, the algorithm would stop after one component, leaving parts of the graph unspanned.

Algorithm Steps:

Pick a start vertex $i$.
Set key[i] = 0, parent[i] = None; for all other vertices $v \ne i$, set key[v] = ∞; push $i$ into a min-priority queue keyed by key.
While the priority queue is nonempty, repeat steps 4–6.
Extract the vertex $u$ with the smallest key[u].
If $u$ is already in the MST, continue; otherwise add $u$ to the MST and, if parent[u] ≠ None, record the tree edge (parent[u], u).
For each neighbor $v$ of $u$ with weight $w(u,v)$, if $v$ is not in the MST and $w(u,v) < key[v]$, set key[v] = w(u,v), set parent[v] = u, and push $v$ into the priority queue keyed by the new key[v].
Stop when the queue is empty or when all vertices are in the MST (for a connected graph).
The edges ${(parent[v], v) : v \ne i}$ form an MST; the MST total weight equals $\sum key[v]$ at the moments when each $v$ is added.

Vertices are finalized when they are dequeued: at that moment, key[u] is the minimum cost to connect u to the growing tree (by the cut property).

Reference pseudocode (adjacency-list graph):

Prim(G, i):
    INF = +infinity
    key    = defaultdict(lambda: INF)
    parent = {i: None}
    key[i] = 0

    pq = MinPriorityQueue()              # holds (key[v], v)
    pq.push((0, i))

    in_mst = set()
    mst_edges = []

    while pq:
        ku, u = pq.pop_min()             # smallest key
        if u in in_mst:
            continue
        in_mst.add(u)

        if parent[u] is not None:
            mst_edges.append((parent[u], u, ku))

        for (v, w_uv) in G[u]:           # undirected: each edge seen twice
            if v not in in_mst and w_uv < key[v]:
                key[v] = w_uv
                parent[v] = u
                pq.push((key[v], v))     # decrease-key or lazy insert

    return mst_edges, parent, sum(w for (_,_,w) in mst_edges)

Sanity notes:

The time complexity of Prim’s algorithm is $O(E \log V)$ with a binary heap, $O(E + V \log V)$ with a Fibonacci heap, and $O(V^2)$ for the dense-graph adjacency-matrix variant; without knowing this, one might apply the wrong implementation and get poor performance on sparse or dense networks.
An indexed queue requires $O(V)$ auxiliary space. The lazy duplicate-entry version shown can require $O(V+E)$ space and $O(V+E\log(E+2))$ time. On a connected simple graph, its time simplifies to $O(E\log V)$.
The graph type handled is a weighted, undirected graph with no restrictions on edge weights being positive; without this flexibility, graphs with negative costs, such as energy-saving transitions, could not be processed.
In terms of uniqueness, if all edge weights are distinct, the minimum spanning tree is unique; without distinct weights, multiple MSTs may exist, such as in networks where two equally light connections are available.

Example

Undirected, weighted graph; start at A. Edge weights shown on links.

#
               ┌────────┐
               │   A    │
               └─┬──┬───┘
                4│  │1
                 │  │
     ┌───────────┘  └───────────┐
     │                          │
┌────▼────┐                ┌────▼────┐
│   B     │◄──────2────────│   C     │
└───┬─────┘                └─────┬───┘
  1 │                          4 │
    │                            │
┌───▼────┐      3           ┌────▼───┐
│   E    │─────────────────▶│   D    │
└────────┘                  └────────┘

Edges: A–B(4), A–C(1), C–B(2), B–E(1), C–D(4), D–E(3)

Frontier (keys) / In-tree evolution (min at front):

Legend: key[v] = cheapest known connection to tree; parent[v] = chosen neighbor

Step | Action                          | PQ (key:vertex) after push         | In MST      | Updated keys / parents
-----+---------------------------------+------------------------------------+-------------+-------------------------------
0    | init at A                       | [0:A]                              | {}          | key[A]=0, others=∞
1    | pop A → add                     | [1:C, 4:B]                         | {A}         | key[C]=1 (A), key[B]=4 (A)
2    | pop C → add                     | [2:B, 4:D, 4:B]                    | {A,C}       | key[B]=min(4,2)=2 (C), key[D]=4 (C)
3    | pop B(2) → add                  | [1:E, 4:D, 4:B]                    | {A,C,B}     | key[E]=1 (B)
4    | pop E(1) → add                  | [3:D, 4:D, 4:B]                    | {A,C,B,E}   | key[D]=min(4,3)=3 (E)
5    | pop D(3) → add                  | [4:D, 4:B]                         | {A,C,B,E,D} | done

MST edges chosen (with weights):

A–C(1), C–B(2), B–E(1), E–D(3)
Total weight = 1 + 2 + 1 + 3 = 7

Resulting MST (tree edges only):

A
└── C (1)
    └── B (2)
        └── E (1)
            └── D (3)

Applications

In network design, Prim’s or Kruskal’s MST construction connects all sites such as offices, cities, or data centers with the least total cost of wiring, piping, or fiber; without using MSTs, infrastructure plans risk including redundant and more expensive links.
As an approximation for the traveling salesman problem (TSP), building an MST and performing a preorder walk of it yields a tour within twice the optimal length for metric TSP; without this approach, even approximate solutions for large instances may be much harder to obtain.
In clustering with single linkage, removing the $k-1$ heaviest edges of the MST partitions the graph into $k$ clusters; without this technique, hierarchical clustering may require recomputing pairwise distances repeatedly.
For image processing and segmentation, constructing an MST over pixels or superpixels connects similar regions with low-weight edges, while cutting selected high-weight edges can separate contrasting regions; without MST-based grouping, segmentations may fail to respect natural intensity or color edges.
In map generalization and simplification, the MST preserves a connectivity backbone with minimal redundancy, reducing complexity while maintaining essential routes; without this, simplified maps may show excessive or unnecessary detail.
In circuit design and VLSI, MSTs minimize interconnect length under simple wiring models, supporting efficient layouts; without this method, chip designs may consume more area and power due to avoidable wiring overhead.

Implementation:

C++
Python

Implementation tip: For dense graphs ($E \approx V^2$), skip heaps: store key in an array and, at each step, scan all non-MST vertices to pick the minimum key in $O(V)$. Overall $O(V^2)$ but often faster in practice on dense inputs due to low overhead.

Kruskal’s Algorithm

Kruskal’s algorithm builds a minimum spanning tree (MST) for a weighted, undirected graph by sorting all edges by weight (lightest first) and repeatedly adding the next lightest edge that does not create a cycle. It grows the MST as a forest of trees that gradually merges until all vertices are connected.

First step: Collect the edges as (weight, u, v) triples and sort them, then set up the structure from the Union-Find (Disjoint Set Union) section above; the helpers below are the same idea. Count accepted edges so you can stop at $V-1$ and notice when the graph is disconnected.

To efficiently keep track of the construction, Kruskal’s algorithm employs two primary data structures:

A sorted edge list arranged in ascending order of weights ensures that Kruskal’s algorithm always considers the lightest available edge next; without this ordering, the method cannot guarantee that the resulting spanning tree has minimum total weight.
A Disjoint Set Union (DSU), or Union–Find structure, tracks which vertices belong to the same tree and prevents cycles by only uniting edges from different sets; without this mechanism, the algorithm could inadvertently form cycles instead of building a spanning tree.

Useful additions in practice:

Using Union–Find with path compression and union by rank/size enables near-constant-time merge and find operations, making Kruskal’s algorithm efficient; without these optimizations, edge processing in large graphs such as communication networks would slow down significantly.
Applying an early stop allows the algorithm to terminate once $V-1$ edges have been added in a connected graph, since the MST is then complete; without this, unnecessary edges are still considered, adding avoidable work.
Enforcing deterministic tie-breaking ensures that when multiple edges share equal weights, the same MST is consistently produced; without this, repeated runs on the same weighted graph might yield different but equally valid spanning trees, complicating reproducibility.
On disconnected graphs, Kruskal’s algorithm naturally outputs a minimum spanning forest with one tree per component; without this property, handling graphs such as multiple separate road systems would require additional adjustments.

Algorithm Steps:

Gather all edges $E={(u,v,w)}$ and sort them by weight $w$ in ascending order.
Initialize a DSU with each vertex in its own set: parent[v]=v, rank[v]=0.
Traverse the edges in the sorted order.
For the current edge $(u,v,w)$, compute ru = find(u) and rv = find(v) in the DSU.
If ru ≠ rv, add $(u,v,w)$ to the MST and union(ru, rv).
If ru = rv, skip the edge (it would create a cycle).
Continue until $V-1$ edges have been chosen (connected graph) or until all edges are processed (forest).
The chosen edges form the MST; the total weight is the sum of their weights.

By the cycle and cut properties of MSTs, selecting the minimum-weight edge that crosses any cut between components is always safe; rejecting edges that close a cycle preserves optimality.

Reference pseudocode (edge list + DSU):

Kruskal(V, E):
    # V: iterable of vertices
    # E: list of edges (u, v, w) for undirected graph

    sort E by weight ascending

    make_set(v) for v in V        # DSU init: parent[v]=v, rank[v]=0

    mst_edges = []
    total = 0

    for (u, v, w) in E:
        if find(u) != find(v):
            union(u, v)
            mst_edges.append((u, v, w))
            total += w
            if len(mst_edges) == len(V) - 1:   # early stop if connected
                break

    return mst_edges, total

# Union-Find helpers (path compression + union by rank),
# see the Union-Find (Disjoint Set Union) section for details:
find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry: return
    if rank[rx] < rank[ry]:
        parent[rx] = ry
    elif rank[rx] > rank[ry]:
        parent[ry] = rx
    else:
        parent[ry] = rx
        rank[rx] += 1

Sanity notes:

The time complexity of Kruskal’s algorithm is dominated by sorting edges, which takes $O(E \log E)$, which is $O(E\log V)$ for simple graphs, while DSU operations run in near-constant amortized time; without recognizing this, one might wrongly attribute the main cost to the union–find structure rather than sorting.
The space complexity is $O(V)$ for the DSU arrays and $O(E)$ to store the edges; without this allocation, the algorithm cannot track connectivity or efficiently access candidate edges.
With respect to weights, Kruskal’s algorithm works on undirected graphs with either negative or positive weights; without this flexibility, cases like networks where some connections represent cost reductions could not be handled.
Regarding uniqueness, if all edge weights are distinct, the MST is guaranteed to be unique; without distinct weights, multiple equally valid minimum spanning trees may exist, such as in graphs where two different links have identical costs.

Example

Undirected, weighted graph (we’ll draw the key edges clearly and list the rest). Start with all vertices as separate sets: {A} {B} {C} {D} {E} {F}.

Top row:       A────────4────────B────────2────────C
               │                 │                 │
               │                 │                 │
               7                 3                 5
               │                 │                 │
Bottom row:    F────────1────────E────────6────────D

Other edges (not all drawn to keep the picture clean):
A–C(4), B–D(5), C–E(5), D–E(6), D–F(2)

Sorted edge list (ascending): E–F(1), B–C(2), D–F(2), B–E(3), A–B(4), A–C(4), B–D(5), C–D(5), C–E(5), D–E(6), A–F(7)

Union–Find / MST evolution (take the edge if it connects different sets):

Step | Edge (w)  | Find(u), Find(v) | Action      | Components after union            | MST so far                 | Total
-----+-----------+-------------------+------------+-----------------------------------+----------------------------+------
 1   | E–F (1)   | {E}, {F}          | TAKE       | {E,F} {A} {B} {C} {D}             | [E–F(1)]                   | 1
 2   | B–C (2)   | {B}, {C}          | TAKE       | {E,F} {B,C} {A} {D}               | [E–F(1), B–C(2)]           | 3
 3   | D–F (2)   | {D}, {E,F}        | TAKE       | {B,C} {D,E,F} {A}                 | [E–F(1), B–C(2), D–F(2)]   | 5
 4   | B–E (3)   | {B,C}, {D,E,F}    | TAKE       | {A} {B,C,D,E,F}                   | [..., B–E(3)]              | 8
 5   | A–B (4)   | {A}, {B,C,D,E,F}  | TAKE       | {A,B,C,D,E,F} (all connected)     | [..., A–B(4)]              | 12
     | (stop: we have V−1 = 5 edges for 6 vertices)

Resulting MST edges and weight:

E–F(1), B–C(2), D–F(2), B–E(3), A–B(4)    ⇒  Total = 1 + 2 + 2 + 3 + 4 = 12

Clean MST view (tree edges only):

A
└── B (4)
    ├── C (2)
    └── E (3)
        └── F (1)
            └── D (2)

Applications

In network design, Kruskal’s algorithm builds the least-cost backbone, such as roads, fiber, or pipelines, that connects all sites with minimal total expense; without MST construction, the resulting infrastructure may include redundant and costlier links.
For clustering with single linkage, constructing the MST and then removing the $k-1$ heaviest edges partitions the graph into $k$ clusters; without this method, grouping data points into clusters may require repeated and slower distance recalculations.
In image segmentation, applying Kruskal’s algorithm to pixel or superpixel graphs groups regions by intensity or feature similarity through MST formation; without MST-based grouping, boundaries between regions may be less well aligned with natural contrasts.
As an approximation for the metric traveling salesman problem, building an MST and performing a preorder walk (with shortcutting) yields a tour at most twice the optimal length; without this approach, near-optimal solutions would be harder to compute efficiently.
In circuit and VLSI layout, Kruskal’s algorithm finds minimal interconnect length under simplified wiring models; without this, designs may require more area and energy due to unnecessarily long connections.
For maze generation, a randomized Kruskal process selects edges in random order while maintaining acyclicity, producing mazes that remain connected without loops; without this structure, generated mazes could contain cycles or disconnected regions.

Implementation:

C++
Python

Implementation tip: On huge graphs that stream from disk, you can external-sort edges by weight, then perform a single pass with DSU. For reproducibility across platforms, stabilize sorting by (weight, min(u,v), max(u,v)).

Topological Sort

Topological sort orders the vertices of a directed acyclic graph (DAG) so that every directed edge $u \rightarrow v$ goes from left to right in the order (i.e., $u$ appears before $v$). It’s the canonical tool for scheduling tasks with dependencies.

First step: Decide the edge direction from the wording (in 207 Course Schedule, the pair [a, b] means take b before a, so the edge is b → a). Build the adjacency list and the indegree array in the same pass, and include every vertex, even ones with no edges.

To efficiently keep track of the process (Kahn’s algorithm), we use:

A queue (or min-heap if you want lexicographically smallest order) holding all vertices with indegree = 0 (no unmet prerequisites).
An indegree map/array that counts for each vertex how many prerequisites remain.
An order list to append vertices as they are “emitted.”

Useful additions in practice:

Maintaining a visited count or tracking the length of the output order lets you detect cycles, since producing fewer than $V$ vertices indicates that some could not be placed due to a cycle; without this check, algorithms like Kahn’s may silently return incomplete results on cyclic task graphs.
Using a min-heap instead of a simple FIFO queue ensures that, among available candidates, the smallest-indexed vertex is always chosen, yielding the lexicographically smallest valid topological order; without this modification, the output order depends on arbitrary queueing, which may vary between runs.
A DFS-based alternative computes a valid topological order by recording vertices in reverse postorder, also in $O(V+E)$ time, while detecting cycles via a three-color marking or recursion stack. Kahn’s algorithm detects cycles differently, through the output count described above.

Algorithm Steps (Kahn’s algorithm)

Compute indegree[v] for every vertex $v$; set order = [].
Initialize a queue Q with all vertices of indegree 0.
While Q is nonempty, repeat steps 4–6.
Dequeue a vertex u from Q and append it to order.
For each outgoing edge u → v, decrement indegree[v] by 1.
If indegree[v] becomes 0, enqueue v into Q.
If len(order) < V at the end, a cycle exists and no topological order; otherwise order is a valid topological ordering.

Reference pseudocode (adjacency-list graph):

TopoSort_Kahn(G):
    # G[u] = iterable of neighbors v with edge u -> v
    V = all_vertices(G)
    indeg = {v: 0 for v in V}
    for u in V:
        for v in G[u]:
            indeg[v] += 1

    Q = Queue()
    for v in V:
        if indeg[v] == 0:
            Q.enqueue(v)

    order = []

    while not Q.empty():
        u = Q.dequeue()
        order.append(u)
        for v in G[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                Q.enqueue(v)

    if len(order) != len(V):
        return None    # cycle detected
    return order

Sanity notes:

With a FIFO queue, time is $O(V+E)$. The min-heap variant used in the example gives the lexicographically smallest order in $O(E+V\log V)$ time. Both require $O(V)$ auxiliary storage.
The space complexity is $O(V)$, required for storing indegree counts, the processing queue, and the final output order; without allocating this space, the algorithm cannot track which vertices are ready to be placed.
The required input is a directed acyclic graph (DAG), since if a cycle exists, no valid topological order is possible; without this restriction, attempts to schedule cyclic dependencies, such as tasks that mutually depend on each other, will fail.

Example

DAG; we’ll start with all indegree-0 vertices. (Edges shown as arrows.)

A ----> C ----> D
        ^ \     ^
        |  v    |
B ------+   E --+
|
v
G           F (isolated)

Edges: A→C, B→C, C→D, C→E, E→D, B→G

Initial indegrees:

indeg[A]=0, indeg[B]=0, indeg[C]=2, indeg[D]=2, indeg[E]=1, indeg[F]=0, indeg[G]=1

Queue/Indegree evolution (front → back; assume we keep the queue lexicographically by using a min-heap):

Step | Pop u | Emit order            | Decrease indeg[...]   | Newly 0 → Enqueue | Q after
-----+-------+-----------------------+-----------------------+-------------------+-----------------
0    | ,      | []                    | ,                      | A, B, F           | [A, B, F]
1    | A     | [A]                   | C:2→1                 | ,                  | [B, F]
2    | B     | [A, B]                | C:1→0, G:1→0          | C, G              | [C, F, G]
3    | C     | [A, B, C]             | D:2→1, E:1→0          | E                 | [E, F, G]
4    | E     | [A, B, C, E]          | D:1→0                 | D                 | [D, F, G]
5    | D     | [A, B, C, E, D]       | ,                      | ,                  | [F, G]
6    | F     | [A, B, C, E, D, F]    | ,                      | ,                  | [G]
7    | G     | [A, B, C, E, D, F, G] | ,                      | ,                  | []

A valid topological order:

A, B, C, E, D, F, G (others like B, A, C, E, D, F, G are also valid.)

Cycle detection (why it fails on cycles)

If there’s a cycle, some vertices never reach indegree 0. Example:

X --> Y
X <-- Y

Here indeg[X]=indeg[Y]=1 initially; Q starts empty ⇒ order=[] and len(order) < V ⇒ cycle reported.

Applications

In build systems and compilation, topological sorting ensures that each file is compiled only after its prerequisites are compiled; without it, a build may fail by trying to compile a module before its dependencies are available.
For course scheduling, topological order provides a valid sequence in which to take courses respecting prerequisite constraints; without it, students may be assigned courses they are not yet eligible to take.
In data pipelines and DAG workflows such as Airflow or Spark, tasks are executed when their inputs are ready by following a topological order; without this, pipeline stages might run prematurely and fail due to missing inputs.
For dependency resolution in package managers or container systems, topological sorting installs components in an order that respects their dependencies; without it, software may be installed in the wrong sequence and break.
In dynamic programming on DAGs, problems like longest path, shortest path, or path counting are solved efficiently by processing vertices in topological order; without this ordering, subproblems may be computed before their dependencies are solved.
For circuit evaluation or spreadsheets, topological order ensures that each cell or net is evaluated only after its referenced inputs; without it, computations could use undefined or incomplete values.

Related exercises enumerate topological orderings using backtracking; the Kahn procedure above computes one ordering directly.

C++
Python

Implementation tips:

Use a deque for FIFO behavior; use a min-heap to get the lexicographically smallest topological order.
When the graph is large and sparse, store adjacency as lists and compute indegrees in one pass for $O(V+E)$.
DFS variant (brief): color states 0=unseen,1=visiting,2=done; on exploring u, mark 1; DFS to neighbors; if you see 1 again, there’s a cycle; on finish, push u to a stack. Reverse the stack for the order.

Eulerian Paths with Hierholzer’s Algorithm

An Eulerian path uses every edge exactly once. Problems hide it behind words like "use all the tickets", "each domino once", or "a string containing every code". The existence conditions are in the terminology list at the top: all edges must lie in one connected piece, and an undirected graph needs zero or two odd-degree vertices. In a directed graph every vertex must have equal indegree and outdegree, except that one vertex may have one extra outgoing edge (the start) and one may have one extra incoming edge (the end).

Hierholzer’s algorithm builds the path in linear time. Walk from the start along unused edges, deleting each edge as you use it. When you reach a vertex with no unused edges left, append it to the result and step back. The result comes out in reverse, so reverse it at the end. When the conditions hold, the first vertex where the walk gets stuck must be the end of the whole path, which is why the post-order append is correct. Any cycle the walk skipped is spliced in automatically when the recursion steps back to a vertex that still has unused edges.

First step: Check the degree conditions and choose the start: the vertex with one extra outgoing edge if there is one, otherwise any vertex that has edges. Store each adjacency list so used edges can be removed cheaply, for example sorted in reverse so pop() returns the smallest neighbor.

332 Reconstruct Itinerary asks for the lexicographically smallest itinerary from "JFK" that uses every ticket. Always taking the smallest airport first is not enough on its own, because it can walk into a dead end too early. The post-order append fixes this, since the dead end is appended first and therefore ends up last in the reversed route.

def find_itinerary(tickets):
    G = defaultdict(list)
    for a, b in sorted(tickets, reverse=True):
        G[a].append(b)                       # reverse order: pop() gives smallest
    route = []

    def visit(u):
        while G[u]:
            visit(G[u].pop())                # each edge is used once
        route.append(u)                      # post-order: append when stuck

    visit("JFK")
    return route[::-1]

In an undirected graph each edge sits in two adjacency lists, so give edges ids and keep a used array instead of popping from one side only. The same algorithm solves 753 Cracking the Safe (a de Bruijn sequence) and 2097 Valid Arrangement of Pairs. The repository’s Python implementation uses Fleury’s algorithm instead, which avoids bridges at every step and is easier to follow but costs about $O(E \cdot (V+E))$ with simple bridge checks.

Hierholzer runs in $O(V+E)$ time, plus $O(E \log E)$ when neighbors must be sorted, and $O(V+E)$ space; the recursion can be $E$ deep, so large inputs need an explicit stack. The most common mistake is appending a vertex when it is first visited instead of when it gets stuck, which gives a wrong route whenever the walk hits a dead end early.

Reading the Problem Statement

Graph problems are usually decided by a few words in the statement and by the constraints. This table maps the common phrases to what they mean for your code.

If the problem says	What it means for your code
"undirected", "bidirectional", "two-way", or "friends"	Add every edge in both directions when building the adjacency list.
Nothing promises the graph is connected	Loop over all vertices and start a search from each unvisited one; the number of starts is the number of components.
"tree", or n nodes with n - 1 edges	Connected and acyclic, so every path is unique; to validate a tree, check for exactly n - 1 edges and one component.
"prerequisites", "order", "depends on", "must come before"	A directed acyclic graph; use Kahn's algorithm, and fewer than n vertices in the output means a cycle.
"group", "merge", "same set", "redundant edge"	Union-Find; the first union whose two ends are already joined is the redundant edge.
"no two adjacent the same", or "split into two groups"	Bipartite 2-coloring with BFS or DFS, started from every uncolored vertex.
"minimum steps", "moves", or "minutes" on an unweighted graph	BFS; with several starting points, put all of them in the queue together at distance 0.
Every move costs 0 or 1	0-1 BFS with a deque, pushing 0-cost moves to the front.
Non-negative weights, "cheapest", "fastest"	Dijkstra with a min-heap and a check that skips stale entries.
Negative weights, or "at most k stops"	Bellman–Ford; for k stops run k + 1 passes, each reading from a copy of dist.
"minimize the maximum", "the largest step on the path"	Minimax Dijkstra with max instead of plus, or binary search on the answer plus BFS.
"maximum probability", or a product of factors at most 1	Dijkstra with a max-heap on the product.
All pairs, or many pair queries, with n up to a few hundred	Floyd–Warshall with k as the outermost loop.
"minimum cost to connect all"	Minimum spanning tree with Kruskal or Prim.
"use every edge (or ticket) exactly once"	Eulerian path; check degrees, then Hierholzer with post-order append and a final reverse.
"critical connection", or removing it disconnects the network	Bridges (articulation points for vertices) with low-link values from one DFS.
"eventually safe", "every path ends at a terminal"	Three-color DFS, or Kahn's algorithm on the reversed graph.
A grid of cells	Each cell is a node with 4 or 8 neighbors; check bounds before indexing.
Nodes labeled 1 to n	Shift every label by one or allocate n + 1 slots.
Edges given as a list of pairs	Build the adjacency list (and indegree array if directed) before anything else.
Nodes are strings such as words, emails, or airports	Map each string to an integer id, or key a dictionary by the string.
n up to $10^5$ or more	You need $O(V+E)$ or $O(E \log V)$, and deep recursion in Python needs an iterative version.
n up to a few hundred	$O(V^3)$ algorithms such as Floyd–Warshall are acceptable.

Navigation Menu

Repository navigation

graphs.md

graphs.md

Graphs

Graph Terminology

Representation of Graphs in Computer Memory

Adjacency Matrix

Adjacency List

Planarity

What is a planar graph?

Kuratowski’s & Wagner’s characterizations

Handy planar edge bounds (quick tests)

Examples

How to check planarity in practice

Traversals

Breadth-First Search (BFS)

Depth-First Search (DFS)

Common BFS and DFS Patterns

Graph Coloring

Bridges, Articulation Points, and Strongly Connected Components

Union-Find (Disjoint Set Union)

Shortest paths

Dijkstra’s Algorithm

Dijkstra Variants: Minimax Paths and Maximum Probability

Bellman–Ford Algorithm

Shortest Paths With at Most k Edges

A* (A-Star) Algorithm

Floyd–Warshall Algorithm

Minimum Spanning Trees

Prim’s Algorithm

Kruskal’s Algorithm

Topological Sort

Eulerian Paths with Hierholzer’s Algorithm

Reading the Problem Statement

FilesExpand file tree

graphs.md

Latest commit

History

graphs.md

File metadata and controls

Graphs

Graph Terminology

Representation of Graphs in Computer Memory

Adjacency Matrix

Adjacency List

Planarity

What is a planar graph?

Kuratowski’s & Wagner’s characterizations

Handy planar edge bounds (quick tests)

Examples

How to check planarity in practice

Traversals

Breadth-First Search (BFS)

Depth-First Search (DFS)

Common BFS and DFS Patterns

Graph Coloring

Bridges, Articulation Points, and Strongly Connected Components

Union-Find (Disjoint Set Union)

Shortest paths

Dijkstra’s Algorithm

Dijkstra Variants: Minimax Paths and Maximum Probability

Bellman–Ford Algorithm

Shortest Paths With at Most k Edges

A* (A-Star) Algorithm

Floyd–Warshall Algorithm

Minimum Spanning Trees

Prim’s Algorithm

Kruskal’s Algorithm

Topological Sort

Eulerian Paths with Hierholzer’s Algorithm

Reading the Problem Statement