使用DFS在图表中检测周期:2种不同的方法,区别在于什么

Question

请注意,图表表示为邻接列表.

我听说有两种方法可以在图表中找到一个循环:

1. 保留一个布尔值数组,以跟踪您之前是否访问过某个节点.如果你的新节点用完了(没有点击你已经存在的节点),那么只需回溯并尝试不同的分支.

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遍历函数的递归堆栈中的顶点.如果我们到达已经在递归堆栈中的顶点,那么树中就有一个循环.

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

Answer 2

为了完成,可以使用DFS(来自维基百科)在有向图中找到循环:

 L ? Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L