Keine Cache-Version

Caching deaktiviert Standardeinstellung für diese Seite:aktiviert (code LNG204)
Wenn die Anzeige zu langsam ist, können Sie den Benutzermodus deaktivieren, um die zwischengespeicherte Version anzuzeigen.

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)

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

Inhaltsverzeichnis 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

Inhaltsverzeichnis 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+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. := j; //le prochain sommet à traiter est y
  18. //le sommet x est fermé, il ne reste plus rien à explorer sous lui
  19. closedVertices[i] := true;
  20. //remonter au précédent s'il existe
  21. := 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-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.

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

Deutsche Übersetzung

Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.

Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.

Vielen Dank im Voraus.

Dokument erstellt 13/12/2009, zuletzt geändert 26/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/graphes-dfs.html

Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.

Aufzeichnungen

  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

Inhaltsverzeichnis Haut

Referenzen

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

Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.

Inhaltsverzeichnis Haut