Prim's algorithm grows a tree from any root . For each vertex outside the current tree, its priority queue key is the cheapest single edge connecting it to the tree, not the total length of a root-to-vertex path:The indexed priority queue supports membership and locating a vertex's heap entry. After the first extraction, the chosen parent edge is a least-weight edge crossing the cut between the current tree and its complement. The minimum spanning tree cut property makes that edge safe: exchanging it for a crossing edge of a suitable minimum tree preserves minimality. Repeating this establishes a minimum tree. Connectivity ensures every nonroot vertex eventually has a parent; edge weights may be negative.
for v in V:
key[v] = infinity
parent[v] = NONE
key[r] = 0
Q = indexed_min_priority_queue(V, key)
while Q is not empty:
u = Q.extract_min()
for (v,weight) in adjacency[u]:
if Q.contains(v) and weight < key[v]:
parent[v] = u
key[v] = weight
Q.decrease_key(v, weight)
return {(parent[v],v) : v != r} Articles by others on the same topic
There are currently no matching articles.