Algorithme DFS (Depth First Search)

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¹).
• 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².

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² 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³

Phase d'exécution

tant_que i > arrayFirstIndex-1 faire
 
	//i n'est pas fermé, il existe des successeurs...
	si closedVertices[i] = false, alors
 
		/*i est l'indice de x, j est l'indice de y
		∃ y suivant de x, et non visité*/
		si ∃ y : (x,y) ∈ A ∧ visitedVertices[j]=false
 
			 visitedVertices[j] := true; //marquer y comme visité
			 k := k+1; //incrémenter le compteur de numéro d'ordre
			 verticesOrders[j] := k; //donner le numéro d'ordre au sommet y
 
			 //le sommet y a été atteint depuis le sommet x
			 previousVertices[j] :=i;
 
			 i := j; //le prochain sommet à traiter est y
		sinon
			//le sommet x est fermé, il ne reste plus rien à explorer sous lui
			closedVertices[i] := true;
	sinon
		//remonter au précédent s'il existe
		i := previousVertices[i]
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-1² 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.

Table des matières Haut

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"

Complexité

Au niveau de la complexité, les algorithmes DFS et BFS sont identiques (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.

You are on the French version of the site, but your system indicates that you prefer to use the English language.
The entire site is not translated yet, but the menus and buttons on the interface are largely translated.

Would you like to reach the page in English?
Click here to continue in English: Consult the English version of this page

U bevindt zich op de Franse versie van de site, maar uw systeem geeft aan dat u liever de Nederlandse taal gebruikt.
De hele site is nog niet vertaald, maar de menu's en knoppen op de interface zijn grotendeels vertaald.

Wilt u de pagina in het Nederlands bereiken?
Klik hier om door te gaan in het Nederlands: Raadpleeg de Nederlandse versie van deze pagina

Sie befinden sich in der französischen Version der Website, Ihr System gibt jedoch an, dass Sie die deutsche Sprache bevorzugen.
Die gesamte Site ist noch nicht übersetzt, aber die Menüs und Schaltflächen auf der Benutzeroberfläche sind weitgehend übersetzt.

Möchten Sie die Seite auf Deutsch erreichen?
Klicken Sie hier, um fortzufahren: Konsultieren Sie die deutsche Version dieser Seite