6

算法设计手册很好地描述了 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首先关注。ifparent[v] == y当然，我们不需要再次处理边 v->y，因为在处理顶点 y 时，y->v 已经处理过一次。

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

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

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

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

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

因此，如果我们永远不会处理已处理的顶点，我们可以删除!processed[y]，因为它总是正确的。

4

1 回答 1

6

不，processed[y] == true可以产生真实的。

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

v0,v1,v2

图表示例

v0启动，然后dfs(v1)在处理后递归调用(v0,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

于 2012-04-05T17:50:29.143 回答