Kruskal and Prim

This builds on Minimum Spanning Trees, which set up the problem and proved the cut property (a light edge crossing a respecting cut is safe) and cycle property (a heaviest edge on a cycle is droppable). Everything below rests on those two certificates. The running example is the same nine-town graph from that lesson, whose unique MST has total weight $38$ .

Kruskal's algorithm

$Kruskal$ 's strategy is global and edge-centric: consider the edges in order of increasing weight, and add each one unless it would form a cycle. The set $A$ is a forest (an acyclic graph) that gradually coalesces into a single tree once $G$ is fully connected.

Why is each added edge safe? It reduces directly to the cut property.

Each rejection is justified too: a rejected edge closes a cycle on which it is a maximum-weight edge (everything already accepted is no heavier), so by the cycle property some MST omits it.

The cycle test, are $u$ and $v$ already in the same tree?, reduces to the question $comp (u) = ? comp (v)$ : does adding $(u, v)$ keep the graph acyclic? This is what the disjoint-set (union-find) data structure answers efficiently.¹ It supports $Make-Set$ , $Find$ ( $comp (x)$ , which component is $x$ in?), and $Union$ (merge two components).

Algorithm 3:

\textsc{Kruskal}(G, c)

— grow a forest, cheapest safe edge first

1
$A \gets \emptyset$
2
foreach vertex $v \in V$ do
3
call $\textsc{Make-Set}(v)$
4
sort the edges of $E$ into nondecreasing order by weight $c$
5
foreach edge $(u, v) \in E$ in sorted order do
6
if $\textsc{Find}(u) \neq \textsc{Find}(v)$ then
stays acyclic
7
$A \gets A \cup \set{(u, v)}$
safe edge
8
call $\textsc{Union}(u, v)$
9
return $A$

A full trace, union-find state included

Running $Kruskal$ on the nine-town graph makes the accept/reject rhythm visible. The thirteen edges in nondecreasing order (ties broken alphabetically) are

1, 2, 2, 4, 6, 7, 7, 7, 8, 9, 10, 11, 14.

The table shows, for every edge scanned, the union-find test and the partition of $V$ into components after the step:

#	edge	$c_{e}$	same component?	action	partition afterwards
1	$h$ – $g$	$1$	no	accept	${a} {b} {c} {d} {e} {f} {g, h} {i}$
2	$c$ – $i$	$2$	no	accept	${a} {b} {c, i} {d} {e} {f} {g, h}$
3	$g$ – $f$	$2$	no	accept	${a} {b} {c, i} {d} {e} {f, g, h}$
4	$a$ – $b$	$4$	no	accept	${a, b} {c, i} {d} {e} {f, g, h}$
5	$i$ – $g$	$6$	no	accept	${a, b} {c, f, g, h, i} {d} {e}$
6	$b$ – $c$	$7$	no	accept	${a, b, c, f, g, h, i} {d} {e}$
7	$c$ – $d$	$7$	no	accept	${a, b, c, d, f, g, h, i} {e}$
8	$i$ – $h$	$7$	yes	reject	unchanged
9	$a$ – $h$	$8$	yes	reject	unchanged
10	$d$ – $e$	$9$	no	accept	${a, b, c, d, e, f, g, h, i}$
11	$e$ – $f$	$10$	yes	reject	unchanged
12	$b$ – $i$	$11$	yes	reject	unchanged
13	$d$ – $f$	$14$	yes	reject	unchanged

Eight accepts, total weight $38$ — the MST from the opening figure. Once the eighth edge lands (step 10) the forest is spanning and the loop could stop early; steps 11–13 can only reject. Four snapshots of the growing forest:

Kruskal's forest on the nine-town graph. Thick edges are accepted; dashed edges are rejected because both endpoints already share a component.

Making it fast: union by size

The simplest implementation keeps an array $comp [1 \dots n]$ where $comp [v]$ names $v$ 's current component. Then $Find$ is $O (1)$ , but a naive $Union$ that relabels one whole side costs $O (n)$ in the worst case. The fix is the classic union-by-size argument:

