I’ve just written a script that executes Kruskal’s algorithm on a randomly generated graph.
Given a weighted graph, many times we are interested in finding a minimum spanning tree (MST) for that graph. These have several applications in areas like transportation and the network simplex method. We already discussed Prim’s algorithm. Another method for generating minimum spanning trees is Kruskal’s algorithm. A spanning tree is a subset of the edges of a graph that connects to every vertex, but contains no cycles. This spanning tree is called a minimum spanning tree if in addition the sum of the weights of the edges included in this tree is less than or equal to the sum of the weights of the edges of any other spanning tree for this graph.
Kruskal’s algorithm works by the following procedure.
1. Initially each vertex is a stand-alone tree, so for each v in V, we define the tree Treev = {v}. The set of selected edges E* is initially empty.
2. Find the edge e = (u, v) of minimum weight such that u and v belong to different trees. If no such edge exists, go to 6.
3. Merge the trees Tlookup(u) and Tlookup(v).
4. Add the edge e to E* and remove the edge e from the graph.
5. If the size of E* is less than n – 1, go to step 2. Else go to step 7.
6. If you reached this step. then the graph is not connected.
7. If you reached this step, then E* is a minimum spanning tree.
For example, consider the graph represented by the following adjacency matrix:
| 0 | 1 | 2 | 3 | 4 | |
| 0 | – | – | – | 13 | 12 |
| 1 | – | – | – | – | 16 |
| 2 | – | – | – | – | 24 |
| 3 | 13 | – | – | – | 13 |
| 4 | 12 | 16 | 24 | 13 | – |
Initially we have 5 distinct trees and E* = {}/
T0 = {0}
T1 = {1}
T2 = {2}
T3 = {3}
T4 = {4}.
The first step of Prim’s algorithm says to find the cheapest edge such that its two endpoints belong to different trees. This will be the edge (0, 4) with a cost of 12. So E* = {(0, 4)}. We then merge the two trees so that our trees are now:
T0 = {0, 4}
T1 = {1}
T2 = {2}
T3 = {3}
Again, we look for the cheapest edge such that the endpoints of the two edges are in different trees. There are two edges with a cost of 13 (either (0, 3) or (3, 4)) so we will arbitrarily choose (0, 3) and add it to our tree. So E* = {(0, 4), (0, 3)}. We again merge the associated trees and it results in the following trees:
T0 = {0, 3, 4}
T1 = {1}
T2 = {2}
The cheapest edge that has endpoints in distinct trees will be the edge (1, 4) with a cost of 16. We add this edge to our tree. So E* = {(0, 4), (0, 3), (1, 4)}. Once we merge the associated trees we have the following:
T0 = {0, 1, 3, 4}
T2 = {2}
The cheapest remaining edge that has endpoints in distinct trees will be the edge (2, 4) with a cost of 16. This makes E* = {(0, 4), (0, 3), (1, 4), (2, 4)}. We merge the associated trees and arrive at:
T0 = {0, 1, 2, 3, 4}
Because T0 contains all the nodes in the graph it is a spanning tree. Its total cost is 12 + 13 + 16 + 24 = 65.
To learn more and see more examples, view Kruskal’s Algorithm at LEARNINGlover.com