Discussion :

[Galet]

Bonjour à tous,
Je dois débuter une application destinée à traiter des graphes orientés et non cyclés. Ayant déjà traité du sujet, je n'ai pas de soucis concernant les 2 grands principes de parcours, en largeur ou en profondeur ainsi que leurs avantages et inconvénients (notamment les cycles).
Ma question : Y a-t-il des études comparatives entre les temps de traitements de ces 2 solutions (si, évidemment elles sont possibles) ? (Je n'ai encore rien trouvé sur le Web)
Merci par avance,
Belle journée à tous.

[Flodelarab]

Bonjour

Tu te rends bien compte que cela prend exactement le même temps car le nombre de nœuds est identique.

[edit] Ce n'est pas une question de performance, mais d'ordre de traitement. Attends, je donne un exemple. Si tu parcours un arbre généalogique avec les 2 parcours :

• Avec un parcours en largeur, tu pourras dire "jusqu'à telle génération, c'est fait ! Il reste à traiter les personnes les plus récentes.".
• Avec un parcours en profondeur, tu pourras dire "La branche de Jean-Louis, c'est fait ! Il reste celle de jacqueline, Louise et Pierrot.".

À la fin, le temps est le même.
[/edit]

[Galet]

Merci Flodelarab,
J'avais orienté ma question côté algo, plus que sur le nombre de sommets à traiter. Ton explication est donc parfaitement cohérente. La différence peut donc seulement provenir de l’efficacité du code utilisé pour les 2 parcours.
Une fois de plus, relever la tête du guidon et écouter de conseils avisés permet de gagner beaucoup de temps.
Belle journée à tous,