14.14 Graph Greedy

Many of the most successful graph algorithms are greedy algorithms.

algorithmsgreedy

14.14 Graph Greedy

Many of the most successful graph algorithms are greedy algorithms. At first glance, this may seem surprising. Graphs contain complex global structure. A local decision on one edge can affect paths, connectivity, cycles, and costs throughout the entire graph.

Yet some graph problems possess exactly the structural properties that greedy algorithms require. In these cases, local choices can be proven safe through cut properties, exchange arguments, or matroid theory. The resulting algorithms are among the most efficient in computer science.

This recipe introduces the graph greedy pattern and develops the ideas that unify algorithms such as Kruskal's minimum spanning tree algorithm, Prim's algorithm, and Dijkstra's shortest path algorithm.

Problem

Given a graph:

$$ G = (V,E) $$

find an optimal structure such as:

  • A spanning tree
  • A shortest path tree
  • A connectivity structure
  • A minimum-cost network

The challenge is determining whether local edge choices can safely contribute to a globally optimal solution.

Why Graph Greedy Is Different

In interval scheduling, choosing one interval affects only neighboring intervals.

In graph problems, a single edge may affect:

  • Connectivity
  • Reachability
  • Cycles
  • Path lengths
  • Future edge choices

This makes correctness proofs substantially more challenging.

The key question becomes:

Which graph edges are guaranteed to belong to some optimal solution?

Once such edges can be identified, greedy algorithms become possible.

Example: Minimum Spanning Tree

Given a connected weighted graph:

      4
 A -------- B
 |          |
 |1        3|
 |          |
 C -------- D
      2

Goal:

Connect all vertices while minimizing total edge weight.

A spanning tree contains:

|V| - 1

edges and no cycles.

A graph with:

m

edges contains exponentially many subsets.

Checking all spanning trees quickly becomes impractical.

We need a more direct strategy.

Greedy Observation

Suppose the smallest edge in the graph has weight:

1

Can an optimal spanning tree exclude it?

Often the answer is no.

This observation motivates a greedy rule:

Prefer small edges whenever possible.

The challenge is proving which small edges are safe.

The Cut Property

Consider any partition of vertices:

Left side
Right side

Among all edges crossing the partition, choose the minimum-weight edge.

The cut property states:

That edge belongs to some minimum spanning tree.

This is one of the most important theorems in greedy algorithm design.

It transforms a local statement:

This edge is cheapest across a cut.

into a global statement:

This edge is safe to include.

Kruskal's Algorithm

The simplest MST algorithm follows directly.

Step 1

Sort all edges by weight.

Step 2

Process edges from smallest to largest.

Step 3

Add an edge if it does not create a cycle.

Pseudo-code:

Sort edges by weight

For each edge:
    If edge creates no cycle:
        Add edge

The algorithm stops after:

|V| - 1

edges have been selected.

Example

Edges:

Edge Weight
A-C 1
C-D 2
B-D 3
A-B 4

Process:

Take A-C
Take C-D
Take B-D

Now all vertices are connected.

Tree weight:

$$ 1 + 2 + 3 = 6 $$

The final edge:

A-B

would create a cycle and is rejected.

Why Kruskal Works

Suppose Kruskal chooses edge:

e

and an optimal spanning tree does not contain it.

Add:

e

to the tree.

A cycle appears.

Within that cycle exists another edge:

f

whose weight is at least as large.

Replace:

f

with:

e

The resulting tree remains connected.

Total weight does not increase.

Therefore an optimal tree exists containing:

e

This exchange argument proves the greedy choice.

Union-Find

Kruskal requires fast cycle detection.

A disjoint-set structure supports:

Find
Union

operations efficiently.

For each edge:

if Find(u) != Find(v) {
    Union(u, v)
}

This determines whether two vertices already belong to the same component.

Complexity

Sorting:

$$ O(E \log E) $$

Union-find operations:

$$ O(E \alpha(V)) $$

Total:

$$ O(E \log E) $$

which is dominated by sorting.

Prim's Algorithm

Prim approaches the same problem differently.

Instead of sorting all edges once, it grows a tree incrementally.

Start with an arbitrary vertex.

Repeatedly:

Add the cheapest edge connecting the current tree to a new vertex.

This again relies on the cut property.

The current tree defines a cut.

The minimum crossing edge is always safe.

Example

Start:

A

Available edges:

A-C (1)
A-B (4)

Choose:

A-C

Now:

A C

Available crossing edges:

C-D (2)
A-B (4)

Choose:

C-D

Continue until all vertices are included.

Priority Queue Implementation

Prim naturally uses a min-heap.

heap.Push(pq, edge)

Each step extracts:

edge := heap.Pop(pq)

with minimum weight.

The algorithm therefore combines:

  • Graph traversal
  • Greedy selection
  • Priority queues

Dijkstra's Algorithm

Dijkstra solves a different problem.

Goal:

Find shortest paths from a source vertex.

The greedy rule is:

Select the unreached vertex with the smallest tentative distance.

At first glance this seems dangerous.

How do we know a shorter path will not appear later?

The answer depends on a critical assumption:

All edge weights are nonnegative.

Under this assumption, distances can only increase as paths grow.

Once the smallest tentative distance is selected, it becomes final.

Example

Distances:

Vertex Tentative Distance
A 0
B 5
C 8
D 12

The smallest unreached vertex is:

B

Any future path to B must pass through vertices with distance at least 5.

Therefore no shorter path can emerge later.

The greedy choice is safe.

Common Structure

Although Kruskal, Prim, and Dijkstra solve different problems, they share a common pattern.

Maintain Partial Solution

A forest, tree, or distance map.

Identify Safe Choice

Smallest edge or shortest distance.

Prove Safety

Using:

  • Cut property
  • Exchange argument
  • Monotonicity

Commit Permanently

The choice never needs reconsideration.

This permanence is what distinguishes greedy algorithms from dynamic programming.

Recognizing Graph Greedy Problems

Several signals suggest a greedy graph solution.

Local Edge Decisions

Optimality depends on choosing individual edges.

Monotonic Progress

The solution only grows.

Safe Edge Theorems

Some edges can be proven optimal independently.

No Need for Backtracking

Once selected, edges remain selected.

Matroid Structure

The problem resembles spanning tree construction or independent-set selection.

When Graph Greedy Fails

Many graph problems do not possess safe local choices.

Examples:

  • Traveling Salesman Problem
  • Longest Path Problem
  • General Steiner Tree
  • Most NP-hard graph optimizations

For these problems, locally attractive edges often lead to globally poor solutions.

The absence of a safe-edge theorem is usually a warning sign.

Comparing Graph Greedy Algorithms

Algorithm Goal Greedy Choice
Kruskal MST Smallest safe edge
Prim MST Cheapest crossing edge
Dijkstra Shortest paths Smallest tentative distance
Huffman Coding tree Smallest frequencies
Interval scheduling Maximum intervals Earliest finish

Different domains, same pattern.

Each algorithm repeatedly commits to a locally optimal choice that can be proven globally safe.

Takeaway

Graph greedy algorithms succeed when local graph decisions can be shown to belong to some optimal solution. The key tools are cut properties, exchange arguments, and monotonicity arguments. Kruskal, Prim, and Dijkstra demonstrate three variations of the same strategy: maintain a partial solution, identify a safe local choice, prove its safety, and commit permanently. Understanding these proofs is often more important than memorizing the algorithms themselves, because the proofs reveal when greedy reasoning is valid and when a graph problem requires a fundamentally different approach.