Last modified: August 31, 2025

This article is written in: πŸ‡ΊπŸ‡Έ

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.

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 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:

Representation of Graphs in Computer Memory

Graphs, with their versatile applications in numerous domains, necessitate efficient storage and manipulation mechanisms in computer memory. The choice of representation often depends on the graph's characteristics (e.g., dense vs. sparse, directed vs. undirected, weighted vs. unweighted) and the specific operations to be performed. Among the various methods available, the adjacency matrix and the adjacency list are the most prevalent.

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:

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

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

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

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.

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.

Euler’s Formula (connected planar graphs):

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

Kuratowski’s & Wagner’s characterizations

These are equivalent β€œforbidden pattern” views.

Handy planar edge bounds (quick tests)

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

These give fast non-planarity proofs:

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
   / \
  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.

How to check planarity in practice

For small graphs

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

For large graphs (efficient algorithms)

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

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.

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)

Breadth-First Search (BFS) is a fundamental 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:

Useful additions in practice:

Algorithm Steps

  1. Pick a start vertex $i$.
  2. Set visited = {i}, parent[i] = None, optionally dist[i] = 0, and enqueue $i$ into queue.
  3. While queue is nonempty, repeat steps 4–5.
  4. Dequeue the front vertex u.
  5. 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.
  6. 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   = [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)

Depth-First Search (DFS) is a fundamental 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:

Useful additions in practice:

Algorithm Steps

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

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:

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.

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

Useful additions in practice:

Algorithm Steps

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

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

Useful additions in practice:

Algorithm Steps

  1. Pick a start vertex $i$.
  2. Set dist[i] = 0 and parent[i] = None; for all other vertices $v \ne i$, set dist[v] = ∞.
  3. 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.
  4. (Optional) Detect negative cycles: if any edge $(u,v,w)$ still satisfies 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.
  5. 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:

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

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* (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:

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

  1. Put start in open (a min-priority queue by f); set g[start]=0, f[start]=h(start), parent[start]=None; initialize closed = βˆ….
  2. While open is nonempty, repeat steps 3–7.
  3. Pop the node u with the smallest f(u) from open.
  4. If u is the goal, reconstruct the path by following parent back to start and return it.
  5. Add u to closed.
  6. For each neighbor v of u with edge cost $w(u,v) \ge 0$, set tentative = g[u] + w(u,v).
  7. 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).
  8. If the loop ends because 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.

Minimal 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:

Such a subgraph is called a minimal spanning tree.

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.

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

Useful additions in practice:

Algorithm Steps

  1. Pick a start vertex $i$.
  2. 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.
  3. While the priority queue is nonempty, repeat steps 4–6.
  4. Extract the vertex $u$ with the smallest key[u].
  5. 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).
  6. 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].
  7. Stop when the queue is empty or when all vertices are in the MST (for a connected graph).
  8. 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:

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

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.

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

Useful additions in practice:

Algorithm Steps

  1. Gather all edges $E={(u,v,w)}$ and sort them by weight $w$ in ascending order.
  2. Initialize a DSU with each vertex in its own set: parent[v]=v, rank[v]=0.
  3. Traverse the edges in the sorted order.
  4. For the current edge $(u,v,w)$, compute ru = find(u) and rv = find(v) in the DSU.
  5. If ru β‰  rv, add $(u,v,w)$ to the MST and union(ru, rv).
  6. If ru = rv, skip the edge (it would create a cycle).
  7. Continue until $V-1$ edges have been chosen (connected graph) or until all edges are processed (forest).
  8. 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):
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

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:

Useful additions in practice:

Algorithm Steps (Kahn’s algorithm)

  1. Compute indegree[v] for every vertex $v$; set order = [].
  2. Initialize a queue Q with all vertices of indegree 0.
  3. While Q is nonempty, repeat steps 4–6.
  4. Dequeue a vertex u from Q and append it to order.
  5. For each outgoing edge u β†’ v, decrement indegree[v] by 1.
  6. If indegree[v] becomes 0, enqueue v into Q.
  7. 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:

Example

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

β”Œβ”€β”€β”€β”€β”€β”€β”€β”
                           β”‚   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:

Table of Contents

    Graphs
    1. Graph Terminology
    2. Representation of Graphs in Computer Memory
      1. Adjacency Matrix
      2. Adjacency List
    3. Planarity
      1. What is a planar graph?
      2. Kuratowski’s & Wagner’s characterizations
      3. Handy planar edge bounds (quick tests)
      4. Examples
      5. How to check planarity in practice
    4. Traversals
      1. Breadth-First Search (BFS)
      2. Depth-First Search (DFS)
    5. Shortest paths
      1. Dijkstra’s Algorithm
      2. Bellman–Ford Algorithm
      3. A* (A-Star) Algorithm
    6. Minimal Spanning Trees
      1. Prim’s Algorithm
      2. Kruskal’s Algorithm
    7. Topological Sort