c语言 - 了解算法设计手册(第二版)BFS实现中的处理状态

Question

在BFS实现的注释中，书中说"一个顶点在我们遍历了它的所有传出边之后被认为是处理的"，这与给定的实现相矛盾：

bfs(graph *g, int start)
{
queue q;
int v;
inv y;
edgenode *p;
init_queue(&q);
enqueue(&q, start);
discovered[start] = TRUE;
while (empty_queue(&q) == FALSE)
{
v = dequeue(y);
processed[v] = TRUE;
p = g->edges[v];
while (p != NULL)
{
y = p->y;
if ((process[y] == FALSE) || g->undirected)
{
process_edge(v, y);
}
if (discovered[y] == FALSE)
{
enqueue(&q, y);
discovered[y] = TRUE;
parent[y] = v;
}
p = p->next;
}
}
}

不应该将processed[v] = TRUE;放在 while 循环之后吗？

Answer 1

在此实现的上下文中，如果图形具有自循环，它将处理某些 v 的边 (v， v)。当然，我们可以移动processed[v] = TRUE;，在while循环之后，但在这种情况下，我们应该仔细对待自循环(导致更多的代码)。