The post is based on <<Introduction to Algorithms>>, Third Edition

What is MST problem: how can we connect all n vertices in a graph G with n-1 edges with the smallest total weights?

**Kruskal algorithm**: consider each edge in the graph in non-decreasing order and check if the vertices connected by the edge belong to one tree; if not, add the edge to the result set and connect the two vertices.

MST-KRUSKAL(G,w):
for each vertex v in G.V:
MAKE-SET(v)
sort the edges of G.E into nondecreasing order by weight w
for each edge (u,v) in G.E, taken in nondecreasing order by weight:
if FIND-SET(u) != FIND-SET(v): //FIND-SET takes O(lg(V)) time
A = A + {(u,v)}
UNION(u,v) //merge the two trees that u and v belong to
return A

- Running time: O(Vlg(V)+Elg(V)). Since we assume that E>= V-1, thus O(VlgV+ElgV) = O(Elg(V))

**Prim algorithm: **Start from any vertex in G.V, and then expand the tree using the minimum weight edge.

MST-PRIM(G,w,r):
for each u in G.V:
u.key = infinity
u.previous = NIL
r.key = 0
Q = G.V
while Q is not empty:
u = EXTRACT-MIN(Q)
for each v in G.Adj[u]:
if v in Q and w(u,v) < v.key:
v.previous = u
v.key = w(u,v)

- Running time: depends on the implementation of priority queue Q
- Array: O(V^2); binary heap: O(Vlg(V)+Elg(V)); Fibonacci heap: O(E+ Vlg(V)).

### Like this:

Like Loading...