The algorithm starts with V different trees (V is the vertices in the graph). While constructing the minimum spanning tree, every time Kruskal’s algorithm selects an edge that has minimum weight and then adds that edge if it doesn’t create a cycle.

Initially, there are | V | single-node trees in the forest. Adding an edge merges two trees into one. When the algorithm is completed, there will be only one tree, and that is the minimum spanning tree. There are two ways of implementing Kruskal’s algorithm:

• By using Disjoint Sets: Using UNION and FIND operations
• By using Priority Queues: Maintains weights in priority queue

The appropriate data structure is the UNION/FIND algorithm.

Each vertex is initially in its own set. If u and v are in the same set, the edge is rejected because it forms a cycle. Otherwise, the edge is accepted, and a UNION is performed on the two sets containing u and v.

As an example, consider the following graph (the edges show the weights).

Now let us perform Kruskal’s algorithm on this graph. We always select the edge which has minimum weight.

The edges which have minimum weight (cost) are: AD and BE. From these two we can select one of them and let us assume that we select AD (dotted line).

DF is the next edge that has the lowest cost (6).

BE now has the lowest cost and we select it (dotted lines indicate selected edges).

DF is the next edge that has the lowest cost (6) that we select.

Next, AC and CE have the low cost of 7.

We select AC.

Then we select CE as its cost is 7 and it does not form a cycle.

The next low cost edges are CB and EF. But if we select CB, then it forms a cycle. So we discard it. This is also the case with EF. So we should not select those two. And the next low cost is 9 (CD and EG). Selecting CD forms a cycle so we discard it. Adding EG will not form a cycle and therefore with this edge we complete all vertices of the graph.

#include <stdio.h>
#include <stdlib.h>
#define M 100
 
typedef struct 
{
	int tab[M], p[M], rank[M],setSize[M];
	int numSets;
	 
} SET;

SET create(int N)
{
	SET S;
	int i;

	S.numSets = N;
	for(i=0;i<N;i++)
	{
		S.setSize[i]=1;
		S.rank[i]=0;
		S.p[i]=i;
	}
	return S;
}

int findSet(int i, SET S) 
{
	return (S.p[i] == i) ? i : (S.p[i] = findSet(S.p[i], S)); 
}



int isSameSet(int i, int j, SET S) 
{ 
	return findSet(i, S) == findSet(j, S); 
}

 
int numDisjointSets(SET S) 
{ 
	return S.numSets; 
}

int sizeOfSet(int i, SET S) 
{ 
	return S.setSize[findSet(i, S)]; 
}

 
void unionSet(int i, int j, SET *S) 
{ 
	int x, y;
	
    if (!isSameSet(i, j , *S)) 
	{ 
		S->numSets--; 
    	x = findSet(i, *S);
		y = findSet(j, *S);
	 
    	if (S->rank[x] > S->rank[y]) 
		{ 
			S->p[y] = x; 
			S->setSize[x] += S->setSize[y]; 
		}
    	else                   
		{ 
			S->p[x] = y; 
			S->setSize[y] += S->setSize[x];
			if (S->rank[x] == S->rank[y]) 
				S->rank[y]++; 
		} 
	} 
}



typedef struct {
	int u, v;
} edge;


typedef edge element;
struct cell { 
	element data; 
	int priority;
	struct cell *next; 
};

typedef  struct { 
	struct cell *front; 
} queue;

queue CreateQueue()
{
	queue q;
	q.front = NULL;
	return q;
}

int isEmptyQueue(queue q)
{
	return q.front == NULL;
}

int Front(queue q, element *e, int *priority)
{
	if (isEmptyQueue(q)) return 0;
	*e = q.front->data;
	*priority = q.front->priority; 
	return 1;
}


int DeQueue(queue *q)
{
	struct cell *temp;
	if (isEmptyQueue(*q)) return 0;
	temp = q->front;
	q->front = q->front->next;
	free(temp);
	return 1;
}

 
void display_queue(queue tmp)
{
	struct cell *temp = tmp.front;

	if (temp == NULL)
		printf("Queue is empty\n");
	else
	{
		printf("Queue is :\n");
		printf("Item\n");
		while (temp != NULL)
		{
			printf("%5d    %5d %5d\n\n", temp->priority, temp->data.u,temp->data.v);
			temp = temp->next;
		}
	}
}
 

