Kruskal's MST Algorithm

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph.
It works by growing forest. Kruskal's algorithm finds a safe edge to add to the growing forest by finding an edge with least weight that connects two tree in the forest.

Algorithm

# here + means union of twp sets
KRUSKAL(G):
  A = NULL
  foreach v in G.V:
  MAKE-SET(v)
  foreach (u, v) ordered by weight(u, v), increasing:
    if FIND-SET(u) != FIND-SET(v):
      A = A + {(u, v)}
      UNION(u, v)
  return A

C Implementation Using Disjoint Set Data Structure

/* Kruskals MST Algorithm Implemented Using Disjoint Set Data Structure (Union & Find).....
 * Where Graph Is Represented In Adjacency Matrix Structure "AdjMa".....
 * Each Cell Has Two Members weight and visited.....
 * For Sorting The Edges WRT Its Weight A Edge: Structure Is Considered.....
 * Where 'u' & 'v' are each end of a vertex with corresponding 'weight'......
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE 1
#define FALSE 0
#define N 4
#define INF 9999

typedef struct
{
    int weight;
    int visited;
}AdjMatrix;

typedef struct
{
    int weight;
    int u;
    int v;
}Edge;

void takeInput(AdjMatrix graph[][N])
{
    int i,j;
    printf("Enter The Matrix:\n");

for(i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            scanf("%d",&graph[i][j].weight);
            if(graph[i][j].weight == 0) graph[i][j].weight = INF;
            graph[i][j].visited = FALSE;
        }
    }
}

void printGraph(AdjMatrix graph[][N])
{
    int i,j;
    for(i = 0; i < N; i++)
    {
        putchar('[');
        for (j = 0; j < N; j++)
        {   if(graph[i][j].weight == INF)
                printf("%3d ",0);
            else
                printf("%3d ",graph[i][j].weight);
        }
        putchar(']');
        putchar('\n');
    }
}

int find(int set[], int i)
{

    if (set[i] == -1)
        return i;
    else
        return find(set, set[i]);
}

//Function to union two sets...
void Union(int set[], int u, int v)
{
    int uset = find(set, u);
    int vset = find(set, v);
    set[uset] = vset;
}

//A comparison function for built-in qsort()...
int myComp(const void* a, const void* b)
{
    Edge *a1 = (Edge *)a;
    Edge *b1 = (Edge *)b;

    if (a1->weight > b1->weight)
        return 1;
    else
        return -1;
}

//Function for finding MST using Kruskal's Algorithm....
void kruskalMST(AdjMatrix graph[][N])
{
    int i, j, k=0, x, y, set[20], cost = 0, e=0;
    AdjMatrix tree[N][N];
    Edge edge[20];

    //Picking The Edges...
    for(i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            tree[i][j].weight = 0;
            if(graph[i][j].visited != TRUE)
            {
                edge[k].weight = graph[i][j].weight;
                edge[k].u = i;
                edge[k++].v = j;
                graph[j][i].visited = TRUE;

            }
        }
    }

    //Sorting the edges using quicksort()....
    qsort(edge, k, sizeof(Edge), myComp);

    //Setting all elements of parent = -1
    //each element of parent is a disjoint set..
    memset(set, -1, N * sizeof(set[0]));

    i = 0;
    //Loops untill all vertices are considered that is e = #(vertices) - 1
    while (e < N - 1)
    {
        x = find(set, edge[i].u);
        y = find(set, edge[i].v);

        if (x != y)
        {
            cost = cost + edge[i].weight;
            tree[x][y].weight = edge[i].weight;
            tree[y][x].weight = edge[i].weight;
            Union(set, x, y);
            e++;
        }
        i++;
    }

    puts("\nAdjMatrix For MST:\n");
    printGraph(tree);
    printf("\n\nMST Cost = %d",cost);
}


int main()
{
    AdjMatrix graph[N][N];
    system("cls");
    takeInput(graph);
    printf("\nGiven Graph In AdjMatrix Representation:\n");
    printGraph(graph);
    kruskalMST(graph);
    return 0;
}

Output

Enter The Matrix:
0 7 5 2
7 0 4 3
5 4 0 1
2 3 1 0

Given Graph In AdjMatrix Representation:
[  0   7   5   2 ]
[  7   0   4   3 ]
[  5   4   0   1 ]
[  2   3   1   0 ]

AdjMatrix For MST:
[  0   0   0   2 ]
[  0   0   0   3 ]
[  0   0   0   1 ]
[  2   3   1   0 ]

MST Cost = 6
--------------------------------
Process exited after 50.48 seconds with return value 0
Press any key to continue . . .

Discussion

• Time Complexity: Time complexity of Kruskals algorithm depends on how we implement each operation like cycle detection and union and sorting etc
• It can be shown to run in O(ElogE) time or equivalently O(ElogV)
• It can be shown to run in O(ElogE) time or equivalently O(ElogV)
• WE can use Union-Find for cycle detection to keep track of which vertices are in which component, Which has at most e iterations. Union Find by rank or path compression take O(log(v)) time.
  • Total = O(ElogE + ElogV) = O(Elog E) or O(ElogV)