I usually go through research paper’s of some popular Algorithms and DS, most of them goes miles above my head. But…. The paper I found today has one of the most simplistic explanation, and over-simplification of this concept in other books and resources makes it complicated.
Its the Kruskal’s Algorithm to find the minimum spanning tree.
Link to the paper “On the shortest spanning subtree of a Graph and the Travelling Salesman Problem” by Joseph B. Kruskal is here
If you are not aware of this algorithm beforehand, go with me, else you can directly read the paper.
Let’s brush up some knowledge before.
In Computer Science, graph is a collection of nodes and edges connecting these nodes. Sometimes these edges have weights (they are called weighted graphs, the ones we will dealing here). Graphs can be used to model various real-life objects and concepts like
- Road Networks (each nodes being cities, and each edge being roads)
- Server-Client Architecture (each client and server being nodes and the connection being edges)
- Digital Logic State Diagrams (Computer science undergrads can relate 😅😢)
and many more.
Trees are a special kind of graphs, where there is always a unique path between any two nodes. You can visualize it as the minimum number of edges needed to make a collection of nodes connected. A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Some very basic conclusions we can draw is:
- ST (spanning tree) cannot have loops. Because the edge that created the loop contributes no new vertex, hence we will be better off removing it.
- There can be multiple spanning tree. (This is important to understand the fact there would exist one tree which has minimum weight)
|Graph||Spanning Tree (by removing some edges)|
Minimum Spanning Tree
Now if the graph has edge weights, then there would exist one (or more than one) spanning tree where the total edge weight will be minimum. That is called the Minimum spanning tree (MST). Kruskal’s theorem helps us identify the MST.
Before diving into the paper, there is small story behind it. It also explains why the paper is very easy to understand. Kruskal was in his grad school and came across a paper with no origins. He couldn’t follow what was told in the paper, so he tried really hard to figure it out, and makes notes so that it would be easy to understand. So he made some notes for himself. A friend of his suggested him to publish the paper, and then he did publish it (duh!!). That paper became really popular and the algorithm described in it is now known as Kruskal’s algo.
In the very first paragraph he describe the theorem
Clearly, he considered only distinct edges, the purpose was to prove the uniqueness of the MST that can be achieved. Also he further points out two specific problem that can be tackled if the theorem is proved
Problem 1. Give a practical method for constructing a spanning subtree of minimum length.
Problem 2. Give a practical method for constructing an unbranched spanning subtree of minimum length.
He further points out
“Problem 1 on the surface is closely related to one version (Problem 2 below) of the well-known traveling salesman problem”
In problem 1 he is looking to find a Spanning tree, but in problem 2 is looking for an “unbranched”. What he means by unbranched is, every tree can be represented as a parent nodes having child, each child has further children, like a heirarchy. Remeber the graph we showed above, if we represent that in a tree fashion it will be like this
Clearly there are branches, node 5 branched off to 3 nodes. Now if you remove the edge(5, 4) and add an edge(3, 2) we will get this version
This is unbranched. There is more technical term for unbranched spanning tree i.e Hamiltonian Path.
The reason he said “one version of the well-known TSP” is because the actual version of TSP requires Hamiltonian Circuit or Cycle. Where the two endpoints of the path are adjacent and are connected by an edge.
Now if you look at this approach he didn’t solve the theorem directly, he said if could show a construction for Problem 1 then that can be used to solve the theorem. Let’s look into his constructions
This is a very straightforward Greedy Approach. We will come to the C++ implementation later.
There is another construction he mentioned
Now this one seems very close to Prim’s Algo for finding MST. The difference is in Prim’s Algo you look into the edges of those nodes which are already considered / visited. But what Kruskal did was consider all the edges. Cheeky
Also he says that this MST formed by Construction A is unqiue because
- Edges are distinct
- We are considering the edges in ascending order (which is unique)
There is also a proof in the paper, which is quite self-explanatory.