algorithm - 使用 DFS 进行图遍历

Question

我正在从 Steven S. Skiena 的算法设计手册中学习图形遍历。在他的书中，他提供了使用 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]) || (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;
}

在无向图中，看起来下面的代码正在处理边两次(调用方法 process_edge(v,y)。一次是在遍历顶点 v 时，另一次是在处理顶点 y 时)。
所以我在else if ((!processed[y]) || (g->directed))中添加了条件parent[v]!=y >。
它只处理一次边缘。但是，我不确定如何修改此代码以使用平行边和自循环边。代码应该处理平行边和自循环。

Answer 1

简答:

用 (parent[v]!=y) 代替 (!processed[y]) 而不是将其添加到条件中.

详细答案:

在我看来，书中的实现存在一个错误，您发现并修复了该错误(平行边除外。更多内容见下文)。实现应该对于有向图和无向图都是正确的，它们之间的区别记录在 g->directed bool 属性中。

在书中，就在实现之前，作者写道:

The other important property of a depth-first search is that it partitions the edges of an undirected graph into exactly two classes: tree edges and back edges. The tree edges discover new vertices, and are those encoded in the parent relation. Back edges are those whose other endpoint is an ancestor of the vertex being expanded, so they point back into the tree.

因此条件 (!processed[y]) 应该处理无向图(因为条件 (g->directed) 是处理有向图)允许算法处理作为后边的边，并防止它重新处理作为树边的边(在相反的方向)。但是，正如您所注意到的，当使用这种条件读取子节点时，树边被视为后边，因此您应该将此条件替换为您建议的 (parent[v]!=y) .

条件 (!processed[y]) 在算法读取无向图时始终为真，只要不存在平行边(进一步详细说明为何为真 - *) .如果存在平行边 - 在第一次“复制”它们之后读取的那些平行边将产生 false 并且边缘将不会被处理，而应该被处理。但是，您建议的条件将区分树边和其余边(后边、平行边和自环)，并允许算法仅处理那些不是相反方向的树边。

要引用自边，它们在新旧条件下都应该没问题:它们是 y==v 的边。到达它们，y 被发现(因为 v 在通过它的边缘之前被发现)，没有被处理(v 只作为最后一个被处理线 - 在穿过它的边缘之后)并且它不是 v 的父级(v 不是它自己的父级)。

---

*通过 v 的边缘，算法读取已发现的 y 的条件(因此它不会进入第一个条件 block )。正如上面引用的(在书中也有一个半证明，我将在这个脚注的末尾包含)，p 是树边或后边。由于 y 被发现，它不可能是从 v 到 y 的树边。它可以是祖先的后沿，这意味着调用处于递归调用中，该调用在某个时候开始处理该祖先，因此祖先的调用尚未到达最后一行，将其标记为已处理(因此仍标记为未处理)并且它可以是从 y 到 v 的树边，在这种情况下，同样的情况成立 - 而 y 仍然是标记为未处理。

每条边都是树边或后边的半证明:

Why can’t an edge go to a brother or cousin node instead of an ancestor? All nodes reachable from a given vertex v are expanded before we finish with the traversal from v, so such topologies are impossible for undirected graphs.