Kruskal's Algorithm implementation using C++

By Saptneel Sharma

Kruskal's Algorithm is used to find the minimum spanning tree/forest of an edge-weighted undirected graph.

Kruskal's algorithm finds the minimum spanning tree in a connected, edge-weighted, undirected graph. If the graph is disconnected, it can also find the minimum spanning forest by finding the minimum spanning tree for each disconnected portion.

The steps for the algorithm are:

Step 1: Sort the weighted edges.

Step 2: Traverse the sorted edges and check whether selecting the edge results in a cycle.

Step 3: If the current edge does not create a cycle, then add it to selected edges.

 

While it is easy to visualize as a human whether the edge will make a cycle or not, it is trickier to implement in a program. One way to do that is to use the concept of disjoint-sets/union-find data structure. It basically means to store collections of disjoint sets. In our case, a disjoint set will contain vertices that are connected with each other but are not connected to any other vertex. Each set will be a tree in itself, so it will have a root vertex. Hence, every time we counter a new edge, we check if the 2 vertices belong to the same set or different sets by comparing their roots. If they belong to the same set, then the edge is basically connecting vertices that are already connected, hence forming a cycle. If they belong to different sets, then it means we can select the edge and connect two disjoint sets into a single set with a single root. The new root can be either the root of the first set or the second. Ideally, we want to make the root of the larger set the root of the new set.

This is implemented of this C++ packet here for Kruskal's algorithm :

//used to initialize all the vertices as disjoint sets with size[] array telling about the no. of child nodes inclusive of the root.
void initialise(char arr[], int size[], int n)
{
    for (int i = 0; i < n; i++)
    {
        arr[i] = (char)(i + 97);
        size[i] = 1;
    }
}

//used the find the root of a vertex 'a'
char find(char arr[], char a)
{
    if (a != arr[(int)a - 97])
        arr[(int)a - 97] = find(arr, arr[(int)a - 97]);
    return a;
}

//used to check if the root of 'a' is equal to the root of 'b' or not
bool root(char arr[], char a, char b)
{
    if (find(arr, a) == find(arr, b))
    {
        return true;
    }
    return false;
}

//used to combine two disjoint sets
void combine(char arr[], int size[], char a, char b)
{
    char rootA = find(arr, a);
    char rootB = find(arr, b);
    if (size[(int)rootA - 97] < size[(int)rootB - 97])
    {
        arr[(int)rootA - 97] = rootB;
        size[(int)rootB - 97] += size[(int)rootA - 97];
    }
    else
    {
        arr[(int)rootB - 97] = rootA;
        size[(int)rootA - 97] += size[(int)rootB - 97];
    }
}

 

Using union-find, the Kruskal algorithm can be implemented easily as given below (download the project for complete understanding):

Edge* Graph::get_accepted_edges()
{
    qsort(edges, e, sizeof(edges[0]), comp);
    int count = 0, i = 0;
    while (count < v - 1)
    {
        if (!(root(arr, edges[i].get_v1(), edges[i].get_v2())))
        {
            accepted_edges[count] = edges[i];
            combine(arr, size, edges[i].get_v1(), edges[i].get_v2());
            count++;
        }
        i++;
    }
    return accepted_edges;
}

 

Output: 

Demonstration of above output:

Input:

         a

       /   \

  3 /       \ 8

   /           \

  b ---7---- c

              /  |

       2  /     | 11

        /        |

     d ---9--- e

 

Output:

         a

       /

  3 /

   /

  b ---7---- c

              /

       2  /

        /

     d ---9--- e