Alongside $comp [\cdot]$ , keep $members [c]$ , a linked list of the vertices currently in component $c$ , so we can enumerate a component cheaply.
On $Union (u, v)$ , relabel the smaller component: choose the side with $∣ comp_{u} ∣ \leq ∣ comp_{v} ∣$ and rewrite $comp [x]$ for the vertices $x$ in that smaller side.

Why this wins: whenever a vertex $x$ has its label $comp [x]$ rewritten, it sat in the smaller of the two merged components, so the component containing $x$ at least doubles in size. After $k$ relabellings of $x$ , its component holds at least $2^{k}$ vertices; since no component exceeds $n$ , $2^{k} \leq n$ , i.e. $k \leq log_{2} n$ . Summing over vertices, the total work spent updating $comp [\cdot]$ across all unions is

x \in V \sum # relabellings of x \leq n log_{2} n = O (n log n) .

The bound is loose in practice. In the trace above, the eight unions relabel smaller sides of sizes $1, 1, 1, 1, 2, 2, 1, 1$ : ten label rewrites total, nowhere near $9 log_{2} 9 \approx 29$ .

Running time. The pieces are: sorting, $O (m log m) = O (m log n)$ since $m \leq n^{2}$ implies $log m \leq 2 log n$ ; the $2 m$ $Find$ calls at $O (1)$ each; and $O (n log n)$ total union work. Sorting dominates:

T (n, m) = O (m log n) .

The pointer-based union-find (union by rank plus path compression) does all $m$ operations in $O (m α (n))$ , where $α$ is the inverse Ackermann function, at most $4$ for any input that fits in the physical universe. That refinement only matters when sorting is not the bottleneck: if the edges arrive pre-sorted, or the weights are small integers that a counting or radix sort handles in $O (m)$ , Kruskal's total drops to $O (m α (n))$ , effectively linear.

kruskal.pypython

from collections.abc import Hashable
from typing import TypeVar

from graph import Edge, Graph
from union_find import UnionFind

Label = TypeVar("Label", bound=Hashable)

def kruskal(graph: Graph[Label]) -> list[Edge[Label]]:
  """
    A minimum spanning tree of a connected, undirected `graph`,\n
    returned as the list of its tree edges (n - 1 of them).\n
    On a disconnected graph this returns a minimum spanning forest.\n
  """
  components: UnionFind[Label] = UnionFind(graph.labels)
  tree_edges: list[Edge[Label]] = []

  # cheapest edge first; ties broken by endpoint labels for determinism.
  sorted_edges: list[Edge[Label]] = sorted(
    graph.edges(),
    key=lambda edge: edge.weight,
  )
  for edge in sorted_edges:
    source_label: Label = edge.source.label
    target_label: Label = edge.target.label

    # union returns False when both ends already share a tree (a cycle).
    if components.union(source_label, target_label):
      tree_edges.append(edge)
  return tree_edges

def mst_weight(tree_edges: list[Edge[Label]]) -> float:
  """
    Total weight of a collection of tree edges.\n
  """
  return sum(edge.weight for edge in tree_edges)

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

union_find.pypython

from collections.abc import Hashable, Iterable
from typing import Generic, TypeVar, cast


Element = TypeVar("Element", bound=Hashable)


class DisjointSetNode(Generic[Element]):
  """
    One element's node: its value, its parent link, and its rank.\n
    A node is its own parent exactly when it is the root of its set.\n
  """

  def __init__(self, value: Element) -> None:
    self.value: Element = value
    self.parent: DisjointSetNode[Element] = self
    self.rank: int = 0

  def __repr__(self) -> str:
    return f"DisjointSetNode({self.value!r})"


