graph - 使用 DFS 检测图中的循环 : 2 different approaches and what's the difference

Question

请注意，图表示为邻接列表。

我听说过两种在图表中查找循环的方法:

1. 保留一个 bool 值数组来跟踪您之前是否访问过某个节点。如果你用完了新的节点(没有到达你已经去过的节点)，那么只需回溯并尝试不同的分支。

2. Cormen 的 CLRS 或 Skiena 中的一个:对于无向图中的深度优先搜索，有两种类型的边:树边和反向边。当且仅当存在后边时，图才有环。

有人可以解释一下什么是图的后边以及上述两种方法之间的区别吗？

谢谢。

更新:这是在两种情况下检测循环的代码。 Graph 是一个简单的类，为了简单起见，将所有图节点表示为唯一的数字，每个节点都有其相邻的邻居节点(g.getAdjacentNodes(int)):

public class Graph {

  private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};

  public int[] getAdjacentNodes(int v) {
    return nodes[v];
  }

  // number of vertices in a graph
  public int vSize() {
    return nodes.length;
  }

}

用于检测无向图中循环的 Java 代码:

    public class DFSCycle {

    private boolean marked[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    // s - starting node
    public DFSCycle(Graph g, int s) {
        this.g = g;
        this.s = s;
        marked = new boolean[g.vSize()];
        findCycle(g,s,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v, int u) {

        marked[v] = true;

        for (int w : g.getAdjacentNodes(v)) {
            if(!marked[w]) {
                marked[w] = true;
                findCycle(g,w,v);
            } else if (v != u) {
                hasCycle = true;
                return;
            }
        }

    }  
}

用于检测有向图中的循环的 Java 代码:

public class DFSDirectedCycle {

    private boolean marked[];
    private boolean onStack[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    public DFSDirectedCycle(Graph g, int s) {
        this.s = s
        this.g = g;
        marked = new boolean[g.vSize()];
        onStack = new boolean[g.vSize()];
        findCycle(g,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v) {

        marked[v] = true;
        onStack[v] = true;

        for (int w : g.adjacentNodes(v)) {
            if(!marked[w]) {
                findCycle(g,w);
            } else if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }

        onStack[v] = false;
    }
}

Answer 1

回答我的问题:

当且仅当存在后边时，图才有环。后边是从节点到其自身(自环)或其在 DFS 生成的树中的祖先之一的边，形成循环。

上面两种方法实际上意思是一样的。然而，该方法只能应用于无向图。

该算法不适用于有向图的原因是，在有向图中，到同一顶点的 2 条不同路径不会形成循环。例如:A-->B、B-->C、A-->C - 不形成循环，而在无向循环中:A--B、B--C、C--A 则形成循环。

在无向图中查找循环

当且仅当深度优先搜索 (DFS) 找到指向已访问顶点(后边缘)的边时，无向图才有循环。

在有向图中查找循环

除了访问过的顶点之外，我们还需要跟踪当前位于 DFS 遍历函数递归堆栈中的顶点。如果我们到达的顶点已经在递归堆栈中，那么树中就有一个循环。

更新:工作代码位于上面的问题部分。