IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Récupérer les sommets constituant un cycle d'un graphe orienté


Sujet :

C++

  1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Novembre 2014
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Novembre 2014
    Messages : 2
    Points : 3
    Points
    3
    Par défaut Récupérer les sommets constituant un cycle d'un graphe orienté
    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

  2. #2
    Expert éminent sénior
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Février 2005
    Messages
    5 210
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Conseil

    Informations forums :
    Inscription : Février 2005
    Messages : 5 210
    Points : 12 381
    Points
    12 381
    Par défaut
    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.

  3. #3
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Novembre 2014
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Novembre 2014
    Messages : 2
    Points : 3
    Points
    3
    Par défaut
    En effet, votre solution est meilleure et fonctionnel.

    Merci de votre aide !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [Google Maps] Récupérer les points constituant un GPolygon
    Par aurelientp dans le forum APIs Google
    Réponses: 2
    Dernier message: 19/01/2010, 18h00
  2. Récupérer les mails Outlook dans une table Access
    Par zerrokooll dans le forum VBA Access
    Réponses: 79
    Dernier message: 07/07/2009, 15h22
  3. Réponses: 2
    Dernier message: 13/11/2003, 16h13
  4. Comment récupérer les adresses WWW dans Internet Explorer ?
    Par chaours dans le forum Web & réseau
    Réponses: 7
    Dernier message: 03/09/2003, 15h27
  5. Réponses: 4
    Dernier message: 04/07/2003, 20h13

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo