Kruskal’s Algorithm in C [Program & Algorithm]

This tutorial is about kruskal’s algorithm in C.

It is an algorithm for finding the minimum cost spanning tree of the given graph. In kruskal’s algorithm, edges are added to the spanning tree in increasing order of cost. If the edge E forms a cycle in the spanning, it is discarded.

Kruskal’s Algorithm

This algorithm will create spanning tree with minimum weight, from a given weighted graph.
1. Begin
2. Create the edge list of given graph, with their weights.
3. Sort the edge list according to their weights in ascending order.
4. Draw all the nodes to create skeleton for spanning tree.
5. Pick up the edge at the top of the edge list (i.e. edge with minimum weight).
6. Remove this edge from the edge list.
7. Connect the vertices in the skeleton with given edge. If by connecting the vertices, a cycle is created in the skeleton, then discard this edge.
8. Repeat steps 5 to 7, until n-1 edges are added or list of edges is over.
9. Return

Program for Kruskal’s Algorithm in C

A C program for constructing a minimum cost spanning tree of a graph using Kruskal’s algorithm is given below.

Time Complexity of Kruskal’s Algorithm

Let us assume a graph with e number of edges and n number of vertices. Kruskal’s algorithm starts with sorting of edges.
Time complexity of sorting algorithm= O (e log e)

In Kruskal’s algorithm, we have to add an edge to the spanning tree, in each iteration. This involves merging of two components.

Time complexity of merging of components= O (e log n)

Overall time complexity of the algorithm= O (e log e) + O (e log n)

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

The complexity of Prim’s algorithm= O(n2)
Where, n is number of vertices.

Time Complexity of Kruskal’s algorithm= O (e log e) + O (e log n)
Where, n is number of vertices and e is number of edges.

For a dense graph, O (e log n) may become worse than O (n2). Hence, the Kruskal’s algorithm should be avoided for a dense graph. Kruskal’s algorithm performs better than Prim’s algorithm for a sparse graph.

Comment below if you find anything wrong or missing in above kruskal’s algorithm in C tutorial.

3 thoughts on “Kruskal’s Algorithm in C [Program & Algorithm]”

1. Pooja Veer

Ty so much for this code….its so easy…

2. Tristan Partridge

I love the way you handle the set tracking! The code could do with a few comments thought…

Easy version–

#include
#include
using namespace std;
int e,v;
struct Edge
{
int src,des,wt;
};
void sort1(struct Edge edge[])
{

int i, j,k;
for (i = 0; i < e-1; i++)
{

// Last i elements are already in place
for (j = 0; j edge[j+1].wt)
{
k=edge[j].wt;
edge[j].wt=edge[j+1].wt;
edge[j+1].wt=k;
k=edge[j].src;
edge[j].src=edge[j+1].src;
edge[j+1].src=k;
k=edge[j].des;
edge[j].des=edge[j+1].des;
edge[j+1].des=k;
}}
}
}
int find(int x,int parent[])
{
if(parent[x]==-1)
return x;
find(parent[x],parent);
}
void union1(int x,int y,int parent[])
{int x1,y1;

parent[x]=y;
}
int iscycle(int i ,int parent[],struct Edge edge[])
{int x,y;

x=find(edge[i].src,parent);
y=find(edge[i].des,parent);
if(x!=y)
{
union1(x,y,parent);
return 0;
}
return 1;

}

int main()
{
int i,j,k,n=0,path[745][452],sum=0;

cout<<"enter the total no of edges and vertices"<>e>>v;
int parent[v];
for(i=0;i<v;i++)
{
parent[i]=-1;
}
cout<<"enter the source, destination and weight of node "<<endl;
struct Edge edge[e];
for(i=0;i>edge[i].src>>edge[i].des>>edge[i].wt;

}
sort1(edge);

k=0;
for(i=0;i<e;i++)
{
if(!iscycle(i,parent,edge))
{
path[k][0]=edge[i].src;
path[k++][1]=edge[i].des;
n++;
sum=sum+edge[i].wt;
}
if(n==v-1)
break;
}
for(i=0;i<v-1;i++)
{
printf("%d %d",path[i][0],path[i][1]);
cout<<endl;
}
cout<<endl<<sum;

}