Prims Algorithm

Prims Algorithm
Runtime	Heap: O(E log V) Array: O(V^2)
Class	Minimum_Spanning_Tree Graph Algorithm Greedy Algorithm

Approach: Greedy

See Minimum_Spanning_Tree

Implementation

for each u in V:
    key[u] = infinity   // cost array
    pi[u] = infinity    // from array
Q = new PriorityQueue(V)
key[root] = 0
while Q is not empty:
    u = extractMin(Q)
    # Reduce nodes
    for v in adj[u]:
        if v in Q and w[u,v] < key[v]:
            key[v] = w[u,v]

Analysis

Priority queue is slower than array when the graph is dense, so sometimes it's better to use Dijsktra's algorithm.

Proof: Greedy

Suboptimality

Given MST tree for the graph G

$OPT={\text{set of edges}}$

where the number of edges is $n-1$, the weight of edges is minimum, and the tree is spanning.

Consider $(x,y)$, where X is a leaf node.

Prove that $A=OPT-(x,y)$ is a MST for the subproblem $G-X$

By contradiction, assume that $A$ is not optimal. There must be $B$ such that

$w(B)<w(A)$

Adding the edge (x, y) back to both graphs, we have

$w(B+w(x,y))<w(A+w(x,y))=w(OPT)$

Therefore, OPT is not the optimal solution.

By contradiction, $A$ must be optimal.