DFS：通過訪問，訪問和未訪問而感到困惑

Question

以下代碼來自Leetcode discussions。

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）。 什麼時候應該使用未訪問，訪問，訪問？什麼時候我們應該使用未訪問，並訪問？任何例子？

感謝

Answer 1

切換到visited[succ] >= 1不會產生等效的算法：當前算法將檢測向無環圖（DAG），而修改算法將只檢測樹（所有的樹都DAG的，但不是所有的DAG是樹）。

該算法使用2來允許DAG檢測。如果您只需要檢測樹，則可以切換到使用布爾值;與DAGs，但是，只是標記一個頂點訪問已不夠。考慮一個簡單的圖表：

如果您在1離開visited["C"]，當它試圖在A算法將報告週期 - 「ç邊緣。