BFS traversal, same node being accessed twice

Question

I am trying to figure out how to write BFS algorithm in C and I got this

typedef struct graph {
   int numnodes;
   int **edges;
} graph;

void bfs(graph *g, int start) {
   int visited[g->numnodes], queue[g->numnodes], front =- 1, rear =- 1;

   for (int i = 0; i < g->numnodes; i++) {
      visited[i] = 0;
   }

   front++;
   queue[++rear] = start;
   visited[start] = 1;

   while (front <= rear) {
      start = queue[front++];
      printf("%d\t", start);
      for (int i = 0; i < g->numnodes; i++) {
         if (g->edges[start][i] == 1 && !visited[i]) {
            queue[++rear] = i;
         }
      }
   }
}

for graph looking like graph. When I print out BFS, it seems to give me 0 1 2 2 3 4

I'm not entirely sure what's wrong here, some help would be appreciated.

Answer 1

I am not sure if BFS is the right term for what you are doing. Your graph is not a tree and with a node having multiple parent nodes it is hard to tell on what level a node really is.

But to make your code work as expected, you just need to fix your missing use of visited array:

        if (g->edges[start][i] == 1 && !visited[i]) {
            queue[++rear] = i;
            visited[i] = 1;
        }