Algorithme DFS (Depth First Search)

Contents

Fonctionnalités de l'algorithme DFS

  • DFS est un algorithme de parcours de graphe par recherche en profondeur d'abord (Depth First Search).
  • Fonctionne avec les graphes orientés et non-orientés.
  • Permet la détection de cycle si on considère le graphe non-orienté.
  • Permet la détection de circuit
  • Permet la détection de Composantes Simplement Connexes si il reste des sommets non traités après un premier passage (plus rapide en pratique que l'algorithme de Warshall si nous avons une seule cfc)

Contents Haut

Caractéristiques de l'algorithme DFS

Comme l'indique son nom, l'algorithme de recherche en profondeur d'abord démarre de la racine, explore le premier chemin de ses successeurs (une branche de l'arbre du haut vers le bas) jusqu'au moment ou le sommet n'a plus de successeurs non visités. Ensuite il remonte d'un niveau pour vérifier s'il ne reste pas de sommets à visiter (si il ne reste plus de sommets candidats, nous fermons alors le sommet courant), et ainsi de suite.

Le fait de "marquer" un sommet pour savoir s'il a déjà été visité permet d'éviter de rentrer dans une boucle infinie, et d'éviter d'emprunter inutilement certains chemins. Nous marquons aussi chaque sommet comme "ouvert" ou "fermé" pour savoir s'il subsiste des sommets à explorer dans l'ensemble des successeurs.

