Kruskal’s Algorithm in C [Program & Algorithm]

This instructional exercise is about kruskal’s calculation in C.

It is a calculation for finding the base expense spreading over a tree of the given diagram. In kruskal’s calculation, edges are added to the spreading over the tree in expanding request of cost. In the event that the edge E frames a cycle in the spreading over, it is disposed of.

Kruskal’s Algorithm

This calculation will make traversing tree with least weight, from a given weighted diagram.

Start

Make the edge rundown of a given chart, with their loads.

Sort the edge rundown as indicated by their loads in the climbing request.

Attract every one of the hubs to make a skeleton for spreading over the tree.

Get the edge at the highest point of the edge list (for example edge with least weight).

Expel this edge from the edge list.

Associate the vertices in the skeleton with a given edge. On the off chance that by interfacing the vertices, a cycle is made in the skeleton, at that point dispose of this edge.

Rehash stages 5 to 7, until n-1 edges are included or rundown of edges is finished.

Return

Program for Kruskal’s Algorithm in C

A-C program for developing a base cost spreading over tree of a chart utilizing Kruskal’s calculation is given underneath.

#include<stdio.h>
 
#define MAX 30
 
typedef struct edge
{
	int u,v,w;
}edge;
 
typedef struct edgelist
{
	edge data[MAX];
	int n;
}edgelist;
 
edgelist elist;
 
int G[MAX][MAX],n;
edgelist spanlist;
 
void kruskal();
int find(int belongs[],int vertexno);
void union1(int belongs[],int c1,int c2);
void sort();
void print();
 
void main()
{
	int i,j,total_cost;
	
	printf("\nEnter number of vertices:");
	
	scanf("%d",&n);
	
	printf("\nEnter the adjacency matrix:\n");
	
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&G[i][j]);
			
	kruskal();
	print();
}
 
void kruskal()
{
	int belongs[MAX],i,j,cno1,cno2;
	elist.n=0;
 
	for(i=1;i<n;i++)
		for(j=0;j<i;j++)
		{
			if(G[i][j]!=0)
			{
				elist.data[elist.n].u=i;
				elist.data[elist.n].v=j;
				elist.data[elist.n].w=G[i][j];
				elist.n++;
			}
		}
 
	sort();
	
	for(i=0;i<n;i++)
		belongs[i]=i;
	
	spanlist.n=0;
	
	for(i=0;i<elist.n;i++)
	{
		cno1=find(belongs,elist.data[i].u);
		cno2=find(belongs,elist.data[i].v);
		
		if(cno1!=cno2)
		{
			spanlist.data[spanlist.n]=elist.data[i];
			spanlist.n=spanlist.n+1;
			union1(belongs,cno1,cno2);
		}
	}
}
 
int find(int belongs[],int vertexno)
{
	return(belongs[vertexno]);
}
 
void union1(int belongs[],int c1,int c2)
{
	int i;
	
	for(i=0;i<n;i++)
		if(belongs[i]==c2)
			belongs[i]=c1;
}
 
void sort()
{
	int i,j;
	edge temp;
	
	for(i=1;i<elist.n;i++)
		for(j=0;j<elist.n-1;j++)
			if(elist.data[j].w>elist.data[j+1].w)
			{
				temp=elist.data[j];
				elist.data[j]=elist.data[j+1];
				elist.data[j+1]=temp;
			}
}
 
void print()
{
	int i,cost=0;
	
	for(i=0;i<spanlist.n;i++)
	{
		printf("\n%d\t%d\t%d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w);
		cost=cost+spanlist.data[i].w;
	}
 
	printf("\n\nCost of the spanning tree=%d",cost);
}

Output

Time Complexity of Kruskal’s Algorithm

Give us a chance to expect a chart with e number of edges and n number of vertices. Kruskal’s calculation begins with arranging of edges.

Time unpredictability of arranging algorithm= O (e log e)

In Kruskal’s calculation, we need to add an edge to the traversing tree, in every cycle. This includes converging of two parts.

Time unpredictability of converging of components= O (e log n)

In general time intricacy of the algorithm= O (e log e) + O (e log n)

Correlation of Time Complexity of Prim’s and Kruskal’s Algorithm

The unpredictability of Prim’s algorithm= O(n2)

Where n is a number of vertices.

Time Complexity of Kruskal’s algorithm= O (e log e) + O (e log n)

Where n is a number of vertices and e is the number of edges.

For a thick chart, O (e log n) may turn out to be more terrible than O (n2). Henceforth, the Kruskal’s calculation ought to be maintained a strategic distance from for a thick diagram. Kruskal’s calculation performs superior to Prim’s calculation for an inadequate diagram.

Remark beneath in the event that you discover anything incorrect or missing in over Kruskal’s calculation in C instructional exercise.