Kruskal's Algorithm

Kruskal's Algorithm

Kruskal's Algorithm is extremely important when we want to find a minimum degree spanning tree for a graph with weighted edges. For example, suppose we have the following graph with weighted edges:

Screen%20Shot%202014-03-20%20at%204.19.56%20PM.png

Finding a minimum weighted spanning tree might not be the hardest task, however, for trees with more vertices and edges, the problem becomes complicated. We will now solve this problem with Kruskal's Algorithm.

Steps to Kruskal's Algorithm

Step 1 Label each vertex (e.g. $x_1, x_2, ...$ or $a, b, c, ...$, etc…).
Step 2 List the edges in non-decreasing order of weight.
Step 3 Start with the smallest weighted and beginning growing the minimum weighted spanning tree from this edge.
Step 4 Add the next available edge that does not form a cycle to the construction of the minimum weighted spanning tree. If the addition of the next least weighted edge forms a cycle, do not use it.
Step 5 Continue with step 4 until you have a spanning tree.

We will now apply Kruskal's algorithm to find a minimum weighted spanning tree..

Step 1 We have already labelled the vertices in this graph as $a, b, c, d, e$ and $f$.
Step 2 The edges listed in non-decreasing weights are $3, 4, 4, 4, 5, 5, 6, 7$.
Step 3 We will start with edge $ab$ since it has the least weight.
Screen%20Shot%202014-03-20%20at%204.30.07%20PM.png
Step 4 The next available edges we can are all of weight $4$. These edges are $bc, cd$, and $ef$. The addition of these edges does not form a cycle, so we can add them all to our graph.
Screen%20Shot%202014-03-20%20at%204.29.53%20PM.png
Step 5 The next available edges we have are $af$ and $ed$, both with weight $5$. Adding either one of these edges results in a spanning tree of the final graph, so we can choose either. Let's choose the edge $af$.

Our final minimum weigh spanning tree is:

Screen%20Shot%202014-03-20%20at%204.30.29%20PM.png

However, this is just one of the two minimum weight spanning trees possible for this graph. If we had chosen edge $ed$ instead, we would have gotten this minimum weight spanning tree:

Screen%20Shot%202014-03-20%20at%204.30.53%20PM.png

Just like with defining spanning trees for a graph, saying "the" minimum weight spanning tree is not necessarily correct as some graphs could have more than one minimum weight spanning trees.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License