Prims Algorithm: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
= Approach: Greedy = | |||
See [[Minimum_Spanning_Tree]] | |||
= Implementation = | = Implementation = | ||
Revision as of 01:49, 6 March 2024
Approach: Greedy
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]