使用 DFS 检测图中的循环:2 种不同的方法以及有什么区别 [英] Detecting cycles in a graph using DFS: 2 different approaches and what's the difference

问题描述

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

我听说过 2 种在图中找到循环的方法:

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

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

谁能解释一下什么是图的后边以及上述两种方法之间的区别是什么.

谢谢.

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

公共类图{私有 int[][] 节点；//所有节点；例如int[][] 节点 = {{1,2,3}, {3,2,1,5,6}...};公共 int[] getAdjacentNodes(int v) {返回节点[v];}//图中的顶点数公共 int vSize() {返回节点长度；}}

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

 公共类 DFSCycle {私有布尔标记[];私有整数；私有图g；私人布尔hasCycle;//s - 起始节点公共 DFSCycle(图形 g，int s){这个.g = g;这.s = s;标记 = 新布尔 [g.vSize()];findCycle(g,s,s);}公共布尔 hasCycle() {返回hasCycle；}public void findCycle(Graph g, int v, int u) {标记 [v] = 真；for (int w : g.getAdjacentNodes(v)) {如果(！标记[w]){标记 [w] = 真；findCycle(g,w,v);} 否则如果 (v != u) {hasCycle = 真；返回;}}}}

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

公共类 DFSDirectedCycle {私有布尔标记[];私有布尔 onStack[];私有整数；私有图g；私人布尔hasCycle;公共 DFSDirectedCycle(图形 g，int s){这.s = s这个.g = g;标记 = 新布尔 [g.vSize()];onStack = new boolean[g.vSize()];findCycle(g,s);}公共布尔 hasCycle() {返回hasCycle；}public void findCycle(Graph g, int v) {标记 [v] = 真；onStack[v] = 真；for (int w : g.adjacentNodes(v)) {如果(！标记[w]){findCycle(g,w);} else if (onStack[w]) {hasCycle = 真；返回;}}onStack[v] = 假；}}

解决方案

回答我的问题:

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

上述两种方法实际上是相同的.但是，这种方法只能应用于无向图.

这个算法对有向图不起作用的原因是，在有向图中，到同一个顶点的 2 条不同路径不会形成循环.例如:A-->B, B-->C, A-->C - 不要循环，而在无向循环中:A--B, B--C, C--A 会.

在无向图中找到一个圈

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

在有向图中找到一个循环

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

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

Note that a graph is represented as an adjacency list.

I've heard of 2 approaches to find a cycle in a graph:

1. Keep an array of boolean values to keep track of whether you visited a node before. If you run out of new nodes to go to (without hitting a node you have already been), then just backtrack and try a different branch.

2. The one from Cormen's CLRS or Skiena: For depth-first search in undirected graphs, there are two types of edges, tree and back. The graph has a cycle if and only if there exists a back edge.

Can somebody explain what are the back edges of a graph and what's the diffirence between the above 2 methods.

Thanks.

Update: Here's the code to detect cycles in both cases. Graph is a simple class that represents all graph-nodes as unique numbers for simplicity, each node has its adjacent neighboring nodes (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 code to detect cycles in an undirected graph:

    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 code to detect cycles in a directed graph:

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

解决方案

Answering my question:

The graph has a cycle if and only if there exists a back edge. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS forming a cycle.

Both approaches above actually mean the same. However, this method can be applied only to undirected graphs.

The reason why this algorithm doesn't work for directed graphs is that in a directed graph 2 different paths to the same vertex don't make a cycle. For example: A-->B, B-->C, A-->C - don't make a cycle whereas in undirected ones: A--B, B--C, C--A does.

Find a cycle in undirected graphs

An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge).

Find a cycle in directed graphs

In addition to visited vertices we need to keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree.

Update: Working code is in the question section above.

这篇关于使用 DFS 检测图中的循环:2 种不同的方法以及有什么区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！