Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
1  
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

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.