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

Algorithmes et structures de données Discussion :

Recherche cycle dans un arbre


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Expert confirmé
    Avatar de shawn12
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Avril 2006
    Messages
    3 368
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2006
    Messages : 3 368
    Par défaut Recherche cycle dans un arbre
    Bonsoir à tous
    Je voudrais rechercher un cycle dans un arbre
    J'ai une liste parent/enfant dans Excel. Comment dois-je faire pour détecter une boucle ?

  2. #2
    Membre émérite

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Par défaut
    Par définition un arbre ne possède pas de cycle. Il doit donc plutôt s'agir d'un graphe. Dans ce cas un simple parcours en largeur ou en profondeur permet de savoir s'il y a un cycle, en marquant les noeuds visités.

  3. #3
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Bonjour,

    par définition un arbre est connexe minimal et acyclique maximal. C'est-à-dire que si tu enlèves n'importe quelle liaison, ce n'est plus un arbre, car une partie est détachée et si tu ajoutes une liaison cela devient un graphe.
    Ca c'était pour la définition d'un arbre.

    Pour ce qui est de ton problème, je te conseille de faire une recherche récursive. Tu parcours tous les nœuds et le feuilles de l'arbre en les marquant. Si tu parcours quelque chose déjà marqué, c'est que tu n'as pas un arbre, mais un graphe.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  4. #4
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Par défaut
    Je te redis ce que j'avais dit hier. Tu parles de relation père/fils dans le fichier ce qui fait penser que tu as affaire à un graphe orienté et non à un arbre (graphe non orienté sans cycle). Ici tu parles de boucle, mais je pense que tu veux parler de cycle.

    Au début, tu dois constuire le graphe à partir du fichier Excel.

    Une méthode simple consiste à avoir une table d'association (genre table de hachage) qui contient en clef un sommet et en élément l'ensemble de ses enfants.

    Ceci se faisant simplement avec un algorithme du type :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    Map m : table d'association
    Pour chaque L ligne du fichier
       Si(m.get(L.parent) == null) 
           m.put(L.parent, nouvel ensemble);
       m.get(L.parent).ajouter(L.fils);
    Ensuite, tu as ton graphe entier et tu peux commencer le parcours de tous les sommets sur chaque sommet => il est possible d'être malin en retirant les sommets déjà visités pour éviter de reparcourir les sommets qui ont été inclus dans des parcours précédents.

    Pour chaque tentative, il faut mémoriser le sommet de départ et si tu tombes dessus, tu arrêtes => c'est qu'il y a eu un cycle.

  5. #5
    Membre Expert
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Par défaut
    Dans ce cas un simple parcours en largeur ou en profondeur permet de savoir s'il y a un cycle, en marquant les noeuds visités.
    Oui, mais il faut retirer le marquage quand tu quittes un chemin, sinon un simple parcours en profondeur avec marquage systématique ne permet que de savoir si tu as affaire à un arbre ou bien une forêt (un noeud partagé).

    Citation Envoyé par millie
    Pour chaque tentative, il faut mémoriser le sommet de départ et si tu tombes dessus, tu arrêtes => c'est qu'il y a eu un cycle.

  6. #6
    Expert confirmé
    Avatar de shawn12
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Avril 2006
    Messages
    3 368
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Finance

    Informations forums :
    Inscription : Avril 2006
    Messages : 3 368
    Par défaut
    Mon problème n'est pas en soit de construire un arbre ou un graphe.

    Je vous l'explique concrètement : j'ai une liste de programmes présentée de la manière suivante :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    APPELANT     APPELE
    2BSL201     0BDOSS
    2BSL201     2BSL204
    2BSL204     2BSL207
    2BSL207     2BSL201
    ....           ....
    Cette indique quels programmes sont appelés par un programme.

    Il faut que je trouve s'il y a un cycle : ici par exemple 2BSL201-->2BSL204-->2BSL207--->2BSL201

    Mais la liste peut etre longue.

    Si j'ai bien compris, il faut que je parcoure à partir de chaque appelant la liste de ses appelés puis ainsi de suite, récursivement, jusqu'à retomber sur un programme déjà parcouru ?

Discussions similaires

  1. [JTree]recherche dans un arbre (non binaire ?)
    Par biozaxx dans le forum Composants
    Réponses: 3
    Dernier message: 07/05/2013, 13h32
  2. Recherche de cycle dans un arbre de dépendances
    Par noooop dans le forum Shell et commandes GNU
    Réponses: 1
    Dernier message: 09/03/2010, 12h54
  3. Recherche dans un arbre généalogique en C++
    Par alcachofa dans le forum C++
    Réponses: 2
    Dernier message: 26/11/2006, 12h46
  4. Recherche dans un arbre-n-aires en C
    Par NThierry dans le forum C
    Réponses: 3
    Dernier message: 22/08/2006, 21h07
  5. Réponses: 4
    Dernier message: 17/10/2005, 14h23

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