/**********************************************************************/
/*Program : To show Prims Algorithm*/
/*Purpose : Program to compute mimimum spanning tree of graph*/
/*Date : 08-01-2005*/
/*Time : 12:20*/
/**********************************************************************/
#include
#include
#include
#define INF INT_MAX
#define v 10
#define FALSE 0
#define TRUE 1
typedef struct tree_tag
{
int nodes;
int path[v];
int tree[v][v];
int chosen[v];
int adj_mat[v][v];
}tree;
/**************Function Declaration Begin**********/
void prims(tree *);
/**************Function Declaration End**********/
void main()
{
tree T;
clrscr();
printf(“\n\t\t Prims Minimum Spanning Tree Algorithm:”);
printf(“\n\t\t Program obtains the minimum spanning tree of a undirected graph \n”);
printf(“\n\t\t Enter number of edges required in the graph:\n”);
scanf(“%d”,&T.nodes);
prims(&T);
getch();
}
/********** prims technique for minimum spanning tree **********/
/********** Function Definition begins **********/
void prims(tree *T)
{
int i,j,k=0,x,y,min,len;
for(i=0;i
{
for(j=0;j
{
printf(“\n\t\t Enter weight for visiting edge %d to edge %d:”,i,j);
scanf(“%d”,&T->adj_mat[i][j]);
}
}
printf(“\n\t\t Cost adjacency matrix of graph is:\n”);
for(i=0;i
{
for(j=0;j
{
printf(“%3d\t”,T->adj_mat[i][j]);
}
printf(“\n”);
}
for(i=0;i
{
T->chosen[i] = FALSE;
}
for(i=0;i
{
for(j=0;j
{
T->tree[i][j]=0;
}
}
T->chosen[0]=TRUE;
T->path[0]=0;
len = 1;
while(len<=T->nodes)
{
min = INF;
for(i=0;i
{
if(T->chosen[i]==TRUE)
{
for(j=0;j
{
if(T->chosen[j]==FALSE)
{
if(T->adj_mat[i][j]
{
min = T->adj_mat[i][j];
y = i;
x = j;
}
}
}
}
}
T->tree[y][x] = 1;
T->chosen[x] = TRUE;
T->path[++k] = x;
len++;
}
printf(“\n\t\t Minimum Spanning Tree Adjacency matrix :\n”);
for(i=0;i
{
for(j=0;j
{
printf(“%3d\t”,T->tree[i][j]);
}
printf(“\n”);
}
printf(“\n\t\t The minimum spanning tree path of the prim’s algorithm is:”);
for(i=0;i
printf(“%d\t”,T->path[i]);
printf(“\n”);
}
/********** Function Definition ends **********/
No comments:
Post a Comment