Discuter:Algorithme de parcours en profondeur

Un article de Wikipédia, l'encyclopédie libre.

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

• • • • • • • • • • • • • • • • • • ENSI Tunis *********Nidou01@yahoo.fr****

c'est pas complet pour le moment je suis entrain de préparer un exposé à ce sujet si vous pouvez apporter de l'aide allez y !!

[modifier] 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)