DFS: durchbesucht, besucht und nicht besucht

Question

In den folgenden Codes von 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; 
    } 
} 

Meine Fragen sind:

1, als für if (visited[succ] == 1) { return true; } // back edge/loop detected! in DFS, habe ich versucht visited[succ] == 1 und visited[succ] >= 1, alle von ihnen arbeiten. Ich bin verwirrt was ist der Unterschied zwischen "besucht [succ] == 1 and besucht [succ] == 2```? Können sie verschiedene Arten von Kreisen erkennen?

2, Es scheint, dass, wenn wir visited verwenden, True und False (besuchte und nicht besuchte) zu speichern, funktioniert es immer noch (aus einem anderen Leetcode topic). Wann sollten wir nicht besucht, besucht, besucht werden? und wann sollten wir nicht besucht und besucht werden? Irgendwelche Beispiele?

Dank

Answer 1

-visited[succ] >= 1 Schalt kein Äquivalent Algorithmus ergeben: der aktuelle Algorithmus gerichteten azyklischen Graphen (DAG) erkennen, während der modifizierte Algorithmus nur Bäume erkennt (alle Bäume DAGs sind, aber nicht alle DAGs sind Bäume).

Der Algorithmus verwendet 2, um die DAG-Erkennung zu ermöglichen. Wenn Sie nur die Baumerkennung benötigen, können Sie zur Verwendung von booleschen Werten wechseln. Bei DAGs ist es jedoch nicht mehr ausreichend, einen besuchten Scheitelpunkt einfach zu markieren. Betrachten Sie diese einfache Grafik:

Wenn Sie visited["C"] bei 1 verlassen, würde der Algorithmus einen Zyklus anzuzeigen, wenn der A versucht -> C Rand.