Prims and Kruskal's Alogithms
Both Prim's algorithm and Kruskal's algorithm are greedy algorithms for finding the Minimum Spanning Tree. For Prim's algorithm, the graph has to be connected, but that is not true in the case of Kruskal's algorithm. In Prim's algorithm, the next edge in the MST shall be the cheapest edge in the current vertex
Use Prim's algorithm when you have a graph with lots of edges.
For a graph with V vertices E edges, Kruskal's algorithm runs in O(E log V) time and Prim's algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.
Prim's algorithm is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.
For Prim's algorithm, the graph has to be connected, but that is not true in the case of Kruskal's algorithm.
Use Prim's algorithm when you have a graph with lots of edges.
For a graph with V vertices E edges, Kruskal's algorithm runs in O(E log V) time and Prim's algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.
Prim's algorithm is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.
For Prim's algorithm, the graph has to be connected, but that is not true in the case of Kruskal's algorithm.
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment