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.

CodePudding user response：

Create an actual graph and go through that (e.g. struct for each node, nodes linked via pointers). Right now what you have is an array that you go through item by item if I understand correctly. You can use an array to store one level of the graph. 0 (first level) 2 1 (second level) ...

CodePudding user response：

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