Kruskal's algorithm

Previous: Algorithms

Kruskal’s algorithm is a method of obtaining a minimum spanning tree of an undirected, edge-weighted graph. It makes use of a disjoint set data structure.

The solution using Kruskal’s algorithm requires both the edges and the number of vertices. If the vertices are not explicitly provided, they can be inferred by examining all unique endpoints in the edge list. Moving on to the actual algorithm, sort the edges by weight in ascending order and then begin adding them to the MST using the disjoint set to detect cycles. An edge is added only if it connects two different components and doesn’t create a cycle. A minimum spanning tree has been produced when the number of edges added is equal to the number of vertices minus one.