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 
Animation of Kruskal's Algorithm
  

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.

Kruskal’s Algorithm for Finding Minimum Cost Spanning Tree

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.

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

  1. 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;

    }

  2. the most complex code that i have seen in your blog made it so complex using typedef and many unnecessary snippets could have made it little simpler to understand.

  3. I don’t understand the matrix the program gives as an answer. The last column is the cost but what are the first two columns?

  4. Your code could be little modified as :

    #include
    #define MAX 30
    typedef struct edge
    {
    int u,v,w;
    }edge;
    edge edgelist[MAX];
    int G[MAX][MAX],n,e=0,s=0;
    edge spanlist[MAX];
    void kruskal();
    int find(int belongs[],int vertexno);
    void union1(int belongs[],int c1,int c2);
    void sort();
    void print();
    int main()
    {
    int i,j;
    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();
    return 0;
    }
    void kruskal()
    {
    int belongs[MAX],i,j,cno1,cno2;
    for(i=1;i<n;i++)
    for(j=0;j<i;j++)
    {
    if(G[i][j]!=0)
    {
    edgelist[e].u=i;
    edgelist[e].v=j;
    edgelist[e].w=G[i][j];
    e++;
    }
    }
    sort();
    for(i=0;i<n;i++)
    belongs[i]=i;
    for(i=0;i<e;i++)
    {
    cno1=find(belongs,edgelist[i].u);
    cno2=find(belongs,edgelist[i].v);
    if(cno1!=cno2)
    {
    spanlist[s]=edgelist[i];
    s++;
    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<e;i++)
    for(j=0;jedgelist[j+1].w)
    {
    temp=edgelist[j];
    edgelist[j]=edgelist[j+1];
    edgelist[j+1]=temp;
    }
    }
    void print()
    {
    int i,cost=0;
    for(i=0;i<s;i++)
    {
    printf("\n%d\t%d\t%d",spanlist[i].u,spanlist[i].v,spanlist[i].w);
    cost=cost+spanlist[i].w;
    }
    printf("\n\nCost of the spanning tree=%d",cost);
    }

Leave a Comment

Your email address will not be published. Required fields are marked *