How it works...

Consider the following undirected graph:

Figure 10.39

Because the graph has five vertices, the minimum spanning tree will have four edges. The first step in Kruskal's algorithm is that the edges of the graph are first sorted in ascending order of their weights:

Weight   Src    Dest
 1        1      2
 1        3      5
 2        1      5
 2        2      5
 2        3      4
 3        1      3
 3        2      4
 4        4      5

Now, we will pick up one edge at a time from the preceding table, and, if it does not make a cycle, we will include it in the minimum spanning tree. We begin with edge (1,2). There is no cycle in this edge; therefore, it is included in the minimum spanning tree as follows:

Figure 10.40

The next edge in the table is (3,5). This edge also does not make a cycle, so it included in the minimum spanning tree:

Figure 10.41

Next, pick edge (1,5). Again, no cycle is made with this edge, so it is included in the minimum spanning tree:

Figure 10.42

The next edge in the table is (2,5) but it does make a cycle, so it is discarded. The next edge in the table is (3,4). Edge (3,4) does not make a cycle; therefore, it is added to the minimum spanning tree:

Figure 10.43

The number of vertices is 5, so the number of edges will be v-1, that is, 4, and we have 4 edges, so our minimum spanning tree is complete.

On compiling and running the kruskal.c program, we get an output that is similar to the following screenshot:

Figure 3.44

As you can see, we get the adjacency list representation and the minimal spanning tree using Kruskal's algorithm in the output.