kruskal algorithm explanation code example

Example 1: 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);
}

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