IMPLEMENTATION OF PRIM’S ALGORITHM
AIM :
To implement prim’s algorithm to find the minimum spanning tree of the given graph.
ALGORITHM :
1. Start the program
2. Read the number of vertices
3. Create a configuration table for given number of vertices
4. Initialize the configuration table
5. Get the adjacency matrix and cost matrix from the user
6. Start with the vertex v1
7. Alter the cost and path entries of the adjacent vertices of v1 accordingly and set the known flag of v1 true
8. Find the minimum cost among the unprocessed entries
9. Continue the procedure 7 and 8 till all the vertices are processed
10. Print the final table with minimum cost
11. Stop the program
SOURCE CODE :
#include
#include
struct table_entry;
typedef int vertex;
int cost_matrix[10][10];
int adj_matrix[10][10];
int numvertex;
void inittable();
void init_cost();
void getdata();
void prims();
int min_dist();
void display();
struct table_entry
{
char known;
int dist;
int path;
}*table;
void inittable()
{
int i;
for(i=1;i<=numvertex;i++)
{
table[i].known='F';
table[i].dist=99;
table[i].path=0;
}
table[1].dist=0;
table[1].path=1;
}
void init_cost()
{
int i,j;
for(i=1;i<=numvertex;i++)
{
for(j=1;j<=numvertex;j++)
{
cost_matrix[i][j]=0;
}
}
}
void getdata()
{
int i,j;
init_cost();
printf("enter the adjacency matrix :");
for(i=1;i<=numvertex;i++)
{
for(j=1;j<=numvertex;j++)
{
scanf("%d",&adj_matrix[i][j]);
}
}
printf("enter the cost matrix :");
for(i=1;i<=numvertex;i++)
{
for(j=1;j<=numvertex;j++)
{
if(adj_matrix[i][j]==1)
{
if(cost_matrix[i][j]==0)
{
printf("cost between v%d and v%d :",i,j);
scanf("%d",&cost_matrix[i][j]);
cost_matrix[j][i]=cost_matrix[i][j];
}
}
}
}
}
void prims()
{
int flag;
int i=1,j,d;
do
{
flag=0;
table[i].known='T';
for(j=1;j<=numvertex;j++)
{
if(adj_matrix[i][j]==1)
{
d=cost_matrix[i][j];
if((d'F'
))
{
table[j].dist=d;
table[j].path=i;
}
}
}
i=min_dist();
for(j=1;j<=numvertex;j++)
{
if(table[j].known=='F')
{
flag=1;
break;
}
}
}while(flag==1);
}
int min_dist()
{
int i,min=0,temp=99;
for(i=1;i<=numvertex;i++)
{
if(table[i].known=='F')
{
if(table[i].dist
{
temp=table[i].dist;
min=i;
}
}
}
return min;
}
void display()
{
int i,j,cost=0;
printf("\nvertex\tknown\tdistance\tpath\n");
printf("-------------------------------------------\n");
printf("\n");
printf("v1\t");
printf("T\t");
printf("0\t");
printf("0\t");
for(i=2;i<=numvertex;i++)
{
printf("\n");
printf("v%d\t",i);
printf("%c\t",table[i].known);
printf("%d\t",table[i].dist);
printf("v%d\t",table[i].path);
cost+=table[i].dist;
}
printf("\n\n minimum spanning cost is %d\n",cost);
}
main()
{
printf("enter the number of vertices :");
scanf("%d",&numvertex);
table=malloc(sizeof(struct table_entry) * numvertex);
inittable();
getdata();
prims();
display();
}
OUTPUT :
Enter the number of vertices : 4
Enter adjacency matrix:
1 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
Enter cost matrix:
V1 and v1:1
V1 and v2:1
V1 and v3:5
V1 and v4:4
V2 and v3:3
V3 and v4:2
vertex known dist path
-------------------------
V1 T 0 0
V2 T 1 A
V3 T 3 B
V4 T 2 C
Minimum Cost is:6
RESULT :
Thus the c program to implement prim’s algorithm to find the minimum spanning tree of the given graph is written and executed successfully.
Earn upto Rs. 9,000 pm checking Emails. Join now!
No comments:
Post a Comment