Prims Program in C language

//  Prims Program in C language


#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define size 8

int cost[size][size]={0},n=0;

/*

The get_mat function-for creating the adjacency matrix

Input :none

Output:none

Parameter Passing Method :none

Called By : main()

Calls : none

*/


void get_mat()

{

int i,j,v1,v2,wt;

for(i=0;i<=size;i++)

   for(j=0;j<=size;j++)

  cost[i][j]=1000;

printf("enter no of vertices: ");

scanf("%d",&n);

do{

   printf("\nenter edge & cores wt (v1<->v2,wt): ");

   scanf("%d%d%d",&v1,&v2,&wt);

   cost[v1][v2]=cost[v2][v1]=wt;

   printf("\ncontinue(y/n): ");

   fflush(stdin);

   }while(getche()=='y');

}

 /*

The main function

Input :none

Output:none

Called By : O.S.

Calls :get_mat()

*/

void main()

{

 int t[size]={0},wt[size]={0},min,p,sum=0,temp,i,j,k=0,l=0,m=0;

  get_mat();

 t[1]=1;

 printf("\n\ntree includes following edges:");

 for(p=1;p<=n-1;p++)

 {

  temp=1000;       /sort of infinity distance/

  for(i=1;i<=n;i++)

  {

   if(t[i]==1)

   {

    min=1000;

 for(j=1;j<=n;j++)

 {

  if(cost[i][j]<min&&t[j]==0)

  {

min=cost[i][j];       /checking the minimum cost/

k=j;

   }   /* End Of if*/

  }   /End Of for/

  if(min<temp)

  {

   temp=min;

   l=k;m=i;

  } /end of if/

  }

  }

  wt[p]=cost[m][l];     /storing the minimum wt from the graph/

  sum=sum+wt[p];    /finding total cost of min.spanning tree/

  printf("\n\nedge: %d<-->%d  wt: %d",m,l,cost[m][l]);

   t[l]=t[m]=1;

   }

  printf("\n\nwt of minimum spanning tree: %d",sum);

 getch();

}

/*End Of Program/ 

Post a Comment

Previous Post Next Post