DEV Community: Nokha Debbarma

Implement Kruskal's Algorithm in C++

Nokha Debbarma — Mon, 26 Apr 2021 15:36:38 +0000

Good to have basic idea of:

What is the Minimum spanning tree in a graph? https://www.programiz.com/dsa/spanning-tree-and-minimum-spanning-tree
Detect a cycle in the graph by Union find Path compression algorithm https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/
C++ ( vector,pairs, sort STL with comparator, classes )

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;

 }

output:

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

CSS Position: relative

Nokha Debbarma — Tue, 16 Feb 2021 09:00:57 +0000

Initially, when I was learning CSS as a complete beginner I faced a lot with CSS position property. However, after learning and playing around I have learned how CSS position property works.
This post of especially for beginners who new to CSS and are confused with CSS position property.

HTML element for Demo:

CSS code:

In the code, you can see that no CSS position property is set.
So, here is the layout of the above code:

Position: relative;

Aughh.... tell me what the heck Position: relative is?
when you set CSS position: relative to HTML element the position is actually relative to itself. Still confused okay.

Let's set the child element to property: relative;
However, you will not see any changes to the child element position because by default it wouldn't until you set any of these property i.e top, left, right, or bottom.
For example, let's just set the values for top and left.
top: 50px;
left: 50px;

In the above image, you can see that position of the child block element has changed.
As we have set left:50px, what it really means is that the element will move 50px in the left to right direction with respect to(from its) original position.
And we have also set top:50px, element will shift 50px in the top to bottom direction with respect to(from its) original position.

For the above image we have set
bottom:50px;
right:50px;

Okay now it's your turn to play around with bottom,right,top,left learn how element moves.
Position: relative; doesn't care about other elements it changes its position relative to its original position.
That's it!

Learning HTML and CSS...

Nokha Debbarma — Tue, 29 Dec 2020 17:47:55 +0000

I began my journey of learning HTML thereafter CSS about a week ago. Today, I am glad to say that I have finished learning the basics of HTML and CSS. Now I'm learning to build a simple basic webpage and form with only HTML & CSS to get my hands dirty. The profile card image that you see on the cover page of this post is built by me. Pretty basic.
Yes, there's a lot to learn more and practice consistently to get really good at it. I'm excited to take up further steps to learn and develop more skills.

But wait, I am confused about whether I should learn Javascript next or should I learn Sass and bootstrap next?

Please, suggest to me what should I learn next.
Thank You.

Taking a step to be a web Developer.

Nokha Debbarma — Sat, 26 Dec 2020 14:45:57 +0000

Hello World,
I am very excited to take a step forward to become a proficient web developer. Currently, I am learning HTML & CSS.
I hope this journey will be awesome.