DEV Community

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

Posted on

Implement Kruskal's Algorithm in C++

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.



 #include<iostream>
 #include<algorithm>
 #include<vector>
 using namespace std;

//class for an edge in a graph
 class Edge{
   public:
   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{
   public:
   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 {

  public:
  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

 //constructor
    kruskal( int totalVertices)
    {
       this->totalVertices =totalVertices;

       subsets.resize(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( currEdge.ss);//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)
     {
       subsets[yroot].first=xroot;
     }
     else{
       subsets[xroot].first=yroot;
       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.ss<<" - "<<edge.dd<<" = "<<edge.ww<<'\n';

      totalMinimumCost+=edge.ww;
    }
    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

output:

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

Top comments (1)

Collapse
 
zigrazor profile image
ZigRazor • Edited

Great Job,

I'm doing a large work to create a comprehensive header-only library for C++ for graph Representation, Manipulation, Partitioning and Algorithms.

I'm looking for Contributor, but also a simple feedback is good enough.
If you have 5 min to check my repo I'd be very grateful.

GitHub logo ZigRazor / CXXGraph

Header-Only C++ Library for Graph Representation and Algorithms

CXXGraph

codecov CodeFactor

GitHub license GitHub release

LGTM Alerts LGTM Grade

Generic badge Generic badge Generic badge

Generic badge Generic badge







Table of Contents

Introduction

CXXGraph is a small library, header only, that manages the Graph and it's algorithms in C++. In other words a "Comprehensive C++ Graph Library".

Algorithm Explanation

Dijkstra

Graph Dijkstras Shortest Path Algorithm(Dijkstra's Shortest Path) Dijkstra's Algorithm is used to find the shortest path from a source node to all other reachable nodes in the graph. The algorithm initially assumes all the nodes are unreachable from the given source node so we mark the distances of all nodes as infinity (infinity) from source node (INF / infinity denotes unable to reach).

Dial

Dial specialization of dijkstra’s algorithm.

When edge…

Thank you so much in advance.
Best regards