Skip to content

Latest commit

 

History

History

Prim's & Kruskal's Algorithm

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

Prim's and Kruskal's Algorithm are both very famous greedy paradigm following algorithms, while both of the algorithms are aimed to find the Minimum Spanning Tree from a given graph but they surely differ in the way they achieve this feat.

Prim's Elaboration

Prim's Algorithm starts with choosing any vertex and then finding the minimum cost edge attached to that chosen vertex. Now we have a tree with 2 vertices and hence now we can select minimum cost edge from any of these 2 vertices and hence making our tree with 3 vertices. This process is followed until every vertex is included in the Minimum spanning tree. Well now after knowing this it's a no brainier to deuced that Prim's algorithm just can't work with disconnected graphs but well that's why we have Kruskal's Algorithm right after we discuss Prim's actual Algorithm.

Algorithm

Here we have assumed that the array starts at 1st index

Complexity Analysis

Time Complexity

Space Complexity

Kruskal's Elaboration

Algorithm

Here we have assumed that the array starts at 1st index

Complexity Analysis

Time Complexity

Space Complexity