Data Communication network programs (DCN)
Data Communication network(DCN) Program to generate sink tree for given network.
Write a program to generate sink tree for given network.
Program Code:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 8
int cost[size][size]={0},n=0;
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');
}
void main()
{
int t[size]={0},wt[size]={0},min,p,sum=0,temp,i,j,k=0,l=0,m=0;
clrscr();
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();
}
Output:
enter no of vertices: 6
enter edge & cores wt (v1<->v2,wt): 1 2 6
continue(y/n): y
enter edge & cores wt (v1<->v2,wt): 1 3 3
continue(y/n): y
enter edge & cores wt (v1<->v2,wt): 2 3 2
continue(y/n): y
enter edge & cores wt (v1<->v2,wt): 2 4 5
continue(y/n): y
enter edge & cores wt (v1<->v2,wt): 3 4 3
continue(y/n): y
enter edge & cores wt (v1<->v2,wt): 3 5 4
continue(y/n): y
enter edge & cores wt (v1<->v2,wt): 4 5 2
continue(y/n): y
enter edge & cores wt (v1<->v2,wt): 4 6 3
continue(y/n): y
enter edge & cores wt (v1<->v2,wt): 5 6 5
continue(y/n): n
tree includes following edges:
edge: 1<-->3 wt: 3
edge: 3<-->2 wt: 2
edge: 3<-->4 wt: 3
edge: 4<-->5 wt: 2
edge: 4<-->6 wt: 3
wt of minimum spanning tree: 13