Last modified: January 02, 2026

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.

The reason graphs matter isn’t just 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 the moment graphs stop being a picture and become a tool.

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.

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.

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

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:

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

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

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.

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:

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.

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

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

These give fast non-planarity proofs:

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

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

  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.

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.

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.

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.

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

Useful additions in practice:

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

  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.

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.

To track the traversal efficiently, DFS typically uses:

Useful additions in practice:

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

  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

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

Applications

Implementation

Implementation tips:

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.

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

└── 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):

└── 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.)

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: