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
Top comments (1)
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.
ZigRazor / CXXGraph
Header-Only C++ Library for Graph Representation and Algorithms
CXXGraph
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