Kruskal’s algorithm will grow a solution from the cheapest edge by adding the next cheapest edge, provided that it doesn’t create a cycle.
Kruskal’s algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).
This algorithm first appeared in Proceedings of the American Mathematical Society and was written by Joseph Kruskal
Nominated!
Brian McMahan is a research engineer at Joostware, a San Francisco-based company specialized in consulting and building intellectual property in natural language processing and deep learning.