Algorithme DFS (Depth First Search)

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)

 

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.

 

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égendegraphes dfs

 

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 successeurs[1]).
  • 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 tableau[2].

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édent[2] 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 tableau[3]

Phase d'exécution


Code (Pseudo-code de DFS) (24 lignes) :
  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 ;: (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.     //remonter au précédent s'il existe
  22.     i ;:= previousVertices[i]

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-1[2] 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.

 

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.

 

Document créé le 13/12/09 17:21, dernière modification le 28/08/17 14:04
Source du document imprimé : https://www.gaudry.be/graphes-dfs.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.

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

 

Références

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

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.