My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
C Program for creating a minimum spanning tree from Kruskal'salgorithm
Posted Date: 24 Mar 2008 Resource Type: Articles/Knowledge Sharing Category: Computer & Technology
|
Posted By: ashish singh Member Level: Diamond
Rating:  Points: 5
|
|
|
/* Program for creating a minimum spanning tree from Kruskal's
algorithm */
#include
#define MAX 20
struct edge
{
int u;
int v;
int weight;
struct edge *link;
}*front = NULL;
int father[MAX]; /*Holds father of each node */
struct edge tree[MAX]; /* Will contain the edges of spanning tree */
int n; /*Denotes total number of nodes in the graph */
int wt_tree=0; /*Weight of the spanning tree */
int count=0; /* Denotes number of edges included in the tree */
/* Functions */
void make_tree();
void insert_tree(int i,int j,int wt);
void insert_pque(int i,int j,int wt);
struct edge *del_pque();
main()
{
int i;
create_graph();
make_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);
}
printf("Weight of this minimum spanning tree is : %d\n", wt_tree);
}/*End of main()*/
create_graph()
{
int i,wt,max_edges,origin,destin;
printf("Enter number of nodes : ");
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
insert_pque(origin,destin,wt);
}/*End of for*/
if(i {
printf("Spanning tree is not possible\n");
exit(1);
}
}/*End of create_graph()*/
void make_tree()
{
struct edge *tmp;
int node1,node2,root_n1,root_n2;
while( count < n-1) /*Loop till n-1 edges included in the tree*/
{
tmp=del_pque();
node1=tmp->u;
node2=tmp->v;
printf("n1=%d ",node1);
printf("n2=%d ",node2);
while( node1 > 0)
{
root_n1=node1;
node1=father[node1];
}
while( node2 >0 )
{
root_n2=node2;
node2=father[node2];
}
printf("rootn1=%d ",root_n1);
printf("rootn2=%d\n",root_n2);
if(root_n1!=root_n2)
{
insert_tree(tmp->u,tmp->v,tmp->weight);
wt_tree=wt_tree+tmp->weight;
father[root_n2]=root_n1;
}
}/*End of while*/
}/*End of make_tree()*/
/*Inserting an edge in the tree */
void insert_tree(int i,int j,int wt)
{
printf("This edge inserted in the spanning tree\n");
count++;
tree[count].u=i;
tree[count].v=j;
tree[count].weight=wt;
}/*End of insert_tree()*/
/*Inserting edges in the priority queue */
void insert_pque(int i,int j,int wt)
{
struct edge *tmp,*q;
tmp = (struct edge *)malloc(sizeof(struct edge));
tmp->u=i;
tmp->v=j;
tmp->weight = wt;
/*Queue is empty or edge to be added has weight less than first edge*/
if( front == NULL || tmp->weight < front->weight )
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while( q->link != NULL && q->link->weight <= tmp->weight )
q=q->link;
tmp->link = q->link;
q->link = tmp;
if(q->link == NULL) /*Edge to be added at the end*/
tmp->link = NULL;
}/*End of else*/
}/*End of insert_pque()*/
/*Deleting an edge from the priority queue*/
struct edge *del_pque()
{
struct edge *tmp;
tmp = front;
printf("Edge processed is %d->%d %d\n",tmp->u,tmp->v,tmp->weight);
front = front->link;
return tmp;
}/*End of del_pque()*/
|
Responses
|
No responses found. Be the first to respond and make money from revenue sharing program.
|
|
Watch TV Channels
Watch Asianet TV onlineKairali TV in InternetSurya TV onlineAmritha TV Channel
|