Kruskal's Minimum Spanning Tree
AIM:
To implement Kruskal’s algorithm to generate a min-cost spanning tree
Description:
In this program, an un-directed graph is created, and then Minimum Spanning Tree(MST) is generated using Kruskal's Algorithm.
Program:
#include<stdio.h>
#include<stdlib.h>
struct Graph
{
int v;
int e;
int adjMat[20][20];
};
struct SDW
{
int src;
int dest;
int weight;
};
struct Graph* createGraph(int v,int e)
{
int i,j,src,dest,weight;
struct Graph* g=(struct Graph*)malloc(sizeof(struct Graph));
g->v=v;
g->e=e;
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
{
g->adjMat[i][j]=0;
}
}
return g;
}
void insertEdges(struct Graph* g)
{
int i,src,dest,weight;
printf("\n Enter Source and Destination Vertices for each edge: ");
i=0;
while(i<g->e)
{
printf("\n Edge %d : ",i+1);
printf("\n Source Vertex : ");
scanf("%d",&src);
printf(" Destination Vertex : ");
scanf("%d",&dest);
if(src>g->v||dest>g->v)
{
printf("\n Vertex does not exists! Enter Again! \n");
}
else if(g->adjMat[src][dest]>0)
{
printf("\n Edge already exists! Enter Again! \n");
}
else
{
printf(" Enter Weight : ");
scanf("%d",&weight);
g->adjMat[src][dest]=weight;
g->adjMat[dest][src]=weight;
i++;
}
}
}
void displayGraph(struct Graph* g)
{
int i,j;
printf("\n Adjacency Matrix Representation : \n");
for(i=0;i<g->v;i++)
{
printf("\n");
for(j=0;j<g->v;j++)
{
printf(" %d",g->adjMat[i][j]);
}
}
printf("\n");
}
void krushkalsMST(struct Graph* g)
{
int i,j,k,TC,temp1,temp2,temp3;
struct SDW List[g->e],MST[g->v-1];
k=0;
for(i=0;i<g->v;i++)
{
for(j=0;j<i;j++)
{
if(g->adjMat[i][j]!=0)
{
List[k].dest=i;
List[k].src=j;
List[k].weight=g->adjMat[i][j];
k++;
}
}
}
for(i=0;i<k-1;i++)
{
for(j=0;j<k-i-1;j++)
{
if(List[j].weight>List[j+1].weight)
{
temp1=List[j].dest;
temp2=List[j].src;
temp3=List[j].weight;
List[j].dest=List[j+1].dest;
List[j].src=List[j+1].src;
List[j].weight=List[j+1].weight;
List[j+1].dest=temp1;
List[j+1].src=temp2;
List[j+1].weight=temp3;
}
}
}
TC=k=0;
for(i=0;i<g->e;i++)
{
temp1=temp2=0;
for(j=0;j<k;j++)
{
if(MST[j].src==List[i].src)
{
temp1++;
}
if(MST[j].src==List[i].dest)
{
temp2++;
}
if(MST[j].dest==List[i].src)
{
temp1++;
}
if(MST[j].dest==List[i].dest)
{
temp2++;
}
}
if(temp1==0||temp2==0)
{
MST[k].src=List[i].src;
MST[k].dest=List[i].dest;
MST[k].weight=List[i].weight;
TC=TC+MST[k].weight;
k++;
}
if(k>=g->v-1)
{
break;
}
}
printf("\n Minimum Spanning Tree: \n");
printf("\n Edge \t Weight \n");
for(i=0;i<g->v-1;i++)
{
printf(" %d-%d \t %d \n",MST[i].src,MST[i].dest,MST[i].weight);
}
printf("\n Total Cost of MST = %d ",TC);
}
int main()
{
int v,e;
printf("\n Enter No. of Vertices: ");
scanf("%d",&v);
printf("\n Enter No. of Edges: ");
scanf("%d",&e);
struct Graph* g=createGraph(v,e);
insertEdges(g);
displayGraph(g);
krushkalsMST(g);
return 0;
}
OUTPUT
Enter No. of Vertices: 5
Enter No. of Edges: 7
Enter Source and Destination Vertices for each edge:
Edge 1 :
Source Vertex : 0
Destination Vertex : 1
Enter Weight : 2
Edge 2 :
Source Vertex : 0
Destination Vertex : 3
Enter Weight : 6
Edge 3 :
Source Vertex : 1
Destination Vertex : 2
Enter Weight : 3
Edge 4 :
Source Vertex : 1
Destination Vertex : 3
Enter Weight : 8
Edge 5 :
Source Vertex : 1
Destination Vertex : 4
Enter Weight : 5
Edge 6 :
Source Vertex : 2
Destination Vertex : 4
Enter Weight : 7
Edge 7 :
Source Vertex : 3
Destination Vertex : 4
Enter Weight : 9
Adjacency Matrix Representation :
0 2 0 6 0
2 0 3 8 5
0 3 0 0 7
6 8 0 0 9
0 5 7 9 0
Minimum Spanning Tree:
Edge Weight
0-1 2
1-2 3
1-4 5
0-3 6
Total Cost of MST = 16
--------------------------------
Process exited after 2.91 seconds with return value 0
Press any key to continue . . .
No comments:
Post a Comment