bfs遍历，两次访问相同的节点
我试图弄清楚如何在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
我不确定这里有什么问题，有些帮助将不胜感激。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我不确定BFS是否适合您正在做的事情。您的图不是树，并且具有具有多个父节点的节点，很难在一个节点的真正级别上分辨出来。
但是，为了使您的代码按预期工作，您只需要修复访问数组的
的缺少使用：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
visitedarray:创建一个实际的图形并浏览该图（例如每个节点的结构，通过指针链接的节点）。现在，如果我正确理解，您拥有的是您通过项目经历的数组。
您可以使用数组来存储图形的一个级别。
0（第一级）
2 1（第二级）
...
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)
...