Prims Algorithm: Difference between revisions
From Rice Wiki
No edit summary |
|||
| Line 1: | Line 1: | ||
{{Infobox Algorithm|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]|runtime=Heap: O(E log V) <br> Array: O(V^2)}} | {{Infobox Algorithm|class=[[Minimum_Spanning_Tree]] <br> [[Graph Algorithm]] <br> [[Greedy Algorithm]]|runtime=Heap: O(E log V) <br> Array: O(V^2)}} | ||
= Approach: Greedy = | = Approach: Greedy = | ||
See [[Minimum_Spanning_Tree]] | See [[Minimum_Spanning_Tree]] | ||
| Line 20: | Line 20: | ||
</pre> | </pre> | ||
= Analysis = | |||
Priority queue is slower than array when the graph is dense, so sometimes it's better to use Dijsktra's algorithm. | |||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
Revision as of 00:52, 8 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]
Analysis
Priority queue is slower than array when the graph is dense, so sometimes it's better to use Dijsktra's algorithm.
