Primes algorithm and Krushkals algorithm

Asked By jasper torres 10 points N/A Posted on - 04/06/2012

Hi,

What are the differences between the primes algorithm and Kruskal's algorithm to find the minimum spanning tree of a graph?

• Status: Open
• Question Views: 1093
• Answer Count: 3
• Vote Up 0 Vote Down

• Answer Accepted: Yes
• Question Category: C

Best Answer by Sharath Reddy

Go To Solution

Answered By Sheldon Ron 0 points N/A #102550

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.

 

About Sheldon Ron

Questions
3

Answers
52

Best Answers
10

• Vote Up 0 Vote Down

• Posted on - 04/06/2012
• Question Category: C

Best Answer

Best Answer

Answered By Sharath Reddy 590495 points N/A #102551

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.

About Sharath Reddy

Questions
1

Answers
14599

Best Answers
2290

• Vote Up 0 Vote Down

• Posted on - 04/14/2013
• Question Category: C

Answered By jasper torres 10 points N/A #102552

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

About jasper torres

Questions
18

Answers
4

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 08/30/2013
• Question Category: C