class UnionFind(Generic[Element]):
  """
    A collection of disjoint sets over hashable elements.\n
  """

  def __init__(self, elements: int | Iterable[Element] = 0) -> None:
    """
      Seed the structure. An int `n` creates singletons `0..n-1`;\n
      an iterable creates one singleton node per member.\n
    """
    # a seed count `n` means the elements are 0..n-1 (ints standing in for
    # Element); cast keeps the type checker happy about that substitution.
    members: Iterable[Element] = (
      cast("Iterable[Element]", range(elements))
      if isinstance(elements, int)
      else elements
    )
    # one singleton node per seeded member.
    self._nodes: dict[Element, DisjointSetNode[Element]] = {
      value: DisjointSetNode(value) for value in members
    }
    self.count: int = len(self._nodes)

  def add(self, value: Element) -> None:
    """
      Add `value` as a new singleton set if it is absent.\n
    """
    if value not in self._nodes:
      self._nodes[value] = DisjointSetNode(value)
      self.count += 1

  def _find_root(self, value: Element) -> DisjointSetNode[Element]:
    """
      The root node of `value`'s set, compressing the path on the way.\n
    """
    # first pass: climb parent links to the root of the set.
    node = self._nodes[value]
    root = node
    while root.parent is not root:
      root = root.parent

    # second pass: point every node on the path straight at the root.
    while node.parent is not root:
      node.parent, node = root, node.parent

    return root

  def find(self, value: Element) -> Element:
    """
      The representative value of `value`'s set.\n
    """
    return self._find_root(value).value

  def union(self, first: Element, second: Element) -> bool:
    """
      Merge the sets containing `first` and `second`.\n
      Returns False if they already shared a set.\n
    """
    # already in the same set: nothing to merge.
    first_root = self._find_root(first)
    second_root = self._find_root(second)
    if first_root is second_root:
      return False

    # hang the shorter tree under the taller one.
    if first_root.rank < second_root.rank:
      first_root, second_root = second_root, first_root
    second_root.parent = first_root

    # equal ranks: the merged tree grows one level taller.
    if first_root.rank == second_root.rank:
      first_root.rank += 1

    self.count -= 1
    return True

  def connected(self, first: Element, second: Element) -> bool:
    """
      Whether `first` and `second` belong to the same set.\n
    """
    return self._find_root(first) is self._find_root(second)

Prim's algorithm

$Prim$ 's strategy is local and vertex-centric: grow a single tree outward from an arbitrary root, repeatedly attaching the cheapest edge that links a tree vertex to a non-tree vertex. Here the set $A$ is always one connected tree.²

Safety is again the cut property.

This is exactly $Dijkstra$ with the relaxation rule changed. Where Dijkstra keys a frontier vertex by $d [x] + c_{xv}$ (distance from the source), Prim keys it by $c_{xv}$ alone (cost to attach to the finished set). Prim keeps every non-tree vertex $v$ in a min-priority queue keyed by $key [v]$ , maintaining the invariant

\forall v \in Q : key [v] = x \in / Q min c_{xv} (the cheapest way to connect v to a finished vertex).

Extracting the minimum yields the next vertex to absorb; absorbing it may make its neighbors cheaper to reach, so we relax their keys with $Decrease-Key$ .

Algorithm 4:

\textsc{Prim}(G, c, s)

— grow one tree from an arbitrary start

s

1
foreach vertex $u \in V$ do
2
$\text{key}[u] \gets \infty$
3
$\pi[u] \gets \text{nil}$
4
$\text{key}[s] \gets 0$
start tree at $s$
5
$Q \gets V$
min-PQ keyed by $\text{key}$
6
$E' \gets \emptyset$
7
while $Q \neq \emptyset$ do
8
$u \gets \textsc{Extract-Min}(Q)$
cheapest to attach
9
if $\pi[u] \neq \text{nil}$ then
10
$E' \gets E' \cup \set{(\pi[u], u)}$
commit safe edge
11
foreach $v$ adjacent to $u$ with $v \in Q$ do
12
if $c_{uv} < \text{key}[v]$ then
13
$\pi[v] \gets u$
$v$ 's best link to tree
14
$\text{key}[v] \gets c_{uv}$
Decrease-Key
15
return $E'$

A single step in isolation: the tree $S = {a, b, c}$ has been grown from root $a$ ; every frontier vertex carries a key equal to its cheapest edge into $S$ . The cut $(S, V ∖ S)$ respects the tree, and $Extract-Min$ returns the endpoint of the lightest crossing edge — here $c$ – $i$ at weight $2$ — which the cut property certifies as safe:

A Prim snapshot: the grown tree

S

(shaded, dashed box) and the frontier;

Extract-Min

