Last modified: September 25, 2025
This article is written in: πΊπΈ
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.
Some real-world examples include:
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.
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:
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.
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 exists0
or β
(or None
) indicates βno edgeβ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
Benefits
Drawbacks
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
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
Benefits
Drawbacks
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))$ (find & delete) |
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.
Hybrids/Alternatives:
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.
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.
Eulerβs Formula (connected planar graphs):
$$ |V| - |E| + |F| = 2 $$
$$ \text{(for (c) connected components: } |V|-|E|+|F|=1+c) $$
These are equivalent βforbidden patternβ views.
For a simple planar graph with $|V|\ge 3$:
These give fast non-planarity proofs:
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
/ \
BβββC
\ /
D
All edges meet only at vertices; no crossings.
III. Complete graph on five vertices $K_5$ (non-planar)
No drawing avoids crossings. Even a βbest effortβ forces at least one:
AβββB
ββ² β±β
β β³ β (some crossing is unavoidable)
ββ± β²β
DβββC
\ /
E
The edge bound $10>9$ (above) certifies non-planarity.
IV. Complete bipartite $K_{3,3}$ (non-planar)
Two sets ${u_1,u_2,u_3}$ and ${v_1,v_2,v_3}$, all cross-set pairs connected:
u1 u2 u3
β \ β \ β \
β \ β \ β \
v1βββv2βββv3 (many edges must cross in the plane)
The bipartite bound $9>8$ proves non-planarity.
For small graphs
For large graphs (efficient algorithms)
Both are widely used in graph drawing, EDA (circuit layout), GIS, and network visualization.
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.
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.
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.
To efficiently keep track of the traversal, BFS employs two primary data structures:
queue
or unexplored
) that stores vertices pending exploration in first-in, first-out (FIFO) order.visited
set (or boolean array) that records which vertices have already been discovered to prevent revisiting.Useful additions in practice:
parent
map to reconstruct shortest paths (store parent[child] = current
when you first discover child
).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
).Algorithm Steps
visited = {i}
, parent[i] = None
, optionally dist[i] = 0
, and enqueue $i$ into queue
.queue
is nonempty, repeat steps 4β5.u
.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
.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 = [i]
order = [] # optional: visitation order
while queue:
u = queue.pop(0) # dequeue
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:
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
Implementation
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.
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.
To track the traversal efficiently, DFS typically uses:
visited
set (or boolean array) to avoid revisiting vertices.Useful additions in practice:
parent
map to reconstruct paths and build the DFS tree (parent[child] = current
on discovery).tin[u]
on entry, tout[u]
on exit) to reason about edge types, topological order, and low-link computations.order
lists: pre-order (on entry) and post-order (on exit).Algorithm Steps
visited[v]=False
for all $v$; optionally set parent[v]=None
; set a global timer t=0
.visited[u]=True
, record tin[u]=t++
(and keep parent[u]=None
if $u=i$).visited[v]=False
, set parent[v]=u
and visit $v$ (recurse/push), then resume scanning $u$βs neighbors.tout[u]=t++
and backtrack (return or pop).Mark vertices when first discovered (on entry/push) to prevent infinite loops in cyclic graphs.
Pseudocode (recursive, adjacency list):
time = 0
DFS(G, i):
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]
while stack:
u = stack.pop() # take the top
if u in visited:
continue
visited.add(u)
order.append(u)
# Push neighbors in reverse of desired visiting order
for v in reversed(G[u]):
if v not in visited:
parent[v] = u
stack.append(v)
return order, parent
Sanity notes:
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
Implementation
Implementation tips:
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 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.
To efficiently keep track of the traversal, Dijkstraβs algorithm employs two primary data structures:
pq
, open
, or unexplored
) keyed by each vertexβs current best known distance from the start.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:
Algorithm Steps
dist[i] = 0
and parent[i] = None
; for all other vertices $v \ne i$, set dist[v] = β
.dist[Β·]
.dist[u]
.dist[u] + w(u,v) < dist[v]
.dist[v] = dist[u] + w(u,v)
, set parent[v] = u
, and push $v$ into the priority queue keyed by the new dist[v]
.parent[Β·]
backward from the target to $i$.Vertices are finalized when they are dequeued (popped) from the priority queue. With non-negative weights, once a vertex is popped the recorded dist
is provably optimal.
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:
Example
Weighted, undirected graph; start at A. Edge weights are on the 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)
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
Implementation
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.
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.
To efficiently keep track of the computation, BellmanβFord employs two primary data structures:
dist
map (or array) with the best-known distance to each vertex (initialized to β except the start).parent
map to reconstruct shortest paths (store parent[v] = u
when relaxing edge $u!\to!v$).Useful additions in practice:
Algorithm Steps
dist[i] = 0
and parent[i] = None
; for all other vertices $v \ne i$, set dist[v] = β
.dist[u] + w < dist[v]
, set dist[v] = dist[u] + w
and parent[v] = u
. If a full pass makes no changes, stop early.dist[u] + w < dist[v]
, a reachable negative cycle exists. To extract one, follow parent
from $v$ for $V$ steps to enter the cycle, then continue until a vertex repeats, collecting the cycle.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:
Example
Directed, weighted graph; start at A. (Negative edges allowed; no negative cycles here.)
#
βββββββββββ
β A β
ββββ¬ββββ¬βββ
4 β β 2
β βββββββββββββββββ
ββββββββββββΌββββ -1 βββββΌββββββ
β B β ββββββββββΊβ C β
ββββββββ¬ββββββββ ββββ¬βββββββ
2 β 5 β
β β
ββββββββΌβββββββ -3 βββββΌββββββ
β D β ββββββββ β E β
ββββββββββββββββ βββββββββββ
Also:
A β C (2)
C β B (1)
C β E (3)
(Edges shown with weights on arrows)
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
(AβB=4, AβC=2; CβB improved B to 3; BβD=5? (via B gives 6); DβE=-3 gives 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
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.
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:
If $h$ is admissible (never overestimates) and consistent (triangle inequality), A is optimal* and never needs to βreopenβ closed nodes.
Core data structures
Algorithm Steps
start
in open
(a min-priority queue by f
); set g[start]=0
, f[start]=h(start)
, parent[start]=None
; initialize closed = β
.open
is nonempty, repeat steps 3β7.u
with the smallest f(u)
from open
.u
is the goal, reconstruct the path by following parent
back to start
and return it.u
to closed
.v
of u
with edge cost $w(u,v) \ge 0$, set tentative = g[u] + w(u,v)
.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).open
is empty, no path exists.Mark neighbors when you enqueue them (by storing their best g
) to avoid duplicate work; with consistent $h$, any node popped from open
is final and will not improve later.
Reference pseudocode
A_star(G, start, goal, h):
open = MinPQ() # keyed by f = g + h
open.push(start, h(start))
g = {start: 0}
parent = {start: None}
closed = set()
while open:
u = open.pop_min() # node with smallest f
if u == goal:
return reconstruct_path(parent, goal), g[goal]
closed.add(u)
for (v, w_uv) in G.neighbors(u): # w_uv >= 0
tentative = g[u] + w_uv
if v in closed and tentative >= g.get(v, +inf):
continue
if tentative < g.get(v, +inf):
parent[v] = u
g[v] = tentative
f_v = tentative + h(v)
open.push(v, f_v) # decrease-key OR push new entry
return None, +inf
reconstruct_path(parent, t):
path = []
while t is not None:
path.append(t)
t = parent[t]
return list(reversed(path))
Sanity notes:
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:
Final path (example rendering):
Row/Col β 1 2 3 4 5 6 7 8 9
βββββββββββββββββββββββββββββββ
1 β Γ Γ Γ Γ . # . . . β
2 β Γ # # Γ Γ # . # . β
3 β Γ Γ Γ Γ Γ Γ Γ # . β
4 β # . # # Γ # Γ Γ Γ β
5 β . . . # Γ Γ Γ # G β
βββββββββββββββββββββββββββββββ
Path length (g at G) equals number of Γ steps (optimal with admissible/consistent h).
Priority queue evolution (toy example)
Step | Popped u | Inserted neighbors (v: g,h,f) | Note
-----+----------+-------------------------------------------------+---------------------------
0 | β | push S: g=0, h=14, f=14 | S at (1,1), G at (5,9)
1 | S | (1,2): g=1,h=13,f=14 ; (2,1): g=1,h=12,f=13 | pick (2,1) next
2 | (2,1) | (3,1): g=2,h=11,f=13 ; (2,2) blocked | ...
3 | (3,1) | (4,1) wall; (3,2): g=3,h=10,f=13 | still f=13 band
β¦ | β¦ | frontier slides along the corridor toward G | A* hugs the beeline
(Exact numbers depend on the specific grid and walls; shown for intuition.)
Heuristic design
For grids:
For sliding puzzles (e.g., 8/15-puzzle):
Misplaced tiles (admissible, weak). * Manhattan sum (stronger). * Linear conflict / pattern databases* (even stronger).
Admissible vs. consistent
Applications
Variants & practical tweaks
Pitfalls & tips
Implementation
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.
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:
Such a subgraph is called a minimal spanning tree.
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.
To efficiently keep track of the construction, Primβs algorithm employs two primary data structures:
pq
, open
, or unexplored
) keyed by a vertexβs best known connection cost to the current tree.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:
Algorithm Steps
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
.key[u]
.parent[u] β None
, record the tree edge (parent[u], u)
.key[v] = w(u,v)
, set parent[v] = u
, and push $v$ into the priority queue keyed by the new key[v]
.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:
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
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 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.
To efficiently keep track of the construction, Kruskalβs algorithm employs two primary data structures:
Useful additions in practice:
Algorithm Steps
parent[v]=v
, rank[v]=0
.ru = find(u)
and rv = find(v)
in the DSU.ru β rv
, add $(u,v,w)$ to the MST and union(ru, rv)
.ru = rv
, skip the edge (it would create a cycle).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):
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:
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
Implementation
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 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.
To efficiently keep track of the process (Kahnβs algorithm), we use:
indegree
map/array that counts for each vertex how many prerequisites remain.order
list to append vertices as they are βemitted.βUseful additions in practice:
Algorithm Steps (Kahnβs algorithm)
indegree[v]
for every vertex $v$; set order = []
.Q
with all vertices of indegree 0.Q
is nonempty, repeat steps 4β6.u
from Q
and append it to order
.u β v
, decrement indegree[v]
by 1.indegree[v]
becomes 0, enqueue v
into Q
.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:
Example
DAG; weβll start with all indegree-0 vertices. (Edges shown as arrows.)
DAG
βββββββββ
β A β
βββββ¬ββββ
β
β
βββββββββ βββββΌββββ βββββββββ
β B ββββββββββββ C ββββββββββββ D β
βββββ¬ββββ βββββ¬ββββ βββββ¬ββββ
β β β
β β β
β βββββΌββββ β
β β E ββββββββββββββββ
β βββββ¬ββββ
β β
β β
βββββΌββββ βββββΌββββ
β G β β F β
βββββββββ βββββββββ
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.)
Clean left-to-right view (one possible ordering):
A B F C E D G
β β β β β
ββββΊββββΊ ββββΊββββΊββββΊ (all arrows go leftβright)
Cycle detection (why it fails on cycles)
If thereβs a cycle, some vertices never reach indegree 0. Example:
βββββββ βββββββ
β X β ββββΊ β Y β
ββββ¬βββ ββββ¬βββ
βββββββββββββΊβ
(Y ββββΊ X creates a cycle)
Here indeg[X]=indeg[Y]=1
initially; Q
starts empty β order=[]
and len(order) < V
β cycle reported.
Applications
Implementation
Implementation tips:
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.