Depth-first search

Depth-first search

Algorithme de parcours en profondeur

L'algorithme de parcours en profondeur (ou DFS, pour Depth First Search) est le principe qui s'abstrait de ce qu'on connait comme la façon simple de parcourir un labyrinthe sans tourner en rond. La pédagogie de l'informatique l'enseigne aujourd'hui volontiers en termes de parcours récursif d'un graphe quelconque.

Principe

C'est un algorithme de recherche qui progresse à partir d'un sommet S en s'appelant récursivement pour chaque sommet voisin de S.

Le nom d'algorithme en profondeur est dû au fait que, contrairement à l'algorithme de parcours en largeur, il explore en fait « à fond » les chemins un par un: pour chaque sommet, il prend le premier sommet voisin jusqu'à ce qu'un sommet n'ait plus de voisins (ou que tous ses voisins soient marqués), et revient alors au sommet père.

Si G n'est pas un arbre, l'algorithme pourrait tourner indéfiniment, c'est pour cela que l'on doit en outre marquer chaque sommet déjà parcouru, et ne parcourir que les sommets non encore marqués.

Enfin, on notera qu'il est tout à fait possible de l'implémenter itérativement à l'aide d'une pile LIFO contenant les sommets à explorer: on dépile un sommet et on empile ses voisins non encore explorés.

Implémentation récursive

DFS (graphe G, sommet s):
{
Marquer(S);
debut
POUR CHAQUE élément sfils de Voisin(s) FAIRE
   SI NonMarqué(sfils)
    ALORS DFS(G,sfils);
   FIN-SI
FIN-POUR
fin
}

Voisin(s) : renvoie la liste des sommets adjacents à s.

Marquer(Nœud ) : marque un nœud, de manière à ne pas le considérer plusieurs fois.

SousArbre(nœud u) : retourne le sous-arbre de racine u.

Exemple

Voyons concrètement le fonctionnement de cet algorithme sur le graphe suivant:

Graph.traversal.example.svg

L'algorithme DFS commence au sommet A, nous conviendrons que les sommets à gauche sur ce graphe seront choisis avant ceux de droite. Si l'algorithme utilise effectivement un marquage des sommets pour éviter de tourner indéfiniment en boucle, on aura alors l'ordre de visite suivant: A, B, D, F, E, C, G.

Supposons maintenant que nous n'utilisions pas la méthode de marquage, on aurait alors la visite des sommets suivants dans l'ordre: A, B, D, F, E, A, B, D, F, E, etc indéfiniment, puisque l'algorithme ne peut sortir de la boucle A, B, D, F, E et n'atteindra donc jamais C ou G.

Ou encore:

Profondeur(G,s)
 Pour chaque u dans N faire
   vu[u] := faux
 rp(G,s)

rp(G,u)
 vu[u] := vrai
 pour chaque arete (u,v) dans A faire
    si vu[v] := faux alors
       rp(G,v)

G=(N,A), N étant les sommets et A les arêtes d'un graphe et s un sommet de depart.

vu est un tableau de booléen vu[i] := vrai si et seulement si le sommet est accessible de s.

Ce document provient de « Algorithme de parcours en profondeur ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Depth-first search de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Depth-first search — Order in which the nodes are visited Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

  • Depth-First Search — Tiefensuche Tiefensuche (Depth First Search) ist in der Informatik ein Verfahren zum Suchen eines Knotens in einem Graphen. Sie zählt zu den uninformierten Suchalgorithmen. Eine Verbesserung der Tiefensuche ist die iterative Tiefensuche.… …   Deutsch Wikipedia

  • depth-first-search — paieška į gylį statusas T sritis informatika apibrėžtis ↑Paieškos medžio apėjimo būdas, kai pirma analizuojamas tam tikro mazgo ↑pomedis, o tada – neanalizuoti to paties lygio mazgai. atitikmenys: angl. depth first search ryšiai: dar žiūrėk –… …   Enciklopedinis kompiuterijos žodynas

  • Iterative deepening depth-first search — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • Depth-limited search — Class Search Algorithm Data structure Graph Worst case performance O( | V | + | E | ) …   Wikipedia

  • depth-first search — noun an algorithm for traversing a tree or graph where one starts at the root nad explores as far as possible along each branch before backtracking …   Wiktionary

  • Breadth-first search — Infobox Algorithm class=Search Algorithm Order in which the nodes are expanded data=Graph time=O(|V|+|E|) = O(b^d) space=O(|V|+|E|) = O(b^d) optimal=yes (for unweighted graphs) complete=yesIn graph theory, breadth first search (BFS) is a graph… …   Wikipedia

  • Search algorithm — In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer… …   Wikipedia

  • A* search algorithm — In computer science, A* (pronounced A star ) is a best first, graph search algorithm that finds the least cost path from a given initial node to one goal node (out of one or more possible goals). It uses a distance plus cost heuristic function… …   Wikipedia

  • Search for HMAS Sydney and German auxiliary cruiser Kormoran — A search for the wrecks of the Australian warship HMAS Sydney and the German merchant raider Kormoran , that sank each other during World War II, ended successfully in March 2008. On 19 November 1941, the two ships fought a battle in the Indian… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”