[Algorithm] Prim (feat. compare to Kruskal)

 

When to use

get MST of undirected & weighted Graph

 

Idea

maintain two sets of vertices (1: MST, 2: not visited)

find cut vertex minimum weight in each loop

until all vertices be included in MST

📝 cut vertex: connect vertex which connects two disjoint subsets

 

 

Algorithm

(1) Create key-value table (vertex - weight) , empty MST Set

(2) initialize first value of key as '0' to visit first, remain key as 'MAX'

(3) while MST Set includes all vertices , iterates next

     a. pick the minimum cut vertex

     b. include it to MST

     c. update key-value table (adjacent vertex of (b))

          value of b is less than old value? -> update

          equal or more? -> nothing to do

---

Prim vs Kruskal

Prim	Kruskal
can start any vertex	only can start minimum edge
run faster in dense graphs (a lot of edges) ∵ In loop, this cacluates on weight of each vertex	run faster in sparse graphs (a few edges) ∵ at first, sort all edges
it works only on connected graph ∵ in loop, find cut vertex which connects disjoint set	it works on disconnected components too
Greedy , generate MST

 

Problem Solving Example

[GeeksForGeeks] Prim

 

 

---

Reference

Prim’s Minimum Spanning Tree (MST) | Greedy Algo-5 - GeeksforGeeks