Minimum Spanning Tree

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.
    for each vertex v in G.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.
    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)).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s