Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Minimum spanning trees

Minimum spanning trees (MSTs) choose a set of edges of minimum total weight that connects all vertices; engineers use MSTs for wiring, network design, clustering and routing cost optimization.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Minimum spanning trees are used by engineers to design low-cost networks (telecom, power, water piping) and to form efficient backbones for routing and clustering. An MST gives a cheapest way to connect all nodes when adding extra links is costly or when a tree structure is required.

Key ideas

Start with definitions from first principles.

  • Graph: A pair G = (V, E) where V is a set of vertices (nodes) and E is a set of edges (unordered pairs of vertices for undirected graphs). We assume undirected graphs in this topic.
  • Edge weight: A function w: E → R that assigns a real weight (cost, length) to each edge. We write w(e) for the weight of edge e. Weights may be negative; MST algorithms (Kruskal, Prim) and the cut/cycle properties remain valid for any real weights.
  • Connected graph: A graph where there is a path between every pair of vertices.
  • Tree: A connected graph with no cycles (a cycle is a closed path that starts and ends at the same vertex with distinct edges and intermediate vertices).
  • Spanning tree: A tree that includes every vertex of G. It has |V| − 1 edges when the graph is connected. If G is disconnected, no spanning tree exists; Kruskal's algorithm (and Prim on each component) yields a minimum spanning forest (MSF) over the components.
  • Forest: A graph with no cycles (a collection of trees).
  • Cut: A partition of V into two nonempty disjoint sets (S, V\S). An edge crosses the cut if it has one endpoint in S and the other in V\S.
  • Minimum spanning tree (MST): A spanning tree T of a connected, weighted graph G such that the total weight w(T) = sum_{e in T} w(e) is minimum among all spanning trees of G.

Important properties and theorems (state them exactly as used in exam answers):

Cut and cycle properties (used to prove algorithm correctness):

  • Cut property (exact statement): Let (S, V\S) be any partition of V (a cut). Let e be an edge of minimum weight among edges that have one endpoint in S and the other in V\S (a lightest crossing edge). Then there exists an MST that contains e. Assumption: edge weights are real numbers (they may be negative); if multiple edges tie for minimum weight across a cut, at least one of them is in some MST.

