Broadcast tree program in C in computer Network | Implement broadcast tree for a given subnet of hosts

NAME OF THE EXPERIMENT: Broadcast Tree.

AIM: Implement broadcast tree for a given subnet of hosts

HARDWARE REQUIREMENTS: Intel-based Desktop PC:-RAM of 512 MB

SOFTWARE REQUIREMENTS: Turbo C / Borland C.

THEORY:

 This technique is widely used because it is simple and easy to understand. The idea of this algorithm is to build a graph of the subnet with each node of the graph representing a router and each arc of the graph representing a communication line. To choose a route between a given pair of routers the algorithm just finds the broadcast between them on the graph.

ALGORITHM/FLOWCHART:

step 1:declare variable as int p,q,u,v,n;

step 2:Initialize min=99,mincost=0;

step 3: declare variable as int t[50][2],i,j;

step 4: declare variable as int parent[50],edge[50][50];

step 5: Begin

step 6: write "Enter the number of nodes"

step 7: read "n"

step 8: Initialize i=0

step 9: repeat step(10-12) until i<n

step10: increment i

step11: write"65+i"

step12: Initialize parent[i]=-1

step13:wite "\n"

step14: Initialize i=0

step15: repeat 

step(15-21) until i<n

step16: increment i

step17: write"65+i"

step18: Initialize j=0

step19: repeat until j<n

step20: increment j

step21: read edge[i][j]

step22: Initialize i=0

step23: repeat step(23-43) until i<n

step24: increment i

step25: Initialize j=0

step26: repeat until j<n

step27: increment j

step28: if'edge[i]j]!=99

step29: if'min>edge[i][j] repeat step (29-32)

step30: intialize min=edge[i][j]

step31: intialize u=i

step32: intialize v=j

step33: calling function p=find(u);

step34: calling function q=find(v);

step35: if'P!=q repeat steps(35-39)

step36: intialize t[i][0]=u

step37: intialize t[i][1]=v

step38: initialize mincost=mincost+edge[u][v]

step39: call function sunion(p,q)

step40: else repeat steps(40-42)

step41: Intialize t[i][0]=-1;

step42: Intialize t[i][1]=-1;

step43: intialize min=99;

step44; write"Minimum cost is %d\n Minimum spanning tree is",mincost

step45: Initialize i=0

step46: repeat until i<nstep47: increment istep48: if't[i][0]!=-1 && t[i][1]!=-1'repeat step(48-50)

step49: write "%c %c %d", 65+t[i][0], 65+t[i][1], edge[t[i][0]][t[i][1]]

step50: write"\n"step51: endstep52: called function sunion(int l,int m) repeat step(51-52)

step53: intialize parent[l]=m

step54: called function find(int l) repeat step(53-56)

step55: if parent([l]>0)

step56: initialize l=parent

step57: return l

Source Code:

// Write a 'c' program for broadcast tree from subnet of host

#include<stdio.h>

int p,q,u,v,n;

int min=99,mincost=0

int t[50][2],i,j;

int parent[50],edge[50][50];

main()

{

clrscr();

printf("\n Enter the number of nodes");

scanf("%d",&n);

for(i=0;i<n;i++)

{

printf("%c\t",65+i);

parent[i]=-1

}

printf("\n");

for(i=0;i<n;i++)

{

printf("%c",65+i);

for(j=0;j<n;j++)

scanf("%d",&edge[i][j]);

}

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

if(edge[i][j]!=99)

if(min>edge[i][j])

{

min=edge[i][j]

u=i;

v=j;

}

p=find(u);

q=find(v);

if(p!=q)

{

t[i][0]=u;

t[i][1]=v;

mincost=mincost+edge[u][v];

sunion(p,q);

}

else

t[i][0]=-1;

t[i][1]=-1;

}

min=99;

}

printf("Minimum cost is %d \n Minimum spanning tree is \n",mincost);

for(i=0;i<n;i++)

if(t[i][0]!=-1 && t[i][1]!=-1)

{

printf("%c %c %d",65+t[i][0],65+t[i][1],edge[t[i][0]] [t[i][1]])

  

printf("\n");

}

getch();

}

sunion(int I,int m)

{

parent[]=m;

}

find(int I)

{

if(parent[I]>0)

I=parent[I];

return I;

}

OUTPUT: