图表-如何避免在深度优先搜索中两次重新处理同一边？ [英] graph - How to avoid reprocessing same edge twice in Depth First Search?

问题描述

算法设计手册很好地描述了BFS和DFS。在决定是否避免双重处理时，本书中的dfs代码存在问题。我找到了勘误表，并将勘误表应用于代码，但仍然我认为经过精炼的代码存在检查双重处理边缘的问题。

The Algorithm Design Manual describes BFS and DFS quite well. The code for dfs in the book has a problem when deciding whether or not to avoid double processing edges. I found the Errata and applied the errata to the code, but still I think the refined code has a problem of checking double processing edges.

我按如下所示粘贴精炼代码：

I paste the refined code as follows:

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;
}

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

The place where I think there is a problem is marked via ** **.

所以有问题的地方是条件之一。假设它是无向图，因此我们可以忽略（g-> directed）的条件。

So the questionable place is one of the conditions. Let's assume it is undirected graph, so we can just ignore the condition of (g->directed).

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

Ok, let's focus on parent[v] != y first. if parent[v] == y, of course, we don't need to process edge v->y again because y->v is already processed once when processing vertex y.

如果 parent [v]！= y ，我的问题是是否已处理！ [y]&& 是必需的。

And if parent[v] != y, my question is whether !processed[y] && is necessary or not.

因此，如果y不是v的父母，则已处理[y] ==假，这意味着已找到y（否则执行将无法达到 else如果部分），但尚未处理，所以y必须是v的祖母或更高。这是一个后沿，但没问题，我们可以对其进行处理，因为它尚未被处理。

So, if y is not v's parent, and processed[y] == false which means y has been found (otherwise the execution can't reach else if part) but not been processed, so y must be a grandma or above of v. This is a back edge, but no problem, we can process it as it hasn't been processed yet.

现在如果 processed [y] == true ，该怎么办？ 我认为这种如果将永远不会发生，这种情况永远不会成立。

Now what if processed[y] == true? I think this "if" will never happen and this condition will never be true.

为什么？好的，我们假设 processed [y] 是正确的。这意味着已经处理了所有包含y的路径，并且还处理了这些路径中的所有顶点，对吗？因此，在这种情况下，尚未完成处理的顶点v如何接近y？

Why? Ok, let's assume processed[y] can be true. This means that all paths which include y have been processed and also all vertexes in those paths have been processed, right? So if this is a case, how can a "not yet finished processing" vertex v approach y?

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

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

因此，如果我们从不对已处理的顶点进行处理，则可以删除！processed [y] ，因为它将始终为真。

So if we never will meat a processed vertex, we can just remove !processed[y] as it will be always true.

推荐答案

否， processed [y] == true 会产生

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

Look at the following graph, and assume the following [feasible] DFS traversal:

v0,v1,v2

v0 开始，然后在处理（v0，v1）之后递归调用 dfs（v1）。现在， v1 处理（v1，v2）并递归调用 dfs（v2）。 v2 看到已发现 v0 ，如果 else >语句，发现未处理（v0，v2）和 parent [v2]！= v0 [<通过 v1 ]发现了code> v2 。

v0 starts, and then recursively invoke dfs(v1) after processing (v0,v1). Now, v1 processes (v1,v2) and recursively invoke dfs(v2). v2 sees that v0 is discovered and go to the else if statement, and sees that (v0,v2) was not processed and parent[v2] != v0 [v2 was discovered via v1].

现在，当我们从递归中返回 v0 ，然后当我们检查下一个儿子时，它就是 v2 。 v2 已经被发现，所以我们转到 else if 和 v2 不是 v0 的父级，因此如果没有！processed [y] 部分，我们将进行处理（v0，v2）两次。

Now, when we go back from the recursion we reach back v0, and when we check the next "son" - it is v2. v2 was already discovered, so we go to else if, and v2 is not the parent of v0, so without the !processed[y] part, we would have processed (v0,v2) twice.

防止出现这种情况的唯一原因是已处理[y] == true

The only thing that prevent that from hapenning is the fact that processed[y] == true

这篇关于图表-如何避免在深度优先搜索中两次重新处理同一边？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！