Algorithme de parcours en profondeur

L'algorithme de parcours en profondeur (ou DFS, pour Depth First Search) est un algorithme de parcours de graphe qui se décrit naturellement de manière récursive. Son application la plus simple consiste à déterminer s'il existe un chemin d'un sommet à un autre.

Pour les graphes non orientés, il correspond à la méthode intuitive qu'on utilise pour trouver la sortie d'un labyrinthe sans tourner en rond.

Sommaire

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.

Dans le cas d'un arbre, le parcours en profondeur est utilisé pour caractériser l'arbre.

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

Initialement, aucun sommet n'est marqué.

DFS (graphe G, sommet s)
{
  Marquer(s);
  POUR CHAQUE élément s_fils de Voisins(s) FAIRE
     SI NonMarqué(s_fils) ALORS
       DFS(G,s_fils);
     FIN-SI
  FIN-POUR
}

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

Marquer(s) : marque un sommet s comme exploré, de manière à ne pas le considérer plusieurs fois.

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.

Applications

Comme les autres algorithmes de parcours de graphe, l'algorithme de parcours en profondeur trouve l'ensemble des sommets accessibles depuis un sommet donné s, c'est-à-dire ceux vers lesquels il existe un chemin partant de s. Il s'agit précisément des sommets marqués par l'algorithme. Ceci s'applique à un graphe orienté ou non orienté. Sur un graphe non orienté, on peut utiliser cette propriété pour le calcul des composantes connexes.

Dans le cas d'un graphe orienté acyclique, le parcours en profondeur peut servir à calculer un tri topologique des sommets.

L'algorithme de Kosaraju (en) effectue un double parcours en profondeur pour calculer les composantes fortement connexes d'un graphe orienté quelconque.

Voir aussi


Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • Algorithme De Parcours En Largeur — Pour les articles homonymes, voir BFS. L algorithme de parcours en largeur (ou BFS, pour Breadth First Search) permet le parcours d un graphe de manière itérative, en utilisant une file. Il peut par exemple servir à déterminer la connexité d un… …   Wikipédia en Français

  • Algorithme de parcours en largeur — Pour les articles homonymes, voir BFS. L algorithme de parcours en largeur (ou BFS, pour Breadth First Search) permet le parcours d un graphe de manière itérative, en utilisant une file. Il peut par exemple servir à déterminer la connexité d un… …   Wikipédia en Français

  • Algorithme de recherche en faisceau — En informatique, la recherche en faisceau est un algorithme de recherche heuristique qui explore un graphe en ne considérant qu un ensemble limité de fils de chaque nœud. La recherche en faisceau est une optimisation de l algorithme de parcours… …   Wikipédia en Français

  • Algorithme de Tarjan — En théorie des graphes, l algorithme de Tarjan permet de déterminer les composantes fortement connexes d un graphe orienté[1]. Il porte le nom de son inventeur, Robert Tarjan. L algorithme de Tarjan est de complexité linéaire, comme l algorithme… …   Wikipédia en Français

  • Algorithme de Tremaux — Modélisation mathématique d un labyrinthe Une approche mathématique permet la génération de labyrinthes modernes. Les labyrinthes peuvent être modélisés dans un espace multi dimensionnel, les plus courants étant les labyrinthes en deux dimensions …   Wikipédia en Français

  • Algorithme de Trémaux — Modélisation mathématique d un labyrinthe Une approche mathématique permet la génération de labyrinthes modernes. Les labyrinthes peuvent être modélisés dans un espace multi dimensionnel, les plus courants étant les labyrinthes en deux dimensions …   Wikipédia en Français

  • Parcours (graphe) — Pour les articles homonymes, voir Parcours (homonymie).  Pour l’article homophone, voir parkour. En théorie des graphes, un parcours de sommets (resp. d arêtes, d arcs) dans un graphe G est une liste ordonnée de sommets (resp. d arêtes, d… …   Wikipédia en Français

  • Parcours de graphe —  Pour l’article homophone, voir parkour. En théorie des graphes, un parcours de graphe est un algorithme consistant à explorer les sommets d un graphe de proche en proche à partir d un sommet initial. Le mot parcours est également utilisé… …   Wikipédia en Français

  • Algorithmes De Connexité Basés Sur Des Pointeurs — Les algorithmes de connexité suivants permettent de déterminer rapidement si deux sommets d un graphe non orienté sont reliés par un chemin ou non, en créant un tableau de pointeurs qui implémente en fait une forêt d arbres. Chaque arbre créé par …   Wikipédia en Français

Share the article and excerpts

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