DFS：通过访问，访问和未访问而感到困惑

以下代码来自Leetcode discussions。DFS：通过访问，访问和未访问而感到困惑

public class Solution { 
    public boolean validTree(int n, int[][] edges) { 
     int[] visited = new int[n]; 
     List<List<Integer>> adjList = new ArrayList<>(); 
     for (int i=0; i<n; ++i) { adjList.add(new ArrayList<Integer>()); } 
     for (int[] edge: edges) { 
      adjList.get(edge[0]).add(edge[1]); 
      adjList.get(edge[1]).add(edge[0]); 
     } 
     if (hasCycle(-1, 0, visited, adjList)) { return false; } // has cycle 
     for (int v: visited) { if (v == 0) { return false; } } // not 1 single connected component 
     return true; 
    } 

    private boolean hasCycle(int pred, int vertex, int[] visited, List<List<Integer>> adjList) { 
     visited[vertex] = 1; // current vertex is being visited 
     for (Integer succ: adjList.get(vertex)) { // successors of current vertex 
      if (succ != pred) { // exclude current vertex's predecessor 
       if (visited[succ] == 1) { return true; } // ###back edge/loop detected! 
       else if (visited[succ] == 0) { 
        if (hasCycle(vertex, succ, visited, adjList)) { return true; } 
       } 
      } 
     } 
     visited[vertex] = 2; 
     return false; 
    } 
}

我的问题是：

1，对于在DFS if (visited[succ] == 1) { return true; } // back edge/loop detected!，我试图visited[succ] == 1和visited[succ] >= 1，所有这些工作。 我很困惑``visited [succ] == 1 and visited [succ] == 2```有什么区别？他们可以检测到不同类型的圈子吗？ 2，看起来如果我们用visited存储True和False（已访问和未访问），它仍然有效（从另一个Leetcode topic）。 什么时候应该使用未访问，访问，访问？什么时候我们应该使用未访问，并访问？任何例子？

感谢

来源

2017-02-22 BAE

切换到visited[succ] >= 1不会产生等效的算法：当前算法将检测向无环图（DAG），而修改算法将只检测树（所有的树都DAG的，但不是所有的DAG是树）。

该算法使用2来允许DAG检测。如果您只需要检测树，则可以切换到使用布尔值;与DAGs，但是，只是标记一个顶点访问已不够。考虑一个简单的图表：

如果您在1离开visited["C"]，当它试图在A算法将报告周期 - “ç边缘。

来源

2017-02-22 19:42:39 dasblinkenlight

谢谢。对于无向图，我们应该使用'visited [succ] == 1'来检测圆圈。但对于有向图，我们应该在DAG中使用'visited [succ] == 1'，并且在树中使用'visited [succ] == 2'？纠正我，如果我错了。 – BAE

@BAE如果你正在检测一棵树，你应该使用'visited [succ]！= 0'来覆盖'1'和'2'。 – dasblinkenlight

DFS：通过访问，访问和未访问而感到困惑

回答

相关问题