pulls the lightest crossing edge (

c

–

i

, weight

2

A full trace, queue state included

Now the whole run, from root $a$ on the nine-town graph. Each row lists the vertex extracted, the tree edge committed, the $Decrease-Key$ calls its absorption triggers, and the queue contents afterwards (vertices with key $\infty$ omitted):

step	extracted	edge added	key updates ( $π$ in parentheses)	queue after: $v$ : key
1	$a$ (key $0$ )	—	$b \leftarrow 4$ ( $a$ ), $h \leftarrow 8$ ( $a$ )	$b : 4, h : 8$
2	$b$ ( $4$ )	$a$ – $b$	$c \leftarrow 7$ ( $b$ ), $i \leftarrow 11$ ( $b$ )	$c : 7, h : 8, i : 11$
3	$c$ ( $7$ )	$b$ – $c$	$i \leftarrow 2$ ( $c$ ), $d \leftarrow 7$ ( $c$ )	$i : 2, d : 7, h : 8$
4	$i$ ( $2$ )	$c$ – $i$	$g \leftarrow 6$ ( $i$ ), $h \leftarrow 7$ ( $i$ )	$g : 6, d : 7, h : 7$
5	$g$ ( $6$ )	$i$ – $g$	$h \leftarrow 1$ ( $g$ ), $f \leftarrow 2$ ( $g$ )	$h : 1, f : 2, d : 7$
6	$h$ ( $1$ )	$g$ – $h$	—	$f : 2, d : 7$
7	$f$ ( $2$ )	$g$ – $f$	$e \leftarrow 10$ ( $f$ )	$d : 7, e : 10$
8	$d$ ( $7$ )	$c$ – $d$	$e \leftarrow 9$ ( $d$ )	$e : 9$
9	$e$ ( $9$ )	$d$ – $e$	—	empty

Reading the table against the invariant: at every step the extracted key is the weight of the lightest edge crossing the cut around the current tree, and the committed edge $(π [u], u)$ is that light edge. $h$ 's key falls $8 \to 7 \to 1$ as the tree grows toward it, and $i$ 's from $11$ to $2$ the moment $c$ joins; a vertex's key only ever decreases. The same eight edges as Kruskal arrive in a different order — Kruskal took $h$ – $g$ first, Prim last but one — because the two algorithms apply the cut property to different cuts. Three snapshots of the growing tree, with each frontier vertex's cheapest attachment drawn dashed:

Prim from root

a

: tree vertices shaded, and each frontier vertex's best attachment (its key) dashed. Panels show steps 1, 4, and 7 of the trace.

Running time. Prim performs $n$ $Extract-Min$ operations and up to $m$ $Decrease-Key$ operations, so in general $T (n, m) = O (n (T_{ins} + T_{ext}) + m T_{dec})$ . With a binary heap all three operations cost $O (log n)$ , giving $O (m log n)$ , the same as Kruskal. With a Fibonacci heap, $Decrease-Key$ drops to $O (1)$ amortized while $Extract-Min$ stays $O (log n)$ , improving the total to

T (n, m) = O (m + n log n) .

When the graph is dense, $m = Ω (n log n)$ , this is $O (m)$ , that is, linear, and asymptotically the best known. On very dense graphs there is an even simpler route to the same bound: skip the heap, keep $key [\cdot]$ as a plain array, and find each minimum by scanning it. That is $n$ scans at $O (n)$ plus $O (1)$ per key update, for $O (n^{2} + m) = O (n^{2})$ total — on a complete graph ( $m = Θ (n^{2})$ ) this plain-array Prim is linear in the input size and beats the heap version's $O (n^{2} log n)$ .

prim.pypython

import heapq
from collections.abc import Hashable
from typing import Optional, TypeVar

from graph import Edge, Graph

Label = TypeVar("Label", bound=Hashable)

def prim(
  graph: Graph[Label],
  start_label: Optional[Label] = None,
) -> list[Edge[Label]]:
  """
    A minimum spanning tree of a connected, undirected `graph`, returned\n
    as the list of its tree edges. `start_label` chooses the root; it\n
    defaults to the first vertex. The result is identical in weight for\n
    any valid start. On a disconnected graph only the start's component\n
    is spanned.\n
  """
  if len(graph) == 0:
    return []

  root_label: Label = start_label if start_label is not None else graph.labels[0]
  in_tree: set[Label] = set()
  tree_edges: list[Edge[Label]] = []

  # heap entries are (weight, attaching_edge_or_None) for a frontier vertex.
  # the root enters with no attaching edge; we never commit a None edge.
  frontier: list[tuple[float, int, Optional[Edge[Label]], Label]] = []
  counter: int = 0
  heapq.heappush(frontier, (0.0, counter, None, root_label))

  while frontier:
    # pull the lightest crossing edge; skip if its endpoint is already in.
    _, _, attaching_edge, vertex_label = heapq.heappop(frontier)
    if vertex_label in in_tree:
      continue

    # absorb the vertex and commit the edge that brought it in.
    in_tree.add(vertex_label)
    if attaching_edge is not None:
      tree_edges.append(attaching_edge)

    # offer each not-yet-absorbed neighbor its edge into the tree.
    for edge in graph.vertex(vertex_label).outgoing:
      neighbor_label: Label = edge.target.label
      if neighbor_label not in in_tree:
        counter += 1
        heapq.heappush(
          frontier,
          (edge.weight, counter, edge, neighbor_label),
        )
  return tree_edges

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

Edge cases and pitfalls

Equal weights. Nothing in the cut-property proof requires distinct weights (it only uses $c_{e} \leq c_{g}$ ), so Kruskal and Prim are correct as stated under ties; the MST just may not be unique, and different tie-breaks yield different, equally cheap trees. The one algorithm that needs care is Borůvka's, where an inconsistent tie-break can create a cycle within a single round — hence the fixed total order in the remark above. If you need the MST to be well defined (say, for hashing or comparison), perturb ties by edge index: order by $(c_{e}, index (e))$ lexicographically.

Negative weights are harmless. Every spanning tree has exactly $n - 1$ edges, so adding a constant $K$ to every weight adds exactly $(n - 1) K$ to every spanning tree's cost and preserves their relative order. MST algorithms only ever compare weights. Contrast Dijkstra, where shifting weights breaks correctness precisely because paths have different edge counts.

An MST is not a shortest-path tree. The MST minimizes one global sum; it guarantees nothing about the path between any particular pair. In the nine-town graph the MST joins $a$ to $h$ through $a$ – $b$ – $c$ – $i$ – $g$ – $h$ at cost $4 + 7 + 2 + 6 + 1 = 20$ , while the direct edge $a$ – $h$ costs $8$ . Building the MST and then reading distances off it is a classic error.

What an MST does guarantee about paths. It minimizes the bottleneck:

This is why MSTs answer minimax questions: the path between $u$ and $v$ inside an MST minimizes the maximum edge weight over all $u$ – $v$ paths. Two of the practice problems (Path With Minimum Effort, Swim in Rising Water) amount to this bottleneck property in disguise.

Heaviest edge, again. The cycle property removes the heaviest edge on each cycle, not the heaviest edge of the graph; a heavy bridge survives every MST (the figure in the cycle-property section). Symmetrically, a maximum spanning tree needs no new theory: negate all weights, or flip the comparisons.

Disconnected input. If $G$ is not connected no spanning tree exists. Kruskal degrades gracefully: it returns the minimum spanning forest (an MST of each component) with no code change, since it never needed connectivity. Prim must be restarted once per component, as its single tree can never cross between them.

Which to use?

Throughout, $n = ∣ V ∣$ and $m = ∣ E ∣$ .

	Borůvka	Kruskal	Prim
Grows	every component at once	a forest, globally	a single tree, from a root
Core structure	component scan / union-find	union-find (union by size)	priority queue
Headline time	$O (m log n)$	$O (m log n)$	$O (m log n)$
Best variant	parallel rounds	$O (m α (n))$ work after sort	$O (m + n log n)$ (Fib. heap)
Best when	parallel / distributed	edges already sorted; sparse	dense; adjacency-rich data

The tie-breakers in practice: Kruskal wins on sparse graphs and whenever the edges come pre-sorted or sort in linear time (integer weights), since what remains is near-linear union-find work; it also handles edge lists with no adjacency structure and disconnected inputs directly. Prim wins on dense graphs, especially with the plain-array variant at $O (n^{2})$ , and on implicitly dense inputs like connect these points in the plane where materializing and sorting all $Θ (n^{2})$ candidate edges just to feed Kruskal is the expensive part. Borůvka wins when the work must be split across machines or threads, and its rounds compose with the other two: run a few Borůvka rounds to shrink the graph, then finish with Prim or Kruskal — the fastest practical schemes are hybrids of exactly this shape.

All three are correct for the same reason, the cut property, and all three are greedy algorithms whose greediness is provably optimal — rare for greedy strategies.

What MSTs are used for

Beyond network design, the MST is a building block in data analysis and approximation.

Single-linkage clustering. Run Kruskal but stop early, after $n - k$ edges: the $k$ remaining components are the clusters that single-linkage agglomerative clustering would form.³ Merging the two closest clusters is precisely accepting the next-cheapest Kruskal edge, so the whole MST is the clustering dendrogram, and cutting it at a chosen height gives any number of clusters for free. Deleting the $k - 1$ heaviest MST edges partitions the points into the $k$ groups that maximize the smallest inter-cluster gap — the cut and bottleneck properties at work on real data.

Approximating hard tours. The metric travelling-salesman problem is NP-hard, but the MST gives a fast $2$ -approximation: build the MST, walk it in a depth-first order (a full traversal crosses each edge twice, costing $2 \cdot MST$ ), and shortcut past repeats. Since the optimal tour minus one edge is a spanning tree, $MST \leq OPT$ , so the shortcut tour costs at most $2 OPT$ . Christofides' refinement adds a minimum matching on the odd-degree vertices to reach a $1.5$ -approximation — still the classic guarantee for metric TSP, and the MST is its foundation.

MST as a TSP approximation. Left: the MST of five cities. Right: a DFS walk of the MST (each edge twice) shortcut past repeated visits yields a tour of cost at most twice the MST, hence at most twice the optimal tour.

The list runs long: MSTs underlie network design and broadcast trees, image segmentation (Felzenszwalb-Huttenlocher runs single-linkage on a pixel grid), the taut-string structure of point clouds, and the bottleneck routing problems from the practice set. Whenever a problem asks to connect everything cheaply, to find the widest-gap partition, or to approximate a metric optimization, the MST is the standard starting point.

Takeaways

A minimum spanning tree connects all $n$ vertices of a connected weighted graph with exactly $n - 1$ edges of least total weight; tree means connected and acyclic, no root.
The generic method adds one safe edge at a time, maintaining the invariant that the growing edge set sits inside some MST; after $n - 1$ additions the invariant forces equality.
The cut property is the inclusion certificate: a light edge crossing a cut that respects the current edge set is always safe. The exchange argument must swap out the edge $g$ on the cycle created by adding $e$ ; swapping an arbitrary crossing edge is a tempting mistake.
The cycle property is the exclusion certificate: a heaviest edge on any cycle can be dropped, and a strictly heaviest one is in no MST. It applies only to cycle edges; bridges are in every spanning tree. Distinct weights make the MST unique.
$Bor \overset{u}{˚} vka$ adds every component's cheapest exit edge each round; the component count at least halves, giving $O (log n)$ rounds and $O (m log n)$ total, with naturally parallel rounds.
$Kruskal$ adds edges cheapest-first, skipping cycle-forming ones, using union-find; sorting dominates at $O (m log n)$ , and union by size keeps the relabelling work to $O (n log n)$ because each vertex's component can double only $log_{2} n$ times.
$Prim$ is $Dijkstra$ rekeyed by attachment cost: grow one tree from a start vertex, attaching the lightest crossing edge via a priority queue; $O (m log n)$ with a binary heap, $O (m + n log n)$ with a Fibonacci heap, $O (n^{2})$ with a plain array — linear on dense graphs either way.
MSTs tolerate negative weights and ties, minimize the bottleneck edge on every path, and are not shortest-path trees.

CLRS, Ch. 21 — Data Structures for Disjoint Sets — union by size/rank and path compression, with the $O (m α (n))$ bound. ↩
Skiena, §6 — Weighted Graph Algorithms — Prim's algorithm growing one tree via a priority queue. ↩
Skiena, §6 — Weighted Graph Algorithms — single-linkage clustering as the minimum spanning tree cut at a chosen number of components. ↩

Kruskal's algorithm

A full trace, union-find state included

Making it fast: union by size

Prim's algorithm

A full trace, queue state included

Edge cases and pitfalls

Which to use?

What MSTs are used for

Takeaways

Footnotes