Prims Algorithm

A derivative of Kruskal’s Algorithm but the edges X are always connected to form a subtree and the cut is $X$ and $V-X$. Then, add the shortest edge that has one end in $X$ and the other one in $V-X$. We use a priority queue just like in Dijkstras Algorithm.

procedure prim(G, l)
Input: Undirected and connected graph G = (V, E); edge lengths ℓ
Output: An MST specified by prev array

for all u ∈ V:
    cost(u) = inf
    prev(u) = nil
Pick any u₀ ∈ V
cost(u₀) = 0
H = makequeue(V, cost)
while H is not empty:
    v = deletemin(H)
    for all edges {v, z} ∈ E:
        if z ∈ H and cost(z) > ℓ(v, z):
            cost(z) = ℓ(v, z)
            prev(z) = v
            decreasekey(H, z, cost(z))

This is essentially just Dijkstras. In each iteration, cost v records the shortest edge length from each vertex in $V-X$ to the closest vertex in $X$. The runtime here is $O(|v|+|E|\log |V|)$ which is the same as Kruskal’s.