Using Kruskal’s algorithm to reduce the cost of visiting many cities
Assume, if you will, that you want to visit many cities without visiting a city twice. Assume further that you are constrained by time, and as a result you want to be efficient in your travel. This can be depicted as a graph. Kruskal’s algorithm can be used to find the minimum spanning tree (MST) which is a subset of the graph that represents how to traverse the cities efficiently. Kruskal’s algorithm is a type of greedy algorithm which prioritizes finding a local optimum in the expectation of finding a global optimum.
Finding the Minimum Spanning Tree by Kruskal’s algorithm entails the following steps:
1. Separate the edges of the graph.
2. Arrange edges in ascending order of weights.
3. Select the edge with the smallest weight for building a spanning tree. Drop the edge if it creates a cycle.
4. Repeat steps 2 and 3 until all the edges have been selected.
Give the graph below, Kruskal’s algorithm can be applied as follows:
Steps 1 and 2 can be represented as shown in the table below.
| Weights | Edges |
| 10 | (A, B) |
| 23 | (D, E) |
| 30 | (A, D) |
| 35 | (B, D) |
| 40 | (B, C) |
| 45 | (A, C) |
| 49 | (C, E) |
Edges (A, B), (D, E), (A, D) and (B, C) can be selected in building the MST because they do not form cycles. (B, D), (A, C) and (C, E) are dropped because they form cycles with other edges.
Therefore, the minimum spanning tree looks like this:
Kruskal’s algorithm is a greedy algorithm because the edge with the least weight is picked at each stage in building the minimum spanning tree (MST) since this appears to be best choice. In choosing what appears to be the best choice at each stage, it is hoped that doing so will lead to the best solution in the aggregate.
