La détection de cycles dans un graphe à l'aide de DFS: 2 approches différentes et quelle est la différence

Noter qu'un graphe est représenté par une liste d'adjacence.

J'ai entendu parler de 2 approches pour trouver un cycle dans un graphe:

  1. Garder un tableau de valeurs booléennes pour garder une trace de savoir si vous avez visité un nœud avant. Si vous manquez de nouveaux nœuds à l'aller (sans frapper un nœud que vous avez déjà), puis revenir en arrière et essayer une autre branche.

  2. L'un de Cormen du PLC ou Skiena: Pour la profondeur de recherche dans les graphes non dirigés, il y a deux types d'arêtes de l'arbre et à l'arrière. Le graphe a un cycle si et seulement si il existe une arête arrière.

Quelqu'un peut-il expliquer ce que sont le dos de arêtes d'un graphe et quelle est la diffirence entre les 2 méthodes.

Grâce.

Mise à jour:
Voici le code pour détecter les cycles dans les deux cas. Le graphique est une simple classe qui représente l'ensemble de graphe de nœuds comme des numéros uniques pour des raisons de simplicité, chaque nœud a ses voisines nœuds voisins (g.getAdjacentNodes(int)):

public class Graph {

  private int[][] nodes; //all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};

  public int[] getAdjacentNodes(int v) {
    return nodes[v];
  }

  //number of vertices in a graph
  public int vSize() {
    return nodes.length;
  }

}

Code Java pour détecter les cycles dans un graphe non-dirigé:

    public class DFSCycle {

    private boolean marked[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    //s - starting node
    public DFSCycle(Graph g, int s) {
        this.g = g;
        this.s = s;
        marked = new boolean[g.vSize()];
        findCycle(g,s,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v, int u) {

        marked[v] = true;

        for (int w : g.getAdjacentNodes(v)) {
            if(!marked[w]) {
                marked[w] = true;
                findCycle(g,w,v);
            } else if (v != u) {
                hasCycle = true;
                return;
            }
        }

    }  
}

Code Java pour détecter les cycles dans un graphe orienté:

public class DFSDirectedCycle {

    private boolean marked[];
    private boolean onStack[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    public DFSDirectedCycle(Graph g, int s) {
        this.s = s
        this.g = g;
        marked = new boolean[g.vSize()];
        onStack = new boolean[g.vSize()];
        findCycle(g,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v) {

        marked[v] = true;
        onStack[v] = true;

        for (int w : g.adjacentNodes(v)) {
            if(!marked[w]) {
                findCycle(g,w);
            } else if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }

        onStack[v] = false;
    }
}
  • Je pense qu'il y a une erreur dans le graphe ordonné code. Dans le cas de parcours d'un graphe en forme de O, avec la racine en haut et avec toutes les arêtes dirigées vers le bas, cet algorithme détecte cycle (d'abord la traversée de la gauche de O vers le bas et marquer tous les nœuds marqués, puis la partie droite de O jusqu'à ce que je vais arriver à fond, ce qui est déjà marqué). Je voudrais ajouter, il y a marqué[v]= false; juste après findCycle(g,w); Qu'en pensez-vous?
  • Dans DFSCycle la condition à vérifier pour le cycle est incorrect. Il devrait être if(i != u) // If an adjacent is visited and not parent of current vertex, then there is a cycle. { hasCycle = true; return; }
  • Ne devrait pas } else if (v != u) { être } else if (w != u) {?