Algorithme DFS (Depth First Search)

Inhoudsopgave

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)

Inhoudsopgave 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.

Inhoudsopgave 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

Inhoudsopgave 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.

Inhoudsopgave 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.

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 13/12/2009 gemaakt, de laatste keer de 26/10/2018 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/graphes-dfs.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de 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

Inhoudsopgave Haut

Referenties

  1. boek Taal van het document:fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)
  2. Bekijk - html-document Taal van het document:uk Wikipedia : Wikipedia, Depth-first search (version 13/12/09)
  3. Bekijk - html-document Taal van het 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. Bekijk - html-document Taal van het document:fr Parcours en profondeur : Université Pierre Mendes Françe - Grenoble, Parcours en profondeur + applet Java
  5. Bekijk - html-document Taal van het document:uk Graph Theory Applet : Rensselaer Polytechnic Institute, Démonstration interactive par applet Java (version 28/12/09)

Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.

Inhoudsopgave Haut