int EnQueue(queue *q, element e, int priority)
{
	struct cell *temp, *href;
	temp = (struct cell *) malloc(sizeof(struct cell));
	if (!temp) return 0;
	temp->data = e;
	temp->priority = priority;

	if (q->front == NULL || priority < q->front->priority) {/*Queue is empty or item to be added has priority more than first item*/
		temp->next = q->front;
		q->front = temp;
	}
	else
	{
		href = q->front;
		while (href->next != NULL && href->next->priority <= priority)
			href = href->next;
		temp->next = href->next;
		href->next = temp;
	}

	return 1;
}

void delete_head(struct cell **nodeRef)
{
	struct cell *p;
	p = *nodeRef;
	*nodeRef = (*nodeRef)->next;
	free(p);
}

// delete a given element (recursive)
int delete_value(struct cell **nodeRef, element e)
{
	if (*nodeRef == NULL)
		return 0;
	if ((*nodeRef)->data.u == e.u)
	{
		delete_head(nodeRef);
		return 1;
	}
	return delete_value(&((*nodeRef)->next), e);
}


void recursive_ordered_insert(struct cell **node, element value, int priority)
{
	struct cell *temp;
	if ((*node == NULL) || !((*node)->priority <= priority))
	{
		temp = *node;
		*node = (struct cell *) malloc(sizeof(struct cell));
		if (!*node) return ;
		(*node)->data = value;
		(*node)->priority = priority;
		(*node)->next = temp;
		return;
	}

	 recursive_ordered_insert(&((*node)->next), value, priority);

}


void update_priority(queue *q, element data, int priority) {
	if (delete_value(&(q->front), data) == 1)
		recursive_ordered_insert(&(q->front), data, priority);
	// or	EnQueue(q, data, priority);
	
}


typedef struct {
	int V;
	int E;
	int **Adj; // since we need 2 dimensional matrix
} Graph;



Graph* adjacencyMatrix() {
	int i, u, v, w;
	Graph* G = (Graph*)malloc(sizeof(Graph));
	printf("Enter the number of Vertices: ");
	scanf("%d", &G->V);
	printf("Enter the number of Edges: ");
	scanf("%d", &G->E);
	G->Adj = (int **)malloc(G->V * sizeof(int*));
	for (u = 0; u < G->V; u++)
		G->Adj[u] = (int *)malloc(G->V * sizeof(int));

	for (u = 0; u<G->V; u++)
		for (v = 0; v<G->V; v++)
			G->Adj[u][v] = 0;
	for (i = 0; i < G->E; i++) {
		printf("Enter the edge and the weight: ");
		scanf("%d %d %d", &u, &v, &w);
		G->Adj[u][v] = w;
	}
	return G;
}


void kruskal(Graph *G)
{
	SET S;
	queue q;
	int u , v, pr;
	edge e, result[G->V] ;

    	//set of edges SE
     	S=create(G->V);
	
    	// sort edges of E by increasing weights W;
	// will use a priority queue, int the queue
	// will store edges

	q = CreateQueue();
	for (u = 0; u<G->V; u++)
		for (v = 0; v<G->V; v++)
			if(G->Adj[u][v])
				EnQueue(&q, (edge){u,v}, G->Adj[u][v]);

	u=0;
	while(Front(q,&e,&pr))
	{
	    DeQueue(&q);
		if(!isSameSet(e.u, e.v, S) )
		{
			result[u++]=e;
			unionSet(e.u, e.v, &S); 
		}		
	}

	printf("Retained edges in the MST: \n");
	for(v=0;v<u;v++)
		printf(" %d -- %d == %d \n", result[v].u, result[v].v, G->Adj[result[v].u][result[v].v]);

}

int main() 
{
	Graph *G = adjacencyMatrix();
	
	kruskal(G);
	return 0;
}