Answers for "Kruskal's algorithm in C"

Kruskal's algorithm in C

#include<stdio.h>#include<conio.h>#include<stdlib.h>int i,j,k,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(){	clrscr();	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;}

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