BFS

visit[]={0};

A[][] = connection matrix.

n = number of nodes, from 1 to n.
source = 1;
temp[0]=source;
visit[ source ]=1;
N = 0;
M = 1;

while(N!=M)
{
for(i=1;i<=n;i++)
if(A[temp[N]][i]==1&&visit[i]==0)

// A[temp[N]][i]==1 means node temp[N] & i are connected. visit[i]==0 means node i has not visited
{
visit[i]=1;
temp[M]=i;
M++;
}
N++;
}

for(i=0;i<M;i++)
printf(“%ld “,temp[i]);

Advertisements