Weighted Graph: Each edge is assigned a weight/cost $w(e)\in \R$

Spanning Tree: Connected, acyclic subset of edges

• Contains n-1 edges $|E| = |V| - 1$
• Adding an edge creates a cycle, removing an edge disconnects the graph.

Minimum Spanning Tree: A spanning tree with minimum total weight

• Input: Connected, undirected, weighted graph G

Prim’s Algorithm

Prim’s Algorithm: An algorithm for finding minimum spanning trees from a graph

1. Pick a root vertex r
2. Grow the tree one edge at a time
   1. In each iteration, pick the edge with minimum weight and connect it
   2. If an alternative edge with lower weight of an existing node is found, switch edges

Implementation PRIM(G, w: E → R, r ∈ V):

1. Initialize
   1. T = set() - Stores the edges in MST Make a queue (min-heap) Q
   2. For each vertex, π[v] = null, Q.add(v, pri[v] = ∞)
   3. Q.decreaseKey(r, pri[r] = 0)
2. While Q is not empty (n times)
   1. Connect a vertex with the minimum priority u = Q.extractMin() (log n) If π[u] ≠ null: T.add((π[u], u))
   2. Update priorities for neighbours (total m times) Loop through v ∈ u.adj:
      • If v ∈ Q and weight(u, v) < pri[v]: π[v] = u Q.decreaseKey(v, pri[v] = weight(u, v)) (log n)
3. Return T

Running Time: $\theta((n+m)\log n)$

• RT of Prim’s Algo on Fibonacci Heap: $\theta(m+n \log n)$
• DecreaseKey: To make decrease-key $\theta(\log n)$, track index[v] inside the heap so that no search is required, and keep index[v] updated in heap operations.

Disjoint Sets ADT

• Track a collection of non-empty and disjoint sets ⊂ universe U (There cannot be an element in multiple sets)
• MAKE-SET(x): Add a new set {x} (Assume x ∈ U and x ∉ any existing set)