Prims Algorithm

Prims Algorithm
Runtime	Heap: O(E log V) Array: O(V^2)
Class	Minimum_Spanning_Tree Graph Algorithm Greedy Algorithm

<aside class="portable-infobox noexcerpt pi-background pi-theme-default pi-layout-stacked">

Prims Algorithm

</aside>

Approach: Greedy

See Minimum_Spanning_Tree

Implementation

for each u in V:
    key[u] = infinity   // cost array
    pi[u] = infinity    // from array
Q = new PriorityQueue(V)
key[root] = 0
while Q is not empty:
    u = extractMin(Q)
    # Reduce nodes
    for v in adj[u]:
        if v in Q and w[u,v] < key[v]:
            key[v] = w[u,v]