Discussion:Algorithme de parcours en profondeur

Il existe deux techniques extrémes d’exploration d’un arbre de recherche: la recherche en profondeur-d’abord (Depth First Search, ou DFS) et la recherche en largeurd’abord (Breadth First Search, ou BFS). La premi`ere tente d’atteindre la solution le plus vite possible en explorant imm´ediatement les successeurs de tout noeud g´en´er´e, alors que la seconde ´etend l’arbre en g´en´erant les noeuds couche par couche.

*********************
1. Function Recherche-DFS(Noeud-initial)
2. Q ← Noeud-initial
3. loop
4. if Q est vide then return ECHEC
5. n ← first(Q) , Q ← rest(Q)
6. if n est un noeud but then return n
7. S ← successeurs de n (obtenu par application de
toutes les r`egles possibles)
8. Q ← append(S,Q)
9. end
*******************************************************

Boucle dans l'exemple ?

N'y a-t-il pas un problème avec l'exemple ? Dans un graphe orienté, l'algorithme n'est pas censé remonter les arcs en sens inverse. Je ne vois donc pas pourquoi il boucle en remontant de F vers E puis de E vers A. Pour moi, la séquence de parcours dans le second cas serait plutôt A, B, D, F, C, G, E, F - ce qui a un sens, par exemple, dans le cas d'un calcul de flux total.

A moins évidemment que l'on ne considère que le graphe d'exemple est non orienté, auquel cas le schéma me parait faux.

Mithfindel 21 décembre 2006 à 11:55 (CET)

La notion même

Il y a quelque chose de gênant à exposer DFS en termes uniquement de graphes, c'est de l'ordre d'un jargon propre à un choix pédagogique pour l'enseignement de l'informatique, avec un pari sur l'abstraction qu'on pourrait dire bourbakien ou bourbakiesque. Et ça se trouve déjà dans l'équivalence affirmée de "algorithme de parcours" et "search", on parcourt sans se connaître de motivation, alors que quand on cherche c'est pour trouver quelque chose.

Si l'on ne veut pas aller à dire que ça se situe en informatique dans une problématique générale qui sera typiquement de construire progressivement la représentation complète d'une solution à un problème qui s'exprime comme une contrainte sur des représentations, qu'on dise alors au moins quelque chose de simple qui donne l'essentiel du principe.

Dijkstra

Il y a un point que je ne comprends pas, c'est la différence entre l'algorithme de parcours en profondeur et l'algorithme de Dijkstra. Dans l'algo de Dijkstra, les points sont pondérés par deux valeurs différentes de la valeur initiale d'un point, alors que dans l'algorithme de parcours en profondeur, il n'y a qu'une seule valeur (hors initiale). Est-ce que tous les voisins d'un point sont insérés dans la liste des points à visiter au même instant, et qu'on intercale les points supplémentaires entre-temps, ou est-ce qu'on remonte le chemin? Mithfindel, je ne crois pas que la hauteur d'une lettre pondère son ordre. De ce fait, si l'algorihme passe d'abord vers B, le deuxième cas est celui indiqué dans l'article. Mais si l'algorithme commence par A, F... Alors c'est ton cas de figure qui va arriver.

--Benobit (d) 6 janvier 2010 à 21:04 (CET)

Le parcours en profondeur prend en entrée un graphe orienté. Il ne tient pas compte des poids s'il y en a.--Fschwarzentruber (discuter) 29 mai 2016 à 11:23 (CEST)

Infix, postfix etc..

Il me semble qu'il manque une notion dans l'article (et une ligne correspondante dans l'algorithme). On parcours un arbre - généralement - pour effectuer une action sur chaque sommet. En fonction de l'emplacement de Action(s) (qui manque) dans l'algorithme récursif, au début, dans la boucle, ou à la fin, on a un parcours prefix, infix ou postfix. Est-ce pertinent d'en parler dans cet article ? Il me semble que oui, un parcours sans action me semble complètement désincarné et on manque cette notion importante. --Jean-Christophe BENOIST (discuter) 20 avril 2016 à 18:00 (CEST)

Liens externes modifiés

Bonjour aux contributeurs,

Je viens de modifier 1 lien(s) externe(s) sur Algorithme de parcours en profondeur. Prenez le temps de vérifier ma modification. Si vous avez des questions, ou que vous voulez que le bot ignore le lien ou la page complète, lisez cette FaQ pour de plus amples informations. J'ai fait les changements suivants :

• L'archive https://web.archive.org/web/20150209205532/http://www.numdam.org/numdam-bin/fitem?id=NAM_1895_3_14__187_1 a été ajoutée à http://www.numdam.org/numdam-bin/fitem?id=NAM_1895_3_14__187_1

SVP, lisez la FaQ pour connaître les erreurs corrigées par le bot.

Cordialement.—InternetArchiveBot (Rapportez une erreur) 9 mai 2018 à 00:05 (CEST)