Hi,
What are the differences between the primes algorithm and Kruskal's algorithm to find the minimum spanning tree of a graph?
Primes algorithm and Krushkals algorithm
Let me correct you Its Prims not primes.
Prims and Kruskals algorithm for finding the minimum spanning trees are quite different in their behavior.
Prims Algo:
Starts from a vertex and looks for the minimum cost edge from the vertex to any other vertex provided it does not form a loop. It keeps visiting vertices until all vertices are visited. The result is a minimum spanning tree.
Kruskal’s algo:
Selects edges one by one with minimum cost provided no loops are formed until all the vertices have been visited on either side of any edge. The result is a minimum spanning tree.
Both are quite heuristic approaches which do not confirm an optimal solution. However a satisfactory solution is obtained.
Thanks.
Primes algorithm and Krushkals algorithm
Prim’s algorithm, in computer science, is an algorithm [also termed as greedy algorithm] that searches for the smallest spanning tree for linked weighted undirected graph. This algorithm was developed by Vojtěch Jarník, a Czech mathematician in 1930. In 1957 it was further independently developed by Robert C. Prim who is a computer scientist and later on rediscovered in 1959 by Edsger Dijkstra. With so many involved developers, it was also called as the Jarnik algorithm, the Prim-Jarnik algorithm, or the DJP algorithm. Other algorithms are also included in this problem and they are Kruskal's algorithm and the Borůvka's algorithm.
The only difference between these three algorithms is, in Kruskal's and Borůvka's algorithm they can search minimum spanning forests of disconnected graphs while in Prim’s the graph should be connected. Kruskal's algorithm has the same definition as with Prim’s. Their only difference is that in Kruskal's the graph can be found either connected or disconnected while in Prim’s the graph should be connected.
Primes algorithm and Krushkals algorithm
Thank you very much everyone for your nice explanation. Among those comments I particularly respected Sharath, for his comprehensible enlightenment. Sharath, by visiting your comment, comparable discussion about the differences between the primes algorithm and Kruskal’s algorithm to find the minimum spanning tree of a graph, helps me to know that Prim for all time connect a “new” vertex to an “old” vertex, so that all stages is a tree. Kruskal’s permits both “new” to “new” and “old” to “old” to get linked, so it’s danger creating a circuit and have to check for them every time. So Kruskal’s has a superior complexity than Prim. In the conclusion, I can take a decision that Prim’s is easier to draw as well for me. Thanks again for providing a clear idea about the difference between the two algorithms. Well done, Sharath
