Practical C Programming

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 ...