Answers for "kruskal's algorithm"

kruskal algorithm time complexity

Time complexity:- O(ElogV)

kruskal's algorithm

#include<bits/stdc++.h>

using namespace std;

int  main()
{
	int n = 9;
	
	int mat[9][9] = {
	{100,4,100,100,100,100,100,8,100},
	{4,100,8,100,100,100,100,100,100},
	{100,8,100,7,100,4,100,100,2},
	{100,100,7,100,9,14,100,100,100},
	{100,100,100,9,100,10,100,100,100},
	{100,100,4,14,10,100,2,100,100},
	{100,100,100,100,100,2,100,1,6},
	{8,100,100,100,100,100,1,100,7},
	{100,100,2,100,100,100,6,7,100}};
	
	int parent[n];
	
	int edges[100][3];
	int count = 0;
	
	for(int i=0;i<n;i++)
		for(int j=i;j<n;j++)
		{
			if(mat[i][j] != 100)
			{
				edges[count][0] = i;
				edges[count][1] = j;
				edges[count++][2] = mat[i][j];	
			}		
		}

	for(int i=0;i<count-1;i++)
		for(int j=0;j<count-i-1;j++)
			if(edges[j][2] > edges[j+1][2])
				{
					int t1=edges[j][0], t2=edges[j][1], t3=edges[j][2];
					
					edges[j][0] = edges[j+1][0];
					edges[j][1] = edges[j+1][1];
					edges[j][2] = edges[j+1][2];
					
					edges[j+1][0] = t1;
					edges[j+1][1] = t2;
					edges[j+1][2] = t3;
				}
				
	int mst[n-1][2];
	int mstVal = 0;
	int l = 0;
	
	cout<<endl;
	
	for(int i=0;i<n;i++)
		parent[i] = -1;
	cout<<endl;
				
	for(int i=0;i<count;i++)
	{
		if((parent[edges[i][0]] == -1 && parent[edges[i][1]] == -1))
		{
			parent[edges[i][0]] = edges[i][0];
			parent[edges[i][1]] = edges[i][0];
			
			mst[l][0] = edges[i][0];
			mst[l++][1] = edges[i][1];
			
			mstVal += edges[i][2];
		}
		
		else if((parent[edges[i][0]] == -1 && parent[edges[i][1]] != -1))
		{
			parent[edges[i][0]] = parent[edges[i][1]];
			
			mst[l][0] = edges[i][1];
			mst[l++][1] = edges[i][0];
			
			mstVal += edges[i][2];
		}
		
		else if((parent[edges[i][0]] != -1 && parent[edges[i][1]] == -1))
		{
			parent[edges[i][1]] = parent[edges[i][0]];
			
			mst[l][0] = edges[i][0];
			mst[l++][1] = edges[i][1];
			
			mstVal += edges[i][2];
		}
		
		else if(parent[edges[i][0]] != -1 && parent[edges[i][1]] != -1 && parent[edges[i][0]] != parent[edges[i][1]])
		{
			int p = parent[edges[i][1]];
			for(int j=0;j<n;j++)
				if(parent[j] == p)
					parent[j] = parent[edges[i][0]];
			
			mst[l][0] = edges[i][0];
			mst[l++][1] = edges[i][1];
			
			mstVal += edges[i][2];
		}
	}
	
	for(int i=0;i<l;i++)
		cout<<mst[i][0]<<" -> "<<mst[i][1]<<endl;
	
	cout<<endl;
	cout<<mstVal<<endl;
		
	return(0);
}

kruskal's algorithm

//MINIMUM SPANNING TREE USING KRUSHKAL ALGORITHM
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int u,v,wt;
    node(int first,int second, int weight)
    {
        u=first;
        v=second;
        wt=weight;
    }
};
bool cmp(node a,node b)
{
    return (a.wt<b.wt);
}
int findpar(int u,vector<int>&parent)
{
    if(u==parent[u])
    {
        return u;
    }
    return findpar(parent[u],parent);
}
void unionoperation(int u,int v,vector<int>&parent,vector<int>&rank)
{
    u=findpar(u,parent);
    v=findpar(v,parent);
    if(rank[u]<rank[v])
    {
        parent[u]=v;
    }
    else if(rank[v]<rank[u])
    {
        parent[v]=u;
    }
    else
    {
        parent[v]=u;
        rank[u]++;
    }
}
int main()
{
    int vertex,ed;
    cout<<"Enter the number of vertex and edges:"<<endl;
    cin>>vertex>>ed;
    vector<node>edges;
     cout<<"enter the links and weight:"<<endl;
    for(int i=0;i<ed;i++)
    {
        int u,v,wt;
        cin>>u>>v>>wt;
        edges.push_back(node(u,v,wt));
    }
    sort(edges.begin(),edges.end(),cmp);
    vector<int>parent(vertex);
    for(int i=0;i<vertex;i++)
    {
        parent[i]=i;
    }
    vector<int>rank(vertex,0);
    int cost=0;
    vector<pair<int,int>>mst;
    for(auto i:edges)
    {
        if(findpar(i.u,parent)!=findpar(i.v,parent))
        {
            cost+=i.wt;
            mst.push_back(make_pair(i.u,i.v));
            unionoperation(i.u,i.v,parent,rank);
        }
    }
    cout<<cost<<endl;
    for(auto i:mst)
    {
        cout<<i.first<<"-"<<i.second<<endl;
    }
    return 0;
}

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; 
}