Kruskal’s Algorithm in C [Program & Algorithm]

By | March 22, 2014
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.

One thought on “Kruskal’s Algorithm in C [Program & Algorithm]

Leave a Reply

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