Si notre graphe est simplement connexe mais ne possède pas de racine, nous pouvons ajouter un sommet que nous relions à chaque sommet qui ne possède pas de précédent (candidat racine d'une composante simplement connexe). Nous avons donc une racine unique. Un autre moyen plus souvent utilisé est de re-démarrer l'algorithme DFS à chaque fois qu'il s'arrête et qu'il reste des sommets non fermés.

Contents Haut

Exemple de parcours DFS

L'exemple suivant illustre l'algorithme DFS en action. Les sommets sont numérotés dans l'ordre d'exploration DFS.

Légende Graphes : animation DFS

Contents Haut

Code de l'algorithme DFS

Nous pouvons décomposer notre algorithme en deux phases : une phase d'initialisation des valeurs, et une phase d'exécution qui décrit ce qui se passe lorsque l'algorithme est exécuté.

La phase d'exécution décrit comment traiter un sommet.

Variables

Dans cette approche, nous utilisons des collections indexées (par exemple des tableaux) pour maintenir les différentes informations relatives aux états de chaque objet Sommet. Dans une approche "orienté-objet", nous pouvons maintenir ces informations par exemple dans l'objet Sommet lui même.

  • visitedVertices : collection de booléens (true si nous sommes déjà passés par ce sommet)
  • closedVertices : collection de booléens (true si nous sommes déjà passés par ce sommet et par tous ses successeurs1).
  • verticesOrders : collection qui maintient pour chaque sommet son numéro d'ordre de parcours
  • previousVertices : collection qui maintient pour chaque sommet le numéro d'ordre du sommet précédent

Nous utiliserons aussi certaines variables supplémentaires :

  • X est l'ensemble des sommets du graphe.
  • A est l'ensemble des arcs du graphe.
  • k : compteur qui indique le dernier numéro d'ordre attribué à un sommet. Il ne sert qu'à l'affichage.
  • i : indice du sommet courant

arrayFirstIndex : indice du premier élément dans un tableau2.

Phase d'initialisation

Nous devons initialiser les tableaux avec une taille correspondant à n.

Nous emploierons ∀j pour raccourcir la notation ∀(j ≥ arrayFirstIndex) ∧ (j < n+arrayFirstIndex), ce qui signifie pour tout emplacement du tableau.

  • i := arrayFirstIndex //Le sommet en cours est le premier (racine)
  • visitedVertices[i] := true //Puisque nous sommes positionnés sur le premier sommet, il est déjà visité
  • ∀(j ≠ arrayFirstIndex) : visitedVertices[j] := false //Tous les sommets qui suivent le premier sont non visités
  • ∀j : closedVertices[j] := false //Tous les sommets sont non fermés
  • ∀j : previousVertices[j] := arrayFirstIndex-1 //Comme arrayFirstIndex-1 est un indice qui n'existe pas dans le tableau, nous l'utilisons pour signifier l'absence de précédent2 De toute manière, previousVertices[i] ne sera pris en compte que si visitedVertices[i]=true.
  • k := 1 //Initialisation du compteur avec le premier numéro
  • verticesOrders[i] := k //Nous attribuons le numéro 1 au premier sommet
  • ∀(j ≠ arrayFirstIndex) : verticesOrders[j] := 0 //Initialisation des valeurs suivantes du tableau3

Phase d'exécution

  1. tant_que i > arrayFirstIndex-1 faire
  2.  
  3. 	//i n'est pas fermé, il existe des successeurs...
  4. 	si closedVertices[i] = false, alors
  5.  
  6. 		/*i est l'indice de x, j est l'indice de y
  7. 		∃ y suivant de x, et non visité*/
  8. 		si ∃ y : (x,y) ∈ A ∧ visitedVertices[j]=false
  9.  
  10. 			 visitedVertices[j] := true; //marquer y comme visité
  11. 			 k := k+1; //incrémenter le compteur de numéro d'ordre
  12. 			 verticesOrders[j] := k; //donner le numéro d'ordre au sommet y
  13.  
  14. 			 //le sommet y a été atteint depuis le sommet x
  15. 			 previousVertices[j] :=i;
  16.  
  17. 			 i := j; //le prochain sommet à traiter est y
  18. 		sinon
  19. 			//le sommet x est fermé, il ne reste plus rien à explorer sous lui
  20. 			closedVertices[i] := true;
  21. 	sinon
  22. 		//remonter au précédent s'il existe
  23. 		i := previousVertices[i]
  24. fin tant_que

L'exécution de l'algorithme DFS se termine lorsque nous remontons à la racine (sommet 1) et que tous les successeurs de la racine sont fermés. Dans ce cas, le précédent de la racine étant un sommet fictif (arrayFirstIndex-12 dans previousVertices), nous ne pouvons plus satisfaire la condition de la boucle (voir ligne 1).

Si à ce moment il reste des sommets de X qui ne sont pas visités, nous sommes en présence de plus d'une composante simplement connexe. Dans ce cas, nous devons "relancer" l'algorithme DFS depuis un sommet de X non visité et qui ne possède pas de précédent.

Contents Haut

Algorithme DFS orienté objet

Au lieu de mémoriser des ensembles de valeurs qui correspondent à différents états pour chaque sommet, nous pouvons utiliser un algorithme DFS orienté objet, en spécifiant que la responsabilité de maintenir les différentes données relatives à un sommet revient au sommet lui-même.

Par exemple, nous pouvons avoir une classe DFSVertex qui étend la classe GraphVertex en ajoutant les différentes informations nécessaires.

Variables

Pour chaque sommet, nous devrons mémoriser un certain nombre de données. Ces données sont initialisées à la création du DFSVertex.

  • visited : true si nous sommes déjà passés par ce sommet lors de notre exploration du graphe.
  • closed : true si "visited" est true, et que "visited" est true pour tous les successeurs.
  • previous :
    • vide si "visited" est false
    • identification du sommet précédent si "visited" est true
  • ordrer : numéro de marquage (correspond à l'ordre d'exploration des sommets)

Comparaison DFS BFS

Nous pouvons observer pour un même graphe les différences entre le parcours DFS et le parcours BFS. Les sommets sont marqués dans l'ordre d'exploration.

Ordre d'exploration

Dans le cas de DFS, les sommets sont explorés dans l'arbre "de haut en bas", alors que pour BFS ils sont explorés "par niveaux"

Graphes : Parcours DFS Graphes : Parcours BFS

Complexité

Au niveau de la complexité, les algorithmes DFS et BFS sont identiques Ordre de grandeur(m) car chaque arc n'est évalué qu'une seule fois. Ils diffèrent seulement par leur mode opératoire.

Implémentation

Les propos suivants s'appliquent aux implémentations que nous avons vu pour les algorithmes DFS et BFS, mais il existe de nombreuses autres implémentations qui respectent les caractéristiques de ces algorithmes.

Dans le cas de notre implémentation DFS, nous devons utiliser un numéro d'ordre pour les sommets. Nous pouvons trouver le numéro d'ordre d'un sommet en consultatnt le tableau verticesOrders à l'indice correspondant au sommet en question.
Notre implémentation de l'algorithme BFS, au contraire utilise un tableau orderedVertices pour lequel les indices correspondent au numéro d'ordre, et les valeurs correspondent aux indices des sommets.

Notre implémentation de DFS utilise un tableau de booléens closedVertices pour signaler qu'un sommet est visité et qu'il ne reste aucun sommet non visité depuis ce dernier. Ceci n'est pas nécessaire dans BFS car nous utilisons une comparaison d'indices.

English translation

You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.

If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.

Thank you in advance.

Document created the 13/12/2009, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/graphes-dfs.html

The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.

Notes
  1. ↑ Sommet fermé : closedVertices[i] = ( visitedVertices[i] == true ) ∧ ( visitedVertices[j] == true ∀ j successeur de i)

  2. ↑a,b,c arrayFirstIndex : Ce n'est pas à proprement parler une variable, mais cela me permet d'éviter d'écrire 0 ou 1 dans le pseudo-code de l'algorithme selon le type de langage utilisé.
    Selon l'implémentation choisie, la collection utilisée peut démarrer son indexation à 0 (ex : tableau en Java) ou à 1 (ex : tableau en Pascal). Par exemple, en Java nous initialisons avec ∀i : previousVertices[i] = 0

  3. ↑ ∀j : verticesOrders[j] := 0 : Cette initialisation n'est pas nécessaire dans certains langages si nous utilisons des types primitifs comme les int qui sont par défaut initialisés avec la valeur 0

Contents Haut

References

  1. book Language of the document:fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)
  2. View the html document Language of the document:uk Wikipedia : Wikipedia, Depth-first search (version 13/12/09)
  3. View the html document Language of the document:uk Breadth first search and depth first search ICS 161 : University of California - IRVINE, Design and Analysis of Algorithms Lecture notes for February 15, 1996 (version 13/12/09)
  4. View the html document Language of the document:fr Parcours en profondeur : Université Pierre Mendes Françe - Grenoble, Parcours en profondeur + applet Java
  5. View the html document Language of the document:uk Graph Theory Applet : Rensselaer Polytechnic Institute, Démonstration interactive par applet Java (version 28/12/09)

These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.

Contents Haut