Differences between Prim's and Kruskal's algorithms?
Maths and statistics discussion, revision, exam and homework help.
-
- Reputation:
- Thread Starter
- Vengeful, Imperial Overlord of The Student Room
- Posts: 3,840
Differences between Prim's and Kruskal's algorithms?I've read the Edexcel D1 textbook over and over, and I can't get it clear in my head what the difference is between Kruskal's and Prim's algorithms for finding minimum spanning trees.
Can anyone clarify? -
- Reputation:
- Peer Of The TSR Realm
- Location: --
- Posts: 1,405
Re: Differences between Prim's and Kruskal's algorithms?Kruska's builds a minimum spanning tree by adding one edge at a time. The next line is always the shortest (minimum weight) ONLY if it does NOT create a cycle.
Prims builds a mimimum spanning tree by adding one vertex at a time. The next vertex to be added is always the one nearest to a vertex already on the graph. -
- Reputation:
- Peer Of The TSR Realm
- Location: Belfast
- Posts: 1,702
Re: Differences between Prim's and Kruskal's algorithms?Prim always joins a "new" vertex to an "old" vertex, so that every stage is a tree. Kruskal's allows both "new" to "new" and "old" to "old" to get connected, so it risks creating a circuit and must check for them every time. So Kruskal's has a larger complexity than Prim.
-
- Reputation:
- Junior Member
- Location: Bucharest
- Posts: 50
Re: Differences between Prim's and Kruskal's algorithms?Here you find the best answer: http://stackoverflow.com/questions/1...ruskal-vs-prim(Original post by James)
I've read the Edexcel D1 textbook over and over, and I can't get it clear in my head what the difference is between Kruskal's and Prim's algorithms for finding minimum spanning trees.
Can anyone clarify?
However, try and understand each algorithm - wikipedia is a good start. -
- Reputation:
- TSR Legend
- Location: England
Re: Differences between Prim's and Kruskal's algorithms?Sorry, you're a bit late.(Original post by declique)
Here you find the best answer: http://stackoverflow.com/questions/1...ruskal-vs-prim
However, try and understand each algorithm - wikipedia is a good start.
5 years late. -
- Reputation:
- Junior Member
- Location: Bucharest
- Posts: 50
Re: Differences between Prim's and Kruskal's algorithms?Are you from the late police? This is the 3rd result in Google for "prim kruskal" so I didn't do it for the OP but for the people who get here from Google results.
But, yes... assume I don't know to read when this was posted. -
- Reputation:
- TSR Legend
- Location: England
Re: Differences between Prim's and Kruskal's algorithms?Oh sorry, my mind reading machine wasn't working at that precise moment.(Original post by declique)
Are you from the late police? This is the 3rd result in Google for "prim kruskal" so I didn't do it for the OP but for the people who get here from Google results.
But, yes... assume I don't know to read when this was posted.
My bad. -
- Reputation:
- TSR Demigod
- Location: England
- Posts: 5,613
Re: Differences between Prim's and Kruskal's algorithms?Prim's is easier to draw.
Aside from that, Prim's selects edges only from the set of edges that are adjacent to those you have already put in your tree. Kruskal's selects edges from the set of all possible edges. -
- Reputation:
- New Member
- Posts: 1
Re: Differences between Prim's and Kruskal's algorithms?you sir may have just got me the B I need in maths!(Original post by edmundwillis)
The attachments are from an OCR (MEI) cheatsheet but I am sure Edexcel will tackle these questions in the same way.
Hopefully, they make the different methods simple enough.
-
- Reputation:
- TSR Demigod
- Location: Linton Travel Tavern
- Posts: 7,204
Re: Differences between Prim's and Kruskal's algorithms?i like Prim's... i used not to like the matrix method but it is OK now
one of my textbooks says you should also check that Prim's does not form a cycle but i guess that is just a mistake.
Prim's reminds me of Pimms...
