algorithm - graph - 如何避免在深度优先搜索中重复处理相同的边缘？

Question

Algorithm Design Manual很好地描述了 BFS 和 DFS。书中dfs的代码在决定是否避免双重处理边缘时有问题。我找到了 Errata并将勘误表应用于代码，但我仍然认为改进后的代码存在检查双重处理边缘的问题。

我贴上提炼后的代码如下:

dfs(graph *g, int v) {
       edgenode *p;
       int y;
       if (finished) return;
       discovered[v] = TRUE;
       time = time + 1;
       entry_time[v] = time;
       process_vertex_early(v);
       p = g->edges[v];
       while (p != NULL) {
             /* temporary pointer */
             /* successor vertex */
             /* allow for search termination */
             y = p->y;
             if (discovered[y] == FALSE) {
                   parent[y] = v;
                   process_edge(v,y);
                   dfs(g,y);
             }
             else if (**(!processed[y] && parent[v] != y)** || (g->directed))
                   process_edge(v,y);
             if (finished) return;
             p = p->next;
       }
       process_vertex_late(v);
       time = time + 1;
       exit_time[v] = time;
       processed[v] = TRUE;
}

我认为有问题的地方通过** **标出。

所以有问题的地方就是条件之一。假设它是无向图，那么我们可以忽略 (g->directed) 的条件。

好吧，让我们先关注parent[v] != y。如果parent[v] == y，当然我们不需要再处理边v->y了，因为在处理顶点y的时候y->v已经处理过一次了。

如果 parent[v] != y，我的问题是 !processed[y] && 是否必要。

因此，如果 y 不是 v 的父级，并且 processed[y] == false 这意味着 y 已经找到(否则执行无法到达 else if part) 但没有被处理，所以 y 必须是 v 的祖母或以上。这是一个后边，但是没问题，我们可以处理它，因为它还没有被处理。

现在如果 processed[y] == true 会怎样？ 我认为这个“如果”永远不会发生，这个条件也永远不会成立。

为什么？好的，让我们假设 processed[y] 可以是真的。这意味着所有包含 y 的路径都已处理，并且这些路径中的所有顶点都已处理，对吗？那么如果是这种情况，“尚未完成处理”的顶点 v 如何接近 y？

我认为在 dfs 中，没有顶点会接近已处理的顶点，对吗？

因此，如果我们永远不会处理已处理的顶点，我们可以删除 !processed[y]，因为它将始终为真。

Answer 1

不，processed[y] == true 可能产生 true。

查看下图，并假设以下 [可行的] DFS 遍历:

v0,v1,v2

v0开始，然后在处理(v0,v1)后递归调用dfs(v1)。现在，v1 处理 (v1,v2) 并递归调用 dfs(v2)。 v2 发现 v0 并转到 else if 语句，并看到 (v0,v2)未被处理并且 parent[v2] != v0 [v2 是通过 v1 发现的]。

现在，当我们从递归返回时，我们返回 v0，当我们检查下一个“子”时 - 它是 v2。 v2 已经被发现，所以我们转到 else if，并且 v2 不是 v0 的父级，所以如果没有 !processed[y] 部分，我们将处理 (v0,v2) 两次。

唯一阻止这种情况发生的是 processed[y] == true