Haoran's Blog

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?

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

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