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 ?
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 ?
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.
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.
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 :
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.
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);
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.
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é).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.
Envoyé par millie
![]()
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 :
Cette indique quels programmes sont appelés par un programme.
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 .... ....
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 ?
Partager