We are hiring content writers to work from home

Resources » Articles/Knowledge Sharing » Computer & Technology

# C Program for creating minimum spanning tree from Prim's algorithm

 Posted Date: 24-Mar-2008 Last Updated: 24-Mar-2008 Category: Computer & Technology Author: ashish singh Member Level: Gold Points: 5

/* Program for creating minimum spanning tree from Prim's algorithm */
#include

#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999

struct node
{
int predecessor;
int dist; /*Distance from predecessor */
int status;
};

struct edge
{
int u;
int v;
};

int n;

main()
{
int i,j;
int path[MAX];
int wt_tree,count;
struct edge tree[MAX];

create_graph();
display();

count = maketree(tree,&wt_tree);

printf("Weight of spanning tree is : %d\n", wt_tree);
printf("Edges to be included in spanning tree are : \n");
for(i=1;i<=count;i++)
{
printf("%d->",tree[i].u);
printf("%d\n",tree[i].v);
}
}/*End of main()*/

create_graph()
{
int i,max_edges,origin,destin,wt;

printf("Enter number of vertices : ");
scanf("%d",&n);
max_edges=n*(n-1)/2;

for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d(0 0 to quit) : ",i);
scanf("%d %d",&origin,&destin);
if((origin==0) && (destin==0))
break;
printf("Enter weight for this edge : ");
scanf("%d",&wt);
if( origin > n || destin > n || origin<=0 || destin<=0)
{
printf("Invalid edge!\n");
i--;
}
else
{
}
}/*End of for*/
if(i {
printf("Spanning tree is not possible\n");
exit(1);
}
}/*End of create_graph()*/

display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("\n");
}
}/*End of display()*/

int maketree(struct edge tree[MAX],int *weight)
{
struct node state[MAX];
int i,k,min,count,current,newdist;
int m;
int u1,v1;
*weight=0;
/*Make all nodes temporary*/
for(i=1;i<=n;i++)
{
state[i].predecessor=0;
state[i].dist = infinity;
state[i].status = TEMP;
}
/*Make first node permanent*/
state[1].predecessor=0;
state[1].dist = 0;
state[1].status = PERM;

/*Start from first node*/
current=1;
count=0; /*count represents number of nodes in tree */
while( all_perm(state) != TRUE ) /*Loop till all the nodes become
PERM*/
{
for(i=1;i<=n;i++)
{
if ( adj[current][i] > 0 && state[i].status == TEMP )
{
{
state[i].predecessor = current;
}
}
}/*End of for*/

/*Search for temporary node with minimum distance
and make it current node*/
min=infinity;
for(i=1;i<=n;i++)
{
if(state[i].status == TEMP && state[i].dist < min)
{
min = state[i].dist;
current=i;
}
}/*End of for*/

state[current].status=PERM;

/*Insert this edge(u1,v1) into the tree */
u1=state[current].predecessor;
v1=current;
count++;
tree[count].u=u1;
tree[count].v=v1;
/*Add wt on this edge to weight of tree */
}/*End of while*/
return (count);
}/*End of maketree()*/

/*This function returns TRUE if all nodes are permanent*/
int all_perm(struct node state[MAX] )
{
int i;
for(i=1;i<=n;i++)
if( state[i].status == TEMP )
return FALSE;
return TRUE;
}/*End of all_perm()*/

Did you like this resource? Share it with your friends and show your love!

Responses to "C Program for creating minimum spanning tree from Prim's algorithm"

No responses found. Be the first to respond...

Feedbacks

## Post Comment:

• Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
• No HTML formatting and links to other web sites are allowed.
• This is a strictly moderated site. Absolutely no spam allowed.
•  Name: Sign In to fill automatically. Email: (Will not be published, but required to validate comment) Type the numbers and letters shown on the left.

 Next Resource: C Program to find out the path matrix by powers of adjacency matrix Previous Resource: C Program for topological sorting Return to Resources Post New Resource Category: Computer & Technology

Post resources and earn money!

More Resources
 Popular Tags Tag posting guidelines Search Tags

### Subscribe to Email

• Get Jobs by Email
• Forum posts by Email
• Articles by Email
Active Members
Today
Last 7 Days
more...

### Online Members

Ank Arya
tajamul shafi
More...