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, Что касается if (visited[succ] == 1) { return true; } // back edge/loop detected! в ДПП, я попытался visited[succ] == 1 и visited[succ] >= 1, все они работают. Я смущен в чем разница между `` visited [succ] == 1 and посещен [succ] == 2```? Могут ли они обнаруживать разные типы кругов?

2, Кажется, что если мы используем visited для хранения True и False (посетили и не посетили), он по-прежнему работает (от другого Leetcode topic). Когда мы должны использовать un-visit, visit, visited? и Когда следует использовать un-visited и посещать? Любые примеры?

Благодаря

Answer 1

Переключение на visited[succ] >= 1 не дает эквивалентный алгоритм: текущий алгоритм обнаружит направленный ациклический граф (DAG), в то время как модифицированный алгоритм будет обнаруживать только деревья (все деревья DAGs, но не все DAGs деревья).

Алгоритм использует 2, чтобы обеспечить обнаружение DAG. Если все, что вам нужно, - это обнаружение дерева, вы можете переключиться на использование Booleans; с DAG, однако, просто отметить посещенную вершину уже недостаточно. Рассмотрим этот простой график:

Если оставить visited["C"] на 1, алгоритм доложит цикл, когда он пробует A -> C край.