DFS：被访问、访问和未访问混淆

Question

的代码中

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] == 1andvisited[succ] ==2``` 之间有什么区别？ 他们能检测到不同类型的圆吗？

2、好像我们用visited来存储True和False（已访问和未访问），它仍然有效（来自另一个Leetcode topic）。 什么时候应该使用un-visited、visiting、visited？我们什么时候应该使用未访问过的和访问过的？有例子吗？

谢谢

Answer 1

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

该算法使用 2 允许 DAG 检测。如果你只需要树检测，你可以切换到使用布尔值；然而，对于 DAG，简单地标记一个已访问的顶点已经不够了。考虑这个简单的图表：

如果您将 visited["C"] 保留在 1，算法将在尝试 A -> C 边时报告一个循环。

DFS：被访问、访问和未访问混淆

DFS: confused by visiting, visited and un-visited

algorithm

depth-first-search

graph-algorithm