图-如何避免在深度优先搜索中重复处理相同的边两次？

Question

算法设计手册对BFS和DFS的描述相当到位。书中关于dfs的代码在决定是否避免双处理边时有一个问题。我找到了勘误表并将勘误表应用到代码中，但我仍然认为精炼后的代码有一个检查双重处理边的问题。

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]&是否必要。

因此，如果我们永远不会肉处理顶点，我们可以删除！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)并且父[v2]！=v0[v2是通过v1]发现的。

现在，当我们从递归返回到v0时，当我们检查下一个“子”时，它是v2。v2已被发现，因此我们转到else if，而v2不是v0的父级，因此如果没有！processed[y]部分，我们将对(v0,v2)进行两次处理。

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