PROGRAM:
#include
#include
#define size 20
#define INFINITY 32767
void prim(int g[][10],int nodes)
{
int tree[size],i,j,k;
int min_dist,v1,v2,total=0;
for(i=0;i
tree[i]=0;
printf("\nthe minimum spanning tree is");
tree[0]=1;
for(k=1;k<=nodes-1;k++)
{
min_dist=INFINITY;
for(i=0;i
{
for(j=0;j
{
if(g[i][j]&&((tree[i]&&!tree[j])||(!tree[i]&&tree[j])))
{
if(g[i][j]
{
min_dist=g[i][j];
v1=i;
v2=j;
}
}
}
}
printf("\n edge(%d%d)and weight=%d",v1,v2,min_dist);
tree[v1]=tree[v2]=1;
total=total+min_dist;
}
printf("\ntotal path length is =%d",total);
}
void main()
{
int g[size][size],nodes;
int v1,v2,length,i,j,n;
clrscr();
printf("\nprims algorithm");
printf("\nenter the no of nodes");
scanf("%d",&nodes);
printf("\nenter the no of edges");
scanf("%d",&n);
for(i=0;i
for(j=0;j
g[i][j]=0;
printf("\nenter the edges and weight ");
for(i=0;i
{
printf("\nenter the edge by v1&v2");
printf("\nread the graph from starting node");
scanf("%d%d",&v1,&v2);
printf("\nenter the corresponding weight");
scanf("%d",&length);
g[v1][v2]=g[v2][v1]=length;
}
getch();
printf("\n\t");
clrscr();
prim(g,nodes);
getch();
}
OUTPUT:
prims algorithm
enter the no of nodes4
enter the no of edges6
enter the edges and weight
enter the edge by v1&v2
read the graph from starting node0 1
enter the corresponding weight1
enter the edge by v1&v2
read the graph from starting node0 3
enter the corresponding weight3
enter the edge by v1&v2
read the graph from starting node0 2
enter the corresponding weight3
enter the edge by v1&v2
read the graph from starting node1 2
enter the corresponding weight4
enter the edge by v1&v2
read the graph from starting node2 3
enter the corresponding weight7
enter the edge by v1&v2
read the graph from starting node1 3
enter the corresponding weight5
the minimum spanning tree is
edge(01)and weight=1
edge(20)and weight=3
edge(03)and weight=3
total path length is =7
CIET college Programs,LAB Programs for Engineering Students,DAA LAB Programs,DSA LAB Programs,Remoboys,karthik,Remokn,Student3k,programs source code,Design Analysis And Algorithms LAB Programs,Data Structures and Algorithms LAB Programs,LAB Codings,Coimbatore Institute of Engineering and Technology ( CIET )
