Spanning Tree DS and DCN

This program is for implementing Spanning Tree. This is a part of Mumbai University MCA Colleges Data Communication and Networking And Data Structure MCA

#include<stdio.h>
#include<alloc.h>
#define MAX 20
struct edge
{
int u;
int v;
int weight;
struct edge *link;
}*front = NULL;

int father[MAX];
struct edge tree[MAX];
int n;
int wt_tree=0;
int count=0;
void make_tree();
void insert_tree(int i,int j,int wt);
void insert_pque(int i,int j,int wt);
void create_graph();
struct edge *del_pque();
void main()
{
int i;
clrscr();
create_graph();
make_tree();
printf("\nEdges 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("\n\nWeight of this minimum spanning tree is : %d\n", wt_tree);
getch();
}


void 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);
}
}

void make_tree()
{
struct edge *tmp;
int node1,node2,root_n1,root_n2;

while( count < n-1)
{
tmp=del_pque();
node1=tmp->u;
node2=tmp->v;

while( node1 > 0)
{
root_n1=node1;
node1=father[node1];
}


while( node2 >0 )
{
root_n2=node2;
node2=father[node2];
}

if(root_n1!=root_n2)
{
insert_tree(tmp->u,tmp->v,tmp->weight);
wt_tree=wt_tree+tmp->weight;
father[root_n2]=root_n1;
}
}
}

void insert_tree(int i,int j,int wt)
{
count++;
tree[count].u=i;
tree[count].v=j;
tree[count].weight=wt;
}

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;

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)
tmp->link = NULL;
}
}
struct edge *del_pque()
{
struct edge *tmp;
tmp = front;
front = front->link;
return tmp;
}

Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.