Discussion :

[Carambar299]

Bonjour à tous !

Actuellement, je tente de récupérer sous la forme d'une liste (en utilisant std::list), tous les sommets constituant un cycle dans un graphe orienté.

J'ai donc tout d'abord détecté si le graphe comportait un cycle et il y'en a bien un.

Pour faire cette détection, j'ai dans la classe ci-dessous, la méthode "dfs" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template<typename GraphType>class DirectedCycle {
        typedef GraphType Graph;
 
    private:
        const Graph& g;
 
        std::vector<bool> onStack, marked;
        bool hasCycle;  
        std::list<int> cycle;
 
        void dfs(int v){    
            onStack.resize(g.V());
            marked.resize(g.V());
            onStack[v] = true;
            marked[v] = true;
 
            for(int w : g.adjacent(v)) {
                if (hasCycle)
                    return;
 
                if(!marked[w]) {
                    // cycle.push_back(w);
                    dfs(w);
                }
 
                else if (onStack[w]) {
                    hasCycle = true;
                }
            }
            onStack[v] = false;
        }

Et j'ai essayé d'intégrer directement le push_back de la liste dans ma fonction de détection (afin de ne pas reparcourir le graphe pour afficher les sommets qui sont dans le cycle), mais en vain.

Comment faire pour récupérer ses sommets ? Suis-je obligé de reparcourir le grahe dans une autre méthode ?
Je ne comprends pas pourquoi cela ne marche pas... Quelqu'un saurait l'expliquer ?

je suis sur netbeans IDE 8.0.1

Merci de vos réponse

[bacelar]

Très alambiqué votre truc.

dfs devrait retourner un booléen pour indiquer si un cycle a été trouvé ou le cycle lui-même.
Il suffit de faire un simple parcours en profondeur d'abord.
Le chemin sera celui correspondant à la stack au moment de la découverte.

[Carambar299]

En effet, votre solution est meilleure et fonctionnel.

Merci de votre aide !