A spanning tree contains all nodes of a graph and some of its edges so that there is a path between any two nodes. Like trees in general, spanning trees are connected and acyclic. The weight of a spanning tree is the sum of its edge weights. For example, Fig. 35 shows a graph and one of its spanning tree. The weight of this spanning tree is $3 + 5 + 9 + 3 + 2 = 22.$
Kruskal’s algorithm builds a minimum spanning tree by greedily adding edges to the graph. The initial spanning tree only contains the nodes of the graph and does not contain any edges. Then the algorithm goes through the edges ordered by their weights and always adds an edge to the graph if it does not create a cycle.
Prim’s algorithm is an alternative method for constructing minimum spanning trees. The algorithm first adds an arbitrary node to the tree, and then always chooses a minimum weight edge that adds a new node to the tree. Finally, all nodes have been added and a minimum spanning tree has been found.
A union-find structure maintains a collection of sets. The sets are disjoint, so no element belongs to more than one set. Two $\cal(\log n)$ time operations are supported: the unite operation joins two sets, and the find operation finds the representative of the set that contains a given element.