Use Kruskal’s MST Algorithm In Networking Application
Introduction
Imagine a network of airports represented by the vertices. The airline between two airports represented by edges, and each edge weighted by the cost for an airplane to fly from one airport to the next. What if a traveler wants to spend the least money to travel every city listed on the map. By the end of this article, you would know how to implement Kruskal’s Algorithm to come up the most affordable route for this traveler.
Kruskal’s Algorithm is also call greedy algorithm. It was first introduced by an American mathematician Joseph Bernard Kruskal in 1956. It finds a minimum spanning tree (MST) of an undirected edge-weighted graph of a connected graph. The minimum weight of a spanning tree is the sum of weights given to each edge of the spanning tree.
How it works
The idea of Kruskal’s Algorithm is to maintain an acyclic spanning subgraph, enlarging it by edges with the lowest weight to form a spanning tree. In this case, consider all edges are in nondecreasing order of weights.
The iteration starts from picking the cheapest edge, if the next cheapest edge connects two components, then we include this edge to our spanning subgraph, otherwise we discard it. We stop the iteration once all the components are connected.
Setup
Create a Node class function takes in two arguments: the node’s name and array of tuples of the node’s neighbors with edge weight.
For the graph above, we use the Node class function to generate new node for each vertex, thus, the graph can be presented as array of these new nodes.
Implementation
Create Graph class takes an array of list of all nodes in the graph
Get all the non-repeated edges, we need to ensure the output do not have duplicated edges. For example, [ ((‘A’, ‘B’), 1), ((‘B’, ‘A’), 1)) ] are the same edge which should excluded.
sort the edges in a non-decreasing order
Define Kruskal function, initial an empty array as a spanning subgraph
Iterate through the edge array, check if the current edge creates a cycle with the edges we have visited. If cycle was not created, append to the MST list, else, skip that edge. Iteration stops at ( N-1 ) edges.
At last, calculates the minimum weight from each edge in the MST list.
Conclusion
Using Kruskal’s algorithm not only finds the most affordable route for the traveler at the beginning of this article, in fact, it also widely used in designing the network. Another efficient example is finding out the shortest path for laying down the electrical cable wires to save huge amount on the cost of wires.
Prim’s algorithm is another way to find the minimum spanning tree. Kruskal’s algorithm runs faster in sparse graphs, while Prim’s algorithm runs faster in dense graphs.
