/*Prim Algorithm C Program*/
#include<stdio.h>
#include<conio.h>
#define size 20
#define INFINITY 32767
void prim(int G[][size],int nodes)
{
int tree[size],i,j,k;
int min_dist,v1,v2,total=0;
for(i=0;i<nodes;i++)
{
tree[i]=0;
}
printf("\n\n The minimal spaning tree is:\n");
tree[0]=1;
for(k=1;k<=nodes-1;k++)
{
min_dist=INFINITY;
for(i=0;i<=nodes-1;i++)
{
for(j=0;j<=nodes-1;j++)
{
if(G[i][j]&&((tree[i]&&!tree[j])||(!tree[i]&&tree[j])))
{
if(G[i][j]<min_dist)
{
min_dist=G[i][j];
v1=i;
v2=j;
}
}
}
}
printf("\nEdge(%d,%d) and weight=%d",v1,v2,min_dist);
tree[v1]=tree[v2]=1;
total=total+min_dist;
}
printf("\n\n\tTotal path length is=%d",total);
}
void main()
{
int G[size][size] ,nodes;
int v1,v2,length,i,j,n;
clrscr();
printf("\n\tPrim's Algorithm\n");
printf("\nEnter the no. of nodes in Graph");
scanf("%d",&nodes);
printf("\nEnter the no. of edges in Graph");
scanf("%d",&n);
for(i=0;i<nodes;i++)
for(j=0;j<nodes;j++)
G[i][j]=0;
printf("Enter Edge and weight");
for(i=0;i<n;i++)
{
printf("\nEnter edge by v1&v2:");
printf("[read the graph from starting node[0]]");
scanf("%d%d",&v1,&v2);
printf("Enter the corresponding weight");
scanf("%d",&length);
G[v1][v2]=G[v2][v1]=length;
}
getch();
printf("\n\t");
clrscr();
prim(G,nodes);
getch();
}
#include<stdio.h>
#include<conio.h>
#define size 20
#define INFINITY 32767
void prim(int G[][size],int nodes)
{
int tree[size],i,j,k;
int min_dist,v1,v2,total=0;
for(i=0;i<nodes;i++)
{
tree[i]=0;
}
printf("\n\n The minimal spaning tree is:\n");
tree[0]=1;
for(k=1;k<=nodes-1;k++)
{
min_dist=INFINITY;
for(i=0;i<=nodes-1;i++)
{
for(j=0;j<=nodes-1;j++)
{
if(G[i][j]&&((tree[i]&&!tree[j])||(!tree[i]&&tree[j])))
{
if(G[i][j]<min_dist)
{
min_dist=G[i][j];
v1=i;
v2=j;
}
}
}
}
printf("\nEdge(%d,%d) and weight=%d",v1,v2,min_dist);
tree[v1]=tree[v2]=1;
total=total+min_dist;
}
printf("\n\n\tTotal path length is=%d",total);
}
void main()
{
int G[size][size] ,nodes;
int v1,v2,length,i,j,n;
clrscr();
printf("\n\tPrim's Algorithm\n");
printf("\nEnter the no. of nodes in Graph");
scanf("%d",&nodes);
printf("\nEnter the no. of edges in Graph");
scanf("%d",&n);
for(i=0;i<nodes;i++)
for(j=0;j<nodes;j++)
G[i][j]=0;
printf("Enter Edge and weight");
for(i=0;i<n;i++)
{
printf("\nEnter edge by v1&v2:");
printf("[read the graph from starting node[0]]");
scanf("%d%d",&v1,&v2);
printf("Enter the corresponding weight");
scanf("%d",&length);
G[v1][v2]=G[v2][v1]=length;
}
getch();
printf("\n\t");
clrscr();
prim(G,nodes);
getch();
}
No comments:
Post a Comment