Example
Download the example data.
| Image | Description |
|---|---|
| AD and CE are the shortest edges, with length 5, and AD has been arbitrarily chosen, so it is highlighted. | |
| CE is now the shortest edge that does not form a cycle, with length 5, so it is highlighted as the second edge. | |
| The next edge, DF with length 6, is highlighted using much the same method. | |
| The next-shortest edges are AB and BE, both with length 7. AB is chosen arbitrarily, and is highlighted. The edge BD has been highlighted in red, because there already exists a path (in green) between B and D, so it would form a cycle (ABD) if it were chosen. | |
| The process continues to highlight the next-smallest edge, BE with length 7. Many more edges are highlighted in red at this stage: BC because it would form the loop BCE, DE because it would form the loop DEBA, and FE because it would form FEBAD. | |
| Finally, the process finishes with the edge EG of length 9, and the minimum spanning tree is found. |
Read more about this topic: Kruskal's Algorithm
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)