Prim's Minimum Spanning Tree
AIM:
To implement Prim’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 Prim's Algorithm.
Program:
#include<stdio.h>
#include<stdlib.h>
struct Graph
{
int v;
int e;
int adjMat[20][20];
};
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");
}
int minKey(struct Graph* g,int key[100],int mstSet[100])
{
int i,minIndex,Min=INT_MAX;
for(i=0;i<g->v;i++)
{
if(mstSet[i]==0&&key[i]<Min)
{
Min=key[i];
minIndex=i;
}
}
return minIndex;
}
void primsMST(struct Graph* g)
{
int i,TC,dest,src,parent[g->v],key[g->v], mstSet[g->v];
for(i=0;i<g->v;i++)
{
key[i]=INT_MAX;
mstSet[i]=0;
}
key[0]=0;
parent[0]=-1;
for(i=0;i<g->v-1;i++)
{
src=minKey(g,key,mstSet);
mstSet[src]=1;
for(dest=0;dest<g->v;dest++)
{
if(g->adjMat[src][dest]!=0&&mstSet[dest]==0&&g->adjMat[src][dest]<key[dest])
{
parent[dest]=src;
key[dest]=g->adjMat[src][dest];
}
}
}
printf("\n Minimum Spanning Tree: \n");
struct Graph* MST=createGraph(g->v,g->v-1);
TC=0;
for(i=1;i<g->v;i++)
{
MST->adjMat[parent[i]][i]=g->adjMat[i][parent[i]];
MST->adjMat[i][parent[i]]=g->adjMat[i][parent[i]];
TC=TC+g->adjMat[i][parent[i]];
}
displayGraph(MST);
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);
primsMST(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:
Adjacency Matrix Representation :
0 2 0 6 0
2 0 3 0 5
0 3 0 0 0
6 0 0 0 0
0 5 0 0 0
Total Cost of MST = 16
--------------------------------
Process exited after 1.792 seconds with return value 0
Press any key to continue . . .
No comments:
Post a Comment