BFS遍历，同一个节点被访问两次

Question

我想知道如何用 C 语言编写 BFS 算法我得到了这个

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

图表看起来像 graph。当我打印出 BFS 时，它似乎给了我 0 1 2 2 3 4

我不完全确定这里出了什么问题，如果您能提供帮助，我们将不胜感激。

Answer 1

创建一个实际的图并遍历它（例如，每个节点的结构，通过指针链接的节点）。现在你拥有的是一个数组，如果我理解正确的话，你可以逐项浏览它。您可以使用数组来存储图形的一个级别。 0（一级） 2 1（二级） ...

Answer 2

我不确定 BFS 是否适合您所做的事情。您的图表不是树，并且节点具有多个父节点，因此很难判断节点的真实级别。

但是为了使您的代码按预期工作，您只需要修复缺少的 visited 数组的使用：

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

BFS遍历，同一个节点被访问两次

BFS traversal, same node being accessed twice

c

graph-theory

breadth-first-search