使用深度优先搜索在图中查找循环

Question

在以下的深度优先搜索中，为什么ProcessEdge方法中的if(Parent[currVertex] != successorVertex)检查会检测到一个循环呢？此代码遵循S.Skiena的《算法设计手册》中给出的算法。这可能是一个笔误，并且应该是if(Parent[successorVertex] != currVertex)。如有任何疑问，请询问。我真的被卡住了。

    public void Search(int start)
    {
        /* NOTE: the differences from BFS are: this uses a stack instead of a queue AND this maintains 'time' variable */
        Stack<int> s = new Stack<int>();
        int currVertex;
        int successorVertex;
        int time = 0;

        s.Push(start);

        Discovered[start] = true;

        while (s.Count != 0)
        {
            currVertex = s.Pop();
            // time increments every time we enter a node (when discovered) and every time we exit a node (when processed_late, i.e. when all its neighbours have been processed)
            time++;
            EntryTime[currVertex] = time;

            ProcessVertexEarly(currVertex);
            Processed[currVertex] = true;

            for (int i = 0; i < Graph.Vertices[currVertex].Count; i++)
            {
                successorVertex = Graph.Vertices[currVertex][i].Y;
                if (!Processed[successorVertex] || Graph.IsDirected)
                {
                    ProcessEdge(currVertex, successorVertex);
                }
                if (!Discovered[successorVertex])
                {
                    s.Push(successorVertex);
                    Discovered[successorVertex] = true;
                    Parent[successorVertex] = currVertex;
                }
            }
            // time increments every time we enter a node (when discovered) and every time we exit a node (when processed_late, i.e. when all its neighbours have been processed)
            time++;
            ExitTime[currVertex] = time;
            ProcessVertexLate(currVertex);
        }
    }

    private void ProcessEdge(int currVertex, int successorVertex)
    {
        if(Parent[currVertex] != successorVertex) // then we've found a cycle
        {
            /* Found cycle*/
        }
    }

更新

在勘误表http://www.cs.sunysb.edu/~skiena/algorist/book/errata中找到了此代码的更正内容。请看第173页的(*)process_edge过程 -- 正确的测试应该是：

if (discovered[y] && (parent[x] != y)) { /* found back edge */

但这样能检测到环吗？因为在 DFS 方法中，只有当 discovered[y] == false 时才会调用 process_edge，所以 if 判断永远不会通过。

- bytefire

---

关于您的更新：Skiena的dfs在y未被发现或未被处理时调用process_edge。只有当探索完离开顶点的每条边后，顶点才会被标记为已处理。 - David Eisenstat

Answer 1

你发布的代码与Skiena原始代码有很大的区别：bfs-dfs.c，findcycle.c和其他内容。 Skiena的代码存在错误（尝试图3 2 1 2 2 3，一条两边路径），因此可能将其转换为Java的人尝试进行了修复。不幸的是，修复后的版本似乎也存在错误，但如果没有完整的程序，我无法确定。

我相信你所突出的那一行的意图如下。对于无向图中的深度优先搜索，有两种类型的边，即树边和回溯边。当且仅当存在回溯边时，图形成一个环。现在，Skiena 选择的无向图表示方法是将每个无向边存储为两个定向弧，每个方向一个。如果我们使用深度优先搜索来检测这个有向图中的循环，则由单个无向边对应的两个定向弧组成的长度为二的循环会被错误地报告为循环。如所写，此检查确保候选回退弧 y->x 不是树弧 x->y 的反向。

- David Eisenstat

---

谢谢。你上面提到的图是这样解释的吗：顶点0连接到顶点3，顶点1连接到顶点2，顶点2连接到顶点1等等？ - bytefire

另外，你能推荐一种更好的存储图形的方式吗？谢谢。 - bytefire

@bytefire 3个顶点，2条边，第一条边为1-2，第二条边为2-3。Skiena代码的问题在于它在树边上调用了process_edge函数。 - David Eisenstat

我现在明白了！在没有环的无向图中，每个顶点最多只有一个父节点。当第二次处理边缘（即反向弧）时，如果起始顶点的父节点与结束顶点不同，则表示我们有一个循环。谢谢你的帮助。顺便说一下，我将代码从C转换为C#，但没有使用书中的递归版本。我用栈代替了BFS代码中的队列。还没有测试它，所以可能还有其他错误。 - bytefire

Skiena 的代码的问题在于它在树边上调用 process_edge。这样，即使没有环，该代码也会报告存在环吗？ - bytefire