In this recipe, we will learn how to create a minimum spanning tree. A minimum spanning tree of a graph with n number of nodes will have n nodes. In a connected weighted graph, each edge of the graph is assigned a non-negative number called the "weight of the edge." Then, any spanning tree of the graph is assigned a total weight obtained by adding the weights of the edges in the tree. A minimum spanning tree of a graph is a spanning tree whose total weight is as small as possible.
There are a number of techniques that you can use to create a minimum spanning tree for a weighted graph. One of these methods is called Prim's algorithm.
Prim's algorithm is part of the category of greedy algorithms, where vertices are connected with edges that have the lowest weights. An arbitrary node is chosen initially as the tree root. In an undirected graph, any node can be considered as the tree root and the nodes adjacent to it as its children. The nodes of the graph are then appended to the tree, one at a time, until all of the nodes of the graph are included. The node of the graph added to the tree at each point is adjacent to a node of the tree by an arc of minimum weight. The arc of minimum weight becomes a tree arc connecting this new node to the tree. When all the nodes of the graph have been added to the tree, a minimum spanning tree is said to be made for the graph.