Trouver des cycles dans les graphes en utilisant la recherche en profondeur

Question

Étant donné la recherche en profondeur suivante, pourquoi la vérification if(Parent[currVertex] != successorVertex) dans la méthode ProcessEdge détecte-t-elle un cycle ? Ce code suit l'algorithme donné dans le livre Algortim Design Manual de S.Skiena. Il est possible que la vérification soit une faute de frappe et qu'elle soit censée être if(Parent[successorVertex] != currVertex). Veuillez demander toute clarification. Je suis vraiment bloqué(e) à ce sujet.

    public void Search(int start)
    {
        /* REMARQUE : les différences par rapport au BFS sont : ceci utilise une pile au lieu d'une file ET ceci maintient la variable 'temps' */
        Stack s = new Stack();
        int currVertex;
        int successorVertex;
        int time = 0;

        s.Push(start);

        Discovered[start] = true;

        while (s.Count != 0)
        {
            currVertex = s.Pop();
            // Le temps augmente à chaque fois que nous entrons dans un sommet (lorsqu'il est découvert) et à chaque fois que nous quittons un sommet (lorsqu'il est traité en retard, c'est-à-dire lorsque tous ses voisins ont été traités)
            time++;
            EntryTime[currVertex] = time;

            ProcessVertexEarly(currVertex);
            Processed[currVertex] = true;

            for (int i = 0; i < Graph.Vertices[currVertex].Count; i++)
            {
                successorVertex = Graph.Vertices[currVertex][i].Y;
                if (!Processed[successorVertex] || Graph.IsDirected)
                {
                    ProcessEdge(currVertex, successorVertex);
                }
                if (!Discovered[successorVertex])
                {
                    s.Push(successorVertex);
                    Discovered[successorVertex] = true;
                    Parent[successorVertex] = currVertex;
                }
            }
            // Le temps augmente à chaque fois que nous entrons dans un sommet (lorsqu'il est découvert) et à chaque fois que nous quittons un sommet (lorsqu'il est traité en retard, c'est-à-dire lorsque tous ses voisins ont été traités)
            time++;
            ExitTime[currVertex] = time;
            ProcessVertexLate(currVertex);
        }
    }

    private void ProcessEdge(int currVertex, int successorVertex)
    {
        if(Parent[currVertex] != successorVertex) // alors nous avons trouvé un cycle
        {
            /* Cycle trouvé */
        }
    }

MISE À JOUR

Correction trouvée pour ce code dans l'errata http://www.cs.sunysb.edu/~skiena/algorist/book/errata. Voir (*) Page 173, procédure process_edge -- le test correct devrait être

if (discovered[y] && (parent[x] != y)) { /* arête de retour trouvée */

Mais est-ce que cela détectera les cycles ?? La vérification if ne passera jamais car dans la méthode DFS, process_edge n'est appelée que lorsque discovered[y] == false.

Answer 1

Le code que vous avez posté présente des différences significatives par rapport à l'original de Skiena : bfs-dfs.c et findcycle.c et le reste. Le code de Skiena contient des bogues (essayez le graphe 3 2 1 2 2 3, un chemin à deux arêtes), donc peut-être que la personne qui l'a transcrit en Java a tenté des réparations. Malheureusement, la version réparée semble également comporter des bogues, bien que je ne puisse être certain sans un programme complet.

Je crois que l'intention de la ligne que vous avez soulignée était la suivante. Pour la recherche en profondeur dans les graphes non orientés, il existe deux types d'arêtes, arbre et retour. Le graphe contient un cycle si et seulement s'il existe une arête de retour. Maintenant, la représentation des graphes non orientés choisie par Skiena est de stocker chaque arête non orientée comme deux arcs dirigés, un dans chaque direction. Si nous utilisons la recherche en profondeur pour détecter les cycles dans ce graphe dirigé, alors les cycles de longueur deux constitués des deux arcs dirigés correspondant à une seule arête non orientée sont signalés par erreur comme des cycles. Tel qu'écrit, la vérification garantit qu'une arête de retour candidate y->x n'est pas l'inverse d'une arête d'arbre x->y.