Kruskals’ Algorithm to your Rescue
Kruskal Algorithm is an algorithm used to find the minimum spanning tree for a connected and undirected weighted graph.
This algorithm is a Greedy Algorithm. The Greedy Choice is to pick the smallest weight edge that does not cause a cycle in the MST constructed so far.
This algorithm first appeared in Proceedings of the American Mathematical Society, pp. 48–50 in 1956, and was written by Joseph Kruskal.
Kruskal’s algorithm initially places all the nodes of the original graph isolated from each other, to form a forest of single node trees, and then gradually merges these trees, combining at each iteration any two of all the trees with some edge of the original graph. Before the execution of the algorithm, all edges are sorted by weight (in non-decreasing order). Then begins the process of unification: pick all edges from the first to the last (in sorted order), and if the ends of the currently picked edge belong to different subtrees, these subtrees are combined, and the edge is added to the answer. After iterating through all the edges, all the vertices will belong to the same sub-tree, and we will get the answer.
Kruskal’s Approach:
Select the minimum weight edge that does not form a cycle
A graph is an abstract notation used to represent the connection between pairs of objects. A graph consists of − Vertices − Interconnected objects in a graph are called vertices.
Minimum Spanning tree is basically a subgraph of any given graph that connects all the vertices with a minimum number of edges having minimum possible weight with no cycle. As this graph contains no cycle, that’s why it is called a tree.
A minimum spanning tree of a graph is unique if the weight of all the edges is distinct. Otherwise, there may be multiple minimum spanning trees. (Specific algorithms typically output one of the possible minimum spanning trees).
The minimum spanning tree is also the tree with a minimum product of weights of edges. (It can be easily proved by replacing the weights of all edges with their logarithms)
In a minimum spanning tree of a graph, the maximum weight of an edge is the minimum possible from all possible spanning trees of that graph. (This follows from the validity of Kruskal’s algorithm).
The maximum spanning tree (spanning tree with the sum of weights of edges being maximum) of a graph can be obtained similarly to that of the minimum spanning tree, by changing the signs of the weights of all the edges to their opposite and then applying any of the minimum spanning tree algorithm.
For connecting all the vertices in a given graph we need to have at least vertices-1 edges.
HOW DOES IT WORK?
Using these 3 simple steps you can get your desired MST!
STEP 1:Sort all the edges in non-decreasing order of their weight.
STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning-tree formed so far. If a cycle is not formed, include this edge. Else, discard it.
STEP 3:Repeat step#2 until there are (V-1) edges in the spanning tree.
PSEUDOCODE
Let us understand it with an example: Consider the below input graph:
STEP 1:
WRITE ALL WEIGHTS IN ASCENDING ORDER
BD=2
DE=2
CD=3
AC=3
BE=4
AB=5
BC=6
AF=7
CF=8
STEP 2:
BD and DE have the lowest weights that are 2 and B and E cannot be joined as it will make a cycle
STEP 3:
AC and CD have weight equal to 3 and discard BC and AB as they will form a cycle.
STEP 4:
We will Join A and F and discard CF because its weight is higher than AF.
Thus, we get an MST using these simple steps! just remember min edge weight with no cycle and you are good to go!
COMPLEXITY
For a graph with E edges and V vertices, Kruskal’s algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time, all with simple data structures.
For reference do visit:
https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
IMPROVED IMPLEMENTATION
We can use the Disjoint Set Union (DSU) data structure to write a faster implementation of Kruskal’s algorithm with the time complexity of about O(MlogN).
ABOUT JOSEPH KRUSKAL
Joseph B. Kruskal, Jr., was born in 1928, in New York City. He completed his BS (1948) and MS (1949), both in mathematics, at the University of Chicago. He earned his PhD in mathematics at Princeton University in 1954. During the 1950s, Kruskal also worked in logistical research for the U.S. Office of Naval Research, first at George Washington University’s Logistical Research Project (1950–1953), then at Princeton’s Analytical Research Project (1954–1956). He then taught for three years at the University of Wisconsin — Madison and the University of Wisconsin — Ann Arbor. In 1959, he left teaching to conduct research at Bell Laboratories, in Murray Hill, New Jersey, where he would work for the rest of his career. He officially retired from Bell Labs in 1993, but continued to conduct research there for several years after.
Although trained in pure mathematics, Kruskal’s work at Bell Labs encouraged him to explore statistics, computer science, and various other areas of applied mathematics. His major areas of research and publication included: combinatorics; well-partial-ordered sets (the subject of his doctoral dissertation); multidimensional scaling (MDS) and its applications to various fields, particularly linguistics; psychometrics; and sequence comparison. While at Bell Labs, he worked on TAT-8, the first transatlantic fiber optic cable system. In addition to his research, Kruskal lectured frequently, communicated with other scholars about statistical methodology, and advised graduate students from around the world. He was the second president of the Classification Society of North America (1972–1973) and president of the Psychometric Society (1974–1975). He was named a Fellow of the American Statistical Association in 1971 and a Fellow of the American Association for the Advancement of Science in 1982. Kruskal’s two older brothers, William and Martin, were also well-known mathematicians. Kruskal married his wife, Rachel Solomon, in 1953, and the couple had two children, Joyce and Benjamin. He passed away in 2010.
