code implementation of krushkals algorithm

Solutions on MaxInterview for code implementation of krushkals algorithm by the best coders in the world

showing results for - "code implementation of krushkals algorithm"
Alexa
04 Apr 2017
1a,b,u,v,n,ne=1;
2    int min,mincost=0,cost[9][9],parent[9];
3    int find(int);
4    int uni(int,int);
5    void main()
6    {    #include <stdio.h>
7    #include <conio.h>
8    #include <stdlib.h>
9    int i,j,k,
10    	printf("\n\tImplementation of Kruskal's Algorithm\n");
11    	printf("\nEnter the no. of vertices:");
12    	scanf("%d",&n);
13    	printf("\nEnter the cost adjacency matrix:\n");
14    	for(i=1;i<=n;i++)
15    	{
16    	for(j=1;j<=n;j++)
17    	{
18    	scanf("%d",&cost[i][j]);
19    	if(cost[i][j]==0)
20    	cost[i][j]=999;
21    	}
22    	}
23    	printf("The edges of Minimum Cost Spanning Tree are\n");
24    	while(ne < n)
25    	{
26    	for(i=1,min=999;i<=n;i++)
27    	{
28    	for(j=1;j <= n;j++)
29    	{
30    	if(cost[i][j] < min)
31    	{
32    	min=cost[i][j];
33    	a=u=i;
34    	b=v=j;
35    	}
36    	}
37    	}
38    	u=find(u);
39    	v=find(v);
40    	if(uni(u,v))
41    	{
42    	printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
43    	mincost +=min;
44    	}
45    	cost[a][b]=cost[b][a]=999;
46    	}
47    	printf("\n\tMinimum cost = %d\n",mincost);
48    	getch();
49    }
50    int find(int i)
51    {
52    	while(parent[i])
53    	i=parent[i];
54    	return i;
55    }
56    int uni(int i,int j)
57    {
58    	if(i!=j)
59    	{
60    	parent[j]=i;
61    	return 1;
62    	}
63    	return 0;
64    }
65