prim

Prim’s Algorithm

In Prim’s algorithm, the set $A$ forms a single tree. The safe edge added to $A$ is always a lowest-weight edge connecting the tree to a vertex not in the tree.

• Example of a greedy algorithm, each edge added added contributes minimum to the weight of tree.
• Maintains a min-priority queue of all vertices not in the tree, based on key, i.e. the minimum weight edge connecting the vertex to the tree.

MST-PRIM(Q, w, r)
    for each vertex u in G.V
        u.key = Inf
        u.pi = NIL
    r.key = 0
    Q = {}
    for each vertex u in G.V
        INSERT(Q, u)
    while Q != {}
        u = EXTRACT-MIN(Q)  // add u to the tree
        for each vertex v in G.Adj[u]  // update keys of u's non-tree neighbors
            if v in Q and w(u, v) < v.key
                v.pi = u
                v.key = w(u, v)
                DECREASE-KEY(Q, v, w(u, v))

• $O(E\lg V)$ with binary heap
• $O(E+V\lg V)$ time with Fibonacci heap, so that INSERT and DECREASE-KEY takes $O(1)$ time.