C++ code implementation of krushkals algorithm code example

Example 1: kruskal's algorithm c++ hackerearth

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];

void initialize()
{
    for(int i = 0;i < MAX;++i)
        id[i] = i;
}

int root(int x)
{
    while(id[x] != x)
    {
        id[x] = id[id[x]];
        x = id[x];
    }
    return x;
}

void union1(int x, int y)
{
    int p = root(x);
    int q = root(y);
    id[p] = id[q];
}

long long kruskal(pair<long long, pair<int, int> > p[])
{
    int x, y;
    long long cost, minimumCost = 0;
    for(int i = 0;i < edges;++i)
    {
        // Selecting edges one by one in increasing order from the beginning
        x = p[i].second.first;
        y = p[i].second.second;
        cost = p[i].first;
        // Check if the selected edge is creating a cycle or not
        if(root(x) != root(y))
        {
            minimumCost += cost;
            union1(x, y);
        }    
    }
    return minimumCost;
}

int main()
{
    int x, y;
    long long weight, cost, minimumCost;
    initialize();
    cin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        cin >> x >> y >> weight;
        p[i] = make_pair(weight, make_pair(x, y));
    }
    // Sort the edges in the ascending order
    sort(p, p + edges);
    minimumCost = kruskal(p);
    cout << minimumCost << endl;
    return 0;
}

Example 2: code implementation of krushkals algorithm

a,b,u,v,n,ne=1;
    int min,mincost=0,cost[9][9],parent[9];
    int find(int);
    int uni(int,int);
    void main()
    {    #include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>
    int i,j,k,
    	printf("\n\tImplementation of Kruskal's Algorithm\n");
    	printf("\nEnter the no. of vertices:");
    	scanf("%d",&n);
    	printf("\nEnter the cost adjacency matrix:\n");
    	for(i=1;i<=n;i++)
    	{
    	for(j=1;j<=n;j++)
    	{
    	scanf("%d",&cost[i][j]);
    	if(cost[i][j]==0)
    	cost[i][j]=999;
    	}
    	}
    	printf("The edges of Minimum Cost Spanning Tree are\n");
    	while(ne < n)
    	{
    	for(i=1,min=999;i<=n;i++)
    	{
    	for(j=1;j <= n;j++)
    	{
    	if(cost[i][j] < min)
    	{
    	min=cost[i][j];
    	a=u=i;
    	b=v=j;
    	}
    	}
    	}
    	u=find(u);
    	v=find(v);
    	if(uni(u,v))
    	{
    	printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
    	mincost +=min;
    	}
    	cost[a][b]=cost[b][a]=999;
    	}
    	printf("\n\tMinimum cost = %d\n",mincost);
    	getch();
    }
    int find(int i)
    {
    	while(parent[i])
    	i=parent[i];
    	return i;
    }
    int uni(int i,int j)
    {
    	if(i!=j)
    	{
    	parent[j]=i;
    	return 1;
    	}
    	return 0;
    }

Example 3: Kruskals in c++

#include<bits/stdc++.h> 
using namespace std; 
  

typedef  pair<int, int> iPair; 
  

struct Graph 
{ 
    int V, E; 
    vector< pair<int, iPair> > edges; 
  
   
    Graph(int V, int E) 
    { 
        this->V = V; 
        this->E = E; 
    } 
  
    void addEdge(int u, int v, int w) 
    { 
        edges.push_back({w, {u, v}}); 
    } 
 
  
    int kruskalMST(); 
}; 
  

struct DisjointSets 
{ 
    int *parent, *rnk; 
    int n; 
  

    DisjointSets(int n) 
    { 
    
        this->n = n; 
        parent = new int[n+1]; 
        rnk = new int[n+1]; 
  
    
        for (int i = 0; i <= n; i++) 
        { 
            rnk[i] = 0; 
  
      
            parent[i] = i; 
        } 
    } 
 
    int find(int u) 
    { 
     
        if (u != parent[u]) 
            parent[u] = find(parent[u]); 
        return parent[u]; 
    } 
  
 
    void merge(int x, int y) 
    { 
        x = find(x), y = find(y); 
  
       
        if (rnk[x] > rnk[y]) 
            parent[y] = x; 
        else 
            parent[x] = y; 
  
        if (rnk[x] == rnk[y]) 
            rnk[y]++; 
    } 
}; 
  

  
int Graph::kruskalMST() 
{ 
    int mst_wt = 0; 
  
    sort(edges.begin(), edges.end()); 
  

    DisjointSets ds(V); 
  

    vector< pair<int, iPair> >::iterator it; 
    for (it=edges.begin(); it!=edges.end(); it++) 
    { 
        int u = it->second.first; 
        int v = it->second.second; 
  
        int set_u = ds.find(u); 
        int set_v = ds.find(v); 
  
      
        if (set_u != set_v) 
        { 
          
            cout << u << " - " << v << endl; 
  
      
            mst_wt += it->first; 
  
        
            ds.merge(set_u, set_v); 
        } 
    } 
  
    return mst_wt; 
} 
  

int main() 
{ 
   
    int V = 9, E = 14; 
    Graph g(V, E); 
  
   
    g.addEdge(0, 1, 4); 
    g.addEdge(0, 7, 8); 
    g.addEdge(1, 2, 8); 
    g.addEdge(1, 7, 11); 
    g.addEdge(2, 3, 7); 
    g.addEdge(2, 8, 2); 
    g.addEdge(2, 5, 4); 
    g.addEdge(3, 4, 9); 
    g.addEdge(3, 5, 14); 
    g.addEdge(4, 5, 10); 
    g.addEdge(5, 6, 2); 
    g.addEdge(6, 7, 1); 
    g.addEdge(6, 8, 6); 
    g.addEdge(7, 8, 7); 
  
    cout << "Edges of MST are \n"; 
    int mst_wt = g.kruskalMST(); 
  
    cout << "\nWeight of MST is " << mst_wt; 
  
    return 0; 
}