CITS2200 - Lecture 22

← Back to Home

CITS2200 - Lecture 21
Minimum Spanning Trees - Slides

Minimum Spanning Trees

• Minimum spanning trees (MST) is the cheapest method (minimum edge weight) to connect all vertices with no cycles
  • There can be multiple valid MSTs when edge weights are equal
• Edge weight is a value assigned to an edge
  • It could represent cost, distance, time, etc.

---

Key Properties of MSTs

• Cycle property:
  • Adding an edge e into the MST creates a cycle C
  • For every other edge (f) in that cycle:
    • weight(f) ≤ weight(e)
  • Therefore, MST edges are never the heaviest in any cycle
• Partition property:
  • Split all vertices into two groups U and V
  • The minimum-weight edge across partition must be in the MST

---

Building an MST

There are two algorithms you can use to build an MST:

• Prim-Jarník’s algorithm → grows MST one vertex at a time
• Kruskal’s algorithm → sorts all edges by weight, then adds one-by-one

Prim-Jarník’s Algorithm

1. Choose a starting vertex (e.g. vertex A)

2. Record the edge weight to every connected vertex in a min edge index

3. Expand along minimum edge weight to new vertex

   • e.g. if vertex A is connected to B, C & D with edge weights 7, 5 & 9, add A→C (w=5) to MST and move to vertex C

4. Repeat step 2, if edge weight to a vertex is smaller than recorded in our min edge index, update connection in index

   • e.g. if index initially records A→B (w=7), but we find C→B (w=5) then update index for vertex B

5. Repeat step 3 and 4 for all vertices until there are no more changes to the min edge index for unexpanded vertices

   

6. Use the smallest edges from our index to connect the missing vertices

   • e.g. if there are no more updates to the min index for vertex B, our min edge would be between C & B with w = 5

Kruskal’s Algorithm

1. Sort edges by weight
2. We now define each vertex as being in its own cluster
3. Now going along our sorted list, merge vertices into larger clusters
   • If you end up with an edge inside of a cluster, skip it
     • This prevents creating a cycle
   • Add your edges between merged clusters into your MST
4. Repeat until all vertices are in the same cluster

Prim vs Kruskal

Prim-Jarník $-$ grows from single source vertex

• Uses a priority queue of vertices
• Better for dense graphs (many edges)
• Running time $O(m\log n)$

Kruskal $-$ merges separate clusters

• Uses a priority queue of edges + Union-Find ADT
• Better for sparse graphs (few edges)
• Running time $O((n+m)\log n)$:
  • Priority queue operation $-$ $O(m\log n)$
  • Union-Find operations $-$ $O(n\log n)$

---

Union-Find

• Union-Find is a structure that tracks elements split into distinct groups
  • Used by Kruskal algorithm

Three main operations:

• makeSet(u) → create new cluster with vertex u at start
• find(u) → find which cluster u is in
  • Takes $O(1)$ time
• union(A, B) → merge clusters A and B
  • Moves smaller set into larger one
  • Amortised cost of $O(\log n)$

List-based Partition:

• Each set is stored in sequence
• Each element has a reference back to set

---

CITS2200 - Lecture 23