Algorithme BFS (Breadth First Search)

Fonctionnalités de l'algorithme BFS

BFS est un algorithme de parcours de graphe par recherche en largeur d'abord (Breadth 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é.
Ne permet pas la détection de circuit (la version "stricte" n'utilise pas de tableau des précédents).
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 BFS

L'algorithme de recherche en largeur d'abord parcourt les sommets par "niveaux" dans l'arbre formé par le graphe. Le but est donc ici d'explorer tous les sommets suivants (enfants directs) d'un sommet donné, alors que DFS explore les sommets successeurs (du haut vers le bas, branche par branche). Nous n'avons donc pas de backtracking pour BFS, car nous ne devons jamais considérer le sommet précédent.

Inhoudsopgave Haut

Exemple de parcours BFS

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

$Légende$ $Graphes : animation BFS$

Inhoudsopgave Haut

Code de l'algorithme BFS

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)
orderedVertices : collection des indices des sommets. Notre algorithme place directement les sommets dans l'odre d'exploration.

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
i : indice dans notre collection de départ (X) du sommet parent en cours (sommet depuis lequel nous évaluons les suivants).
j : indice dans notre collection de départ (X) d'un des suivants du sommet dont l'index est i
parentVertex : indice dans le tableau orderedVertices du prochain sommet parent (sommet depuis lequel nous évaluerons les suivants).
vertexOrder : indice dans le tableau orderedVertices du premier emplacement libre.

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 //indice du premier sommet (en pratique, peut être initialisé avec n'importe quelle valeur car i prendra sa valeur dans orderedVertices)
parentVertex := i //Nous traiterons le premier sommet (racine)
vertexOrder := arrayFirstIndex //Nous plaçerons le premier sommet au premier emplacement de libre de vertexOrder.
visitedVertices[arrayFirstIndex] := 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
orderedVertices[arrayFirstIndex] := i //le sommet courant est le premier
∀(j ≠ arrayFirstIndex) : orderedVertices[j] := -1 //Valeur hors des indices possibles du tableau, ce qui signifie qu'il ne s'agit pas de l'indice d'un sommet existant

∀j : previousVertices[j] := -1 //Valeur hors des indices possibles du tableau, ce qui signifie l'absence de sommet précédent.

Phase d'exécution

Code (Pseudo-code de BFS) (28 lignes)

//si parentVertex > vertexOrder, nous avons visité tous les sommets
tant_que vertexOrder &ge; parentVertex faire
 
	/* initialisation du sommet courant, et on sait
	que visitedVertices[i]=true car il est marqué comme visité
	AVANT d'être placé dans orderedVertices */
	i := orderedVertices[parentVertex];
 
	//parentVertex pointe maintenant sur le prochain sommet à évaluer
	parentVertex := parentVertex+1;
 
	/* i est l'indice de x, j est l'indice de y
	∃ y suivant de x, et non visité
	cette boucle stocke tous les sommets d'un même niveau */
	tant_que ∃ y : (x,y) ∈ A ∧ visitedVertices[j]=false
 
		//marquer y comme visité
		visitedVertices[j] := true;
 
		//pointer vers l'indice suivant dans orderedVertices
		vertexOrder := vertexOrder+1;
 
		//stocker l'indice du sommet
		orderedVertices[vertexOrder] := j;
 
	fin tant_que
 
fin tant_que

Retourner au début du code

Version alternative : Ajout de la ligne 21 pour retrouver le précédent.

Code (Pseudo-code de BFS avec mémorisation des précédents) (31 lignes)

//si parentVertex > vertexOrder, nous avons visité tous les sommets
tant_que vertexOrder &ge; parentVertex faire
 
	/* initialisation du sommet courant, et on sait
	que visitedVertices[i]=true car il est marqué comme visité
	AVANT d'être placé dans orderedVertices */
	i := orderedVertices[parentVertex];
 
	//parentVertex pointe maintenant sur le prochain sommet à évaluer
	parentVertex := parentVertex+1;
 
	/* i est l'indice de x, j est l'indice de y
	∃ y suivant de x, et non visité
	cette boucle stocke tous les sommets d'un même niveau */
	tant_que ∃ y : (x,y) ∈ A ∧ visitedVertices[j]=false
 
		//marquer y comme visité
		visitedVertices[j] := true;
 
		//le sommet j a été atteint depuis le sommet i
		previousVertices[j] := i;
 
		//pointer vers l'indice suivant dans orderedVertices
		vertexOrder := vertexOrder+1;
 
		//stocker l'indice du sommet
		orderedVertices[vertexOrder] := j;
 
	fin tant_que
 
fin tant_que

Retourner au début du code

Ordre d'exploration et tableau orderedVertices

Selon notre implémentation, le tableau orderedVertices contient les indices des sommets de X, naturellement trié selon l'ordre de découverte des sommets.

Si nous désirons travailler comme pour notre algorithme DFS, il nous pouvons remplacer orderedVertices[vertexOrder] := j; par orderedVertices[j] := vertexOrder; (ligne 24 27). Nous devrons ensuite modifier la ligne 10 pour que parentVertex pointe sur le premier des suivants de i au lieu d'une incrémentation.
Dans ce cas, le tableau est trié (comme les autres tableaux) dans l'ordre des indices des sommets dans X, et contient pour chaque indice le numéro d'ordre du sommet correspondant.

Remarques

Dans le cas d'une implémentation avec arrayFirstIndex = 0, nous devons remplacer ≥ par > dans la comparaison entre vertexOrder et parentVertex (ligne 2).

L'instruction de la ligne 21 n'est pas strictement nécessaire car BFS ne nécessite pas de mémoriser quel est le sommet précédent. Dans ce cas, l'initialisation ∀j : previousVertices[j] := -1 n'est pas nécessaire non plus.

Inhoudsopgave Haut

Comparaison BFS DFS

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 (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 09/03/2020 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/graphes-bfs.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

↑ 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

Inhoudsopgave Haut

Referenties

INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)
Wikipedia : Wikipedia, Shortest paths in graphs (version 13/12/09)
Parcours en largeur : Université Pierre Mendes Françe - Grenoble, Parcours en largeur + applet Java

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