Proof (standard exchange argument, step-by-step to give in exams):

  1. Let e = (u,v) be a lightest edge crossing cut (S, V\S). Let T be any MST. If T contains e, done.
  2. If T does not contain e, adding e to T creates a cycle C (because T is a tree). This cycle must have at least one other edge f that also crosses the same cut (because e crosses the cut once; cycle must return to the other side).
  3. Since e is a lightest crossing edge, w(e) ≤ w(f). Remove f from T ∪ {e}. The result is a spanning tree T' with w(T') ≤ w(T). Because T was minimum, w(T') = w(T) and T' is an MST that contains e.
  • Cycle property (exact statement): For any cycle C in G, let f be an edge of maximum weight on C. Then there exists an MST that does not contain f. If weights are distinct, then f is not in any MST.

Proof (standard):

  1. Suppose an MST T contains f. Removing f from T disconnects T into two components. Since f was part of a cycle C, there is some other edge e in C that reconnects the two components.
  2. Since f is a heaviest on the cycle, w(e) ≤ w(f). Replace f by e in T to get a tree with weight no more than T.
  3. So some MST exists without f; if weights distinct then strict inequality holds and f cannot be in any MST.

Algorithms (exact pseudocode or syntax to remember):

  • Kruskal's algorithm (sort edges and use union-find):

    1. Sort all edges in nondecreasing order of weight.
    2. Initialize forest F with each vertex as a separate component (use union-find).
    3. For each edge e in sorted order: if endpoints of e are in different components, add e to F and union their components.
    4. Stop when F has |V| − 1 edges.
  • Prim's algorithm (grow a single tree using a priority queue):

    1. Start from any vertex r. Mark it included.
    2. Maintain a min-priority queue of edges with one endpoint in the tree and the other outside; key = weight.
    3. Repeatedly extract the minimum-weight edge that connects the tree to a new vertex, add that vertex and edge to the tree, and insert its incident edges to the queue.
    4. Stop when all vertices are included.

Correctness outline for Kruskal and Prim: both follow from repeated application of the cut property — each chosen edge is a lightest crossing edge for some cut separating chosen components from the rest.

Complexity (give standard results used in exams):

  • Kruskal: sorting edges O(E log E) plus union-find operations (amortized near O(α(V)) per operation), so O(E log E) which is O(E log V) since E ≤ V^2.
  • Prim with binary heap: O(E log V). With Fibonacci heap: O(E + V log V). These bounds assume a vertex-keyed priority queue with decrease-key; if you push all crossing edges (allowing duplicates), the time is O(E log E) = O(E log V).

When MST is unique: If all edge weights are distinct, the MST is unique. (Give exchange / cut argument: distinctness makes inequalities strict.)

Diagrams to draw in answers: For examples, draw vertices as labelled points (A, B, C, …). Draw each edge as a straight line connecting its endpoints and write the weight beside the edge. For Kruskal trace, draw the same graph and cross out edges that would create cycles; draw chosen edges in bold or a different color.

Formulas

w(T) = Σ_{e ∈ T} w(e) — w(T) is total weight of tree T; w(e) is weight (cost) of edge e; units: weight units (unitless or given cost units). Applies to any set of edges T.

|E(T)| = |V| - 1 — number of edges in any spanning tree T of a connected graph; |V| is number of vertices; unitless; applies when graph connected.

time(Kruskal) = O(E log E) — E is number of edges, unit: steps; applies when using comparison sort and union-find.

time(Prim, binary heap) = O(E log V) — V is number of vertices.

Pseudocode syntax to remember (short forms): make-set(v), find(v), union(u,v) — union-find operations for Kruskal. priority-queue.insert(v, key), decrease-key(v, newKey), extract-min() — for Prim (vertex-key version achieves O(E log V)).

Worked examples

Example 1 — Kruskal step-by-step (university exam standard): Graph: vertices A,B,C,D,E. Edges and weights: A-B:1, B-C:2, A-C:3, B-D:4, C-D:5, C-E:6, D-E:7, A-E:8. Step 1 (sort edges): (A-B,1), (B-C,2), (A-C,3), (B-D,4), (C-D,5), (C-E,6), (D-E,7), (A-E,8). Step 2 (initialize components): {A},{B},{C},{D},{E}. Step 3 (process edges):

  • Take A-B (1): different components → add. Components {A,B},{C},{D},{E}.
  • Take B-C (2): different components → add. Components {A,B,C},{D},{E}.
  • Take A-C (3): endpoints already in same component → skip (would form cycle).
  • Take B-D (4): different → add. Components {A,B,C,D},{E}.
  • Take C-D (5): same component → skip.
  • Take C-E (6): different → add. Components {A,B,C,D,E} now connected. Stop (4 edges = |V|-1). MST edges: A-B(1), B-C(2), B-D(4), C-E(6). Total weight: w(T) = 1 + 2 + 4 + 6 = 13 — final answer: 13 weight units.

Example 2 — Prim trace (same graph, start at A): Start tree {A}. Candidate edges: A-B(1), A-C(3), A-E(8).

  • Choose A-B(1). Tree {A,B}. Candidate edges now: A-C(3), B-C(2), B-D(4), A-E(8).
  • Choose B-C(2). Tree {A,B,C}. Candidate edges: B-D(4), C-D(5), C-E(6), A-E(8).
  • Choose B-D(4). Tree {A,B,C,D}. Candidate edges: C-E(6), D-E(7), C-D(5) (but C-D connects inside) → choose C-E(6). Tree now {A,B,C,D,E}. Chosen edges: same as Kruskal. Total weight 13.

If asked to draw: place A at top-left, B top-right, C center, D bottom-right, E bottom-left. Label weights on edges as above. Mark chosen edges.

Common mistakes

  • In Prim, inserting all edges without checking endpoints causes duplicates; always consider only edges crossing cut (tree vs outside). Prefer a vertex-keyed priority queue with decrease-key to avoid duplicates and achieve the standard O(E log V) bound.
  • Confusing the cut and cycle properties or applying them with incorrect assumptions (e.g., assuming uniqueness when weights are not distinct).
  • Arithmetic errors in adding weights; always carry units and re-check sums.

For your exam

Typical question types and what full-marks answers need:

  • Definitions: define spanning tree, MST, cut and cycle property. Include exact statements.
  • Short proofs: prove the cut property or cycle property. Give the exchange argument step-by-step.
  • Algorithm description: write Kruskal or Prim pseudocode, explain data structures (union-find or priority queue), and state time complexity with justification.
  • Trace problem: run Kruskal or Prim on a small labelled graph. Show sorting (for Kruskal), show components and chosen/skipped edges; or show priority queue operations for Prim.
  • Numerical: compute MST weight with units; show intermediate sums and final answer.
  • Implementation: write code or algorithmic steps. Mention union-find operations with path compression for efficiency.

Full-marks answers must: include clear diagrams where required, label every edge and weight, show each algorithm step (which edge considered, why accepted or rejected), show final tree and total weight, and state complexity.

Quick check

  1. State the cut property in one sentence.
  2. If all edge weights are distinct, what can you say about the MST? One short reason.
  3. Kruskal uses which main data structure to detect cycles quickly? Answers: 1. The lightest edge crossing any cut belongs to some MST. 2. The MST is unique; distinct weights make exchange inequalities strict. 3. Union-find (disjoint-set) data structure.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?