In this recipe, we will learn how to make a minimum spanning tree using Kruskal's algorithm.
A minimum/minimal spanning tree of an undirected graph is a tree that is formed from graph edges that connect all of the vertices of the graph at the lowest total cost. A minimum spanning tree can exist if, and only if, the graph is connected. A graph is said to be connected if there exists a path between any two vertices.
Here, the nodes of the graph are initially considered as n distinct partial trees with one node each. At each step of the algorithm, two distinct partial trees are connected into a single partial tree by an edge of the graph. When only one partial tree exists (for instance, after n-1 such steps), it is a minimum spanning tree.
The connecting arc of minimum cost is used to connect two distinct trees. To do this, the arcs can be placed in a priority queue based on weight. The arc of lowest weight is then examined to see whether it connects two distinct trees. To determine whether an arc (x, y) connects two distinct trees, we can implement the trees with a father field in each node. Then, we can traverse all the ancestors of x and y to obtain the root of the tree connecting them. If the root of the two trees is the same node, and x and y are already in the same tree, then arc (x, y) is discarded, and the arc of the next lowest weight is examined.