首页 文章

graph - 如何避免在Depth First Search中重复处理相同的边缘两次？

提问于
浏览 次
5

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 部分）但是没有被处理，所以y必须是v的祖母或以上 . 这是后边缘，但没问题，我们可以处理它，因为它尚未处理 .

现在怎么回事 processed[y] == true ？ I think this "if" will never happen and this condition will never be true.

为什么？好的，我们假设 processed[y] 可以是真的 . 这意味着已经处理了包含y的所有路径，并且还处理了这些路径中的所有顶点，对吧？所以，如果是这种情况，"not yet finished processing"顶点v怎么能接近？

I think in dfs, no vertex will ever approach a processed vertex, am I right?

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

algorithm data-structures graph depth-first-search

1 回答

  • 5

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

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

    v0,v1,v2

    graph example

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

    现在，当我们从递归返回时，我们返回 v0 ，当我们检查下一个"son"时 - 它是 v2 . v2 已经被发现了，所以我们去 else if ， v2 不是 v0 的父亲，所以如果没有 !processed[y] 部分，我们就会处理 (v0,v2) 两次 .

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

    回复于

相关问题