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

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-> v在处理顶点y时已经处理过一次。

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

因此，如果y不是V的父，并且processed[y] == false这意味着Y具有被发现（否则执行不能到达else if部分），但不被处理，所以y必须是V的奶奶或以上，这是一个后端，但没问题，我们可以处理它，因为它还没有被处理。

现在如果processed[y] == true？ 我认为这个“如果”永远不会发生，这种情况永远不会发生。

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

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

因此，如果我们永远不会肉加工顶点，我们可以删除!processed[y]，因为它将永远是真实的。

Answer 1

不，processed[y] == 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)。

防止从hapenning是事实，processed[y] == true