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)).