Take the 2-minute tour ×

I read Kruskal's algorithm as it's presented on Wikipedia. There, it says that it's an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph.

But while going through the examples that illustrate this algorithm I am unable to understand why the loops are avoided by marking some of the edges in red.

What is the reason for this?

share|improve this question

migrated from stackoverflow.com Nov 27 '11 at 13:23

This question came from our site for professional and enthusiast programmers.

I think this belongs on cstheory.stackexchange.com –  Raymond Chen Nov 27 '11 at 13:22
Please do not crosspost: we can migrate questions to the right place if you post it on the wrong site. For lack of a better site, non-research-level help with algorithms is on-topic here on Programmers; CSTheory.SE is for research-level theoretical questions. There's a site proposal in the works, Computer Science (Non-Programming), that's supposed to bridge the gap between SO/Programmers and CSTheory. –  user8 Nov 27 '11 at 13:27

2 Answers 2

Kruskal's algorithm, gives a minimum spanning tree, and a tree does not have any cycles (loops). So the algorithm should avoid construction of loops in finding the minimum spanning subgraph.

share|improve this answer

You must already know that you cannot have cycles in a tree. So while adding any edge to the MST you must make sure that no loop or cycle is being created . Secondly in the example that you posted , red color is only used to clarify that this particular link should not be added to the MST as it will create a loop. So loops are not avoided by making some of the edges red rather loops are avoided by not adding the edges that connect the already connected vertices ( for example B and D in step 5 of the example mentioned by you) and such links are shown in red to avoid confusion

share|improve this answer

Your Answer


