Creating the minimum spanning tree

To make the minimum spanning tree, we need to adjust the edges of the vertices in ascending order. The temp1 pointer is set to point at startList, that is, vertex 1. The temp2 pointer is set to point to where the edg pointer of temp1 is pointing to, that is, vertex 2.

Now, until temp2 becomes NULL, the addpqu function is invoked and vertices 1 and 2, and their weight, 1, are passed to it. In the addpqu function, a structure is created called lstNode of the lst type. The 1 and 2 vertices and their weight, 1, are assigned to the u, v, and wt members, respectively. The next pointer of lstNode is set to NULL. Additionally, a pointer, pq, is set to point to lstNode.

Following this, the temp2 pointer is set to point to where its edg pointer is pointing, that is, vertex 3. Again, the addpqu function is called and vertices 1 and 3 and weight 3 are passed to it. In the addpqu function, again, a new node is creating, called lstNode, and vertices 1 and 3 and weight 3 are assigned to its u, v, and wt members, respectively. The next pointer of lstNode is set to NULL.

Because the nodes have to be arranged in ascending order of their weights, the wt member of lstNode and the previous node, pq, are compared. The wt member of lstNode is 3, which is greater than the wt member of the pq node, which is 1. So, the help of two pointers, findloc1 and findloc2, is taken. One pointer is set to point to the weights of lstNode, and the pq nodes are compared.

Let's choose a vertex, 1, and add it to the minimum spanning tree:

Figure 10.33

Now, from vertex 1, there are edges to the vertices of 3, 2, and 5, but the edge with the minimum weight is to vertex 2. So, vertex 2 is also added to the minimum spanning tree:

Figure 10.34

Again, from vertices 1 and 2 in the minimum spanning tree, we search for all the edges that lead to other vertices. We find that edges (1,5) and (2,5) have the same weight, so we can choose either of the vertices. Let's add edge (2,5) to the minimum spanning tree:

Figure 10.35

From the vertices of 1, 2, and 5 in the minimum spanning tree, we search for the edges with the lowest weights. Edge (5,3) has the minimum weight of 1, so edge (5,3) is added to the minimum spanning tree:

Figure 10.36

Now, we need to find the edge that leads to vertex 4 from the existing vertices in the minimum spanning tree. Edge (3,4) has the lowest weight and is, therefore, added to the minimum spanning tree:

Figure 10.37

On compiling and running the program, you should get an output that is similar to the following screenshot:

Figure 10.38

Now, let's move on to the next recipe!