DEV Community

Cover image for Implement Kruskal's Algorithm in C++

Implement Kruskal's Algorithm in C++

nokha_debbarma profile image Nokha Debbarma ・3 min read

Good to have basic idea of:

The implementation code of the Kruskal Algorithm is given below with comments to help understand each line of code.

 using namespace std;

//class for an edge in a graph
 class Edge{
   int ss, dd, ww;
   //ss = source edge
   //dd = destination edge
   //ww = weight of an edge
   Edge( int ss, int dd, int ww)
   { //constructor
     this->ss = ss;
     this->dd = dd;
     this->ww = ww;

//class for a graph
 class Graph{
   vector<Edge>  All_edges;// to hold list of all edges of the graph

   //member function to add an edge to the undirected graph
   void addEdge(int s, int d, int w)
      Edge obj(s, d, w);//create one edge  
      All_edges.push_back(obj);//push one edge to edge container


  //declare a displayMST function to define it later
  void displayMST(const vector<Edge> &);

//class for finding MST in the graph
  class Kruskal {

  int totalVertices;//total vertices

  vector<pair<int,int>> subsets;
  // subsets will hold list of [parent - rank] pairs
  // which we will use in Union Find 
  // by path compression algorithm

  vector<Edge> mst;//declare a container to store edges of MST

    kruskal( int totalVertices)
       this->totalVertices =totalVertices;

       //resize subsets equal to total vertices

       for( int i= 0; i<totalVertices; ++i)
          subsets[i].first =i; //set parent value equal to respective index
          subsets[i].second = 0; //set rank value equal to zero

    static bool comparator( Edge &a , Edge& b)
      return a.ww < b.ww;

    void createMST( Graph& graph)
      //sort the edges of graph in increasing order of their weights
     sort( graph.All_edges.begin(), graph.All_edges.end(), comparator );

    int i=0, e=0;
    // i =  variable to keep track of total vertices 
    // e = variable to keep track of total edges in MST formed so far
    // total edges in MST  == (total vertices - 1)

    //iterate through list of edges in a graph
    while( e < (totalVertices-1) && i < graph.All_edges.size() )
      //store current edge
      Edge currEdge = graph.All_edges[i++];

      //find absolute parent 
     //to detect if current edge form a cycle with MST formed so far
      int x = _find(;//pass current source vertex
      int y = _find( currEdge.dd );//pass current destination vertex

      if( x != y)//is they don't form a cycle 
        //push current edge to MST
        mst.push_back( currEdge );
        //then make that two vertex Union
        // in other words to create edge between two vertices
        makeUnion( x, y);

    //finally display the MST created by the above function
    displayMST( mst );


   int _find(  int i)
       if( subsets[i].first!=i)//if index is not equal to parent value
         //recursively call _find()
         // and pass current parent value 
         subsets[i].first = _find( subsets[i].first );


       return subsets[i].first;

   void makeUnion( int x, int y)
     int xroot = _find( x);
     int yroot = _find(y);

    // if-else for rank comparison & update parent-rank values
     if( subsets[xroot].second < subsets[yroot].second)
       subsets[xroot].first= yroot;
     else if( subsets[xroot].second > subsets[yroot].second)


  // funciton to display all edges of MST & total cost
  void displayMST(  const vector<Edge>&  edges)
     int totalMinimumCost=0;
    cout<<"All MST edges [source - destination = weight]\n";

    for( auto edge : edges)
      cout<<<<" - "<<edge.dd<<" = "<<edge.ww<<'\n';

    cout<<"total minimum cost = "<<totalMinimumCost<<endl;

 int main()

   Graph g;
   //add edeges to graph
   g.addEdge(0, 1, 50);
   g.addEdge( 0 , 2, 10);
   g.addEdge(0, 3, 50);
   g.addEdge(1, 4, 30);
   g.addEdge(3, 4, 100);
   g.addEdge(2, 4, 100);

   //create and object of kruskal class
   kruskal graph(5);

   //call kruskal class's member function to find MST
   graph.createMST( g);

   return 0;


Enter fullscreen mode Exit fullscreen mode


All MST edges [source - destination = weight]
0 - 2 = 10
1 - 4 = 30
0 - 1 = 50
0 - 3 = 50
total minimum cost = 140

Enter fullscreen mode Exit fullscreen mode

Discussion (0)

Forem Open with the Forem app