In this tutorial we shall read about Kruskal’s algorithm and Implementation

Kruskal’s algorithm is used to find MST in a graph. It is a greedy based algorithm.

Why do we call it as greedy? Because, as you will see further, we choose the shortest distance first without considering the fact what there might be more optimized path. Hence, pif we find another path with shortest value, we update the result with that value.

Below are the conditions for Kruskal’s algorithm to work:

- The graph should be connected
- Graph should be undirected.
- Graph should be weighted.

Let us first understand the working of the algorithm, then we shall solve with the help of an example.

The working of Kruskal’s algorithm is very simple and can be understood by 3 simple steps as given below:

Step 1: Sort all the edges according to their weights.

Step 2: a. Start from the edge with smallest weight and connect them together.

- Before connecting, check if it forms a cycle if it forms a cycle then reject the edge and go for the net smallest weighted edge.

Step 3: Check if all the vertices are connected. If they are not connected, then repeat step 2 till all the vertices are connected.

Once all the tree vertices are connected to an edge, we get MST.

Note: As you see in Prims algorithm that starts by choosing a root vertex, in Kruskal’s algorithm we start connecting 2 vertices by choosing least weighted edges.

Understanding Kruskal’s algorithm with the help of an example:

Consider the graph as below

Initial Configuration will be as below:

Connect the nodes “C” and “D” as their weight is minimum

Next connect nodes “D” and “E”, as they are next minimum

Next connect “C” and “B”, as they are next minimum

Next connect “B” and “A”

Next connect “A” and F”. Thus connecting all the nodes and forming a MST.

## Implementation Of Kruskal’s algorithm in C++

#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; #define MAX 1000 struct edge { int u, v, w; }; typedef struct edge E; int parents[MAX+5]; vector <E> graph; // Store the inputted graph (u, v, w). vector <E> selected_edges; // Store the edges which is selected for the MST from given graph. bool comp (const E& l, const E& r) { return l.w < r.w; } void make_set(int nodes) { for(int i=1; i<=nodes; i++) parents[i] = i; return; } int findParent( int r ) { if( r == parents[r] ) return r; return parents[r] = findParent( parents[r] ); } int Kruskal_MST (int nodes) { make_set(nodes); sort(graph.begin(), graph.end(), comp); int edgeCounter=0, totalCost=0; int len = graph.size(); for(int i=0; i<len; i++) { int parent_of_u = findParent( graph[i].u ); int parent_of_v = findParent( graph[i].v ); if( parent_of_u != parent_of_v ) { parents[ parent_of_u ] = parent_of_v; totalCost += graph[i].w; selected_edges.push_back( graph[i] ); edgeCounter++; if( edgeCounter == nodes-1 ) break; } } return totalCost; } int main() { E getEdge; int nodes, edges; cout<<"How many nodes: "<<endl; cin >> nodes; cout<<"How many edges: "<<endl; cin >> edges; cout<<"Enter 2 nodes & their costs (u v & w): \n"; for(int i=1; i<=edges; i++) { int u, v, w; cout<<"Edge "<< i<<endl; cin >> u >> v >> w; getEdge.u = u; getEdge.v = v; getEdge.w = w; graph.push_back(getEdge); } int totalCost = Kruskal_MST(nodes); cout<<"\n\nSelected Edges and their costs: \n"; for(int i=0; i<selected_edges.size(); i++) { cout<<"Edge "<< i+1 <<":"<< selected_edges[i].u<< " -> " << selected_edges[i].v<< ": cost "<< selected_edges[i].w <<endl; } cout<<"\nTotal Costs: "<< totalCost<<endl; getchar(); return 0; }

Time complexity of Kruskal’s algorithm is O(logV)

Kruskal’s algorithm should be used in typical situations (sparse graphs) because it uses simpler data structures.

### Further Reading: