Primes algorithm and Krushkals algorithm

Asked By 10 points N/A Posted on -
qa-featured

Hi,

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

  • Answer Accepted: Yes
  • Question Category:
SHARE
Best Answer by Sharath Reddy
Go To Solution
Answered By 0 points N/A #102550

Primes algorithm and Krushkals algorithm

qa-featured

 

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
  • Posted on -
  • Question Category:
Best Answer
Best Answer
Answered By 590495 points N/A #102551

Primes algorithm and Krushkals algorithm

qa-featured

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
  • Posted on -
  • Question Category:
Answered By 10 points N/A #102552

Primes algorithm and Krushkals algorithm

qa-featured

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
  • Posted on -
  • Question Category:

Set a password for Internet Explorer.

Previous

What is binary digits and who invented it?

Next

Related Questions