Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de parcours en largeur
Résumé
L'algorithme de parcours en largeur (ou BFS, pour Breadth-First Search en anglais) permet le parcours d'un graphe ou d'un arbre de la manière suivante : on commence par explorer un nœud source, puis ses successeurs, puis les successeurs non explorés des successeurs, etc. L'algorithme de parcours en largeur permet de calculer les distances de tous les nœuds depuis un nœud source dans un graphe non pondéré (orienté ou non orienté). Il peut aussi servir à déterminer si un graphe non orienté est connexe.
Un parcours en largeur débute à partir d'un nœud source. Puis il liste tous les voisins de la source, pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés. Les nœuds déjà visités sont marqués afin d'éviter qu'un même nœud soit exploré plusieurs fois. Dans le cas particulier d'un arbre, le marquage n'est pas nécessaire. Voici les étapes de l'algorithme :
mettre le nœud source dans la file ;
retirer le nœud du début de la file pour le traiter ;
mettre tous ses voisins non explorés dans la file (à la fin) ;
si la file n'est pas vide reprendre à l'étape 2.
L'algorithme de parcours en profondeur diffère du parcours en largeur car il continue l'exploration jusqu'à arriver dans un cul-de-sac. C'est seulement à ce moment-là qu'il revient en arrière pour explorer depuis un autre nœud voisin. L'utilisation d'une pile au lieu d'une file transforme l'algorithme du parcours en largeur en l'algorithme de parcours en profondeur.
Sur le graphe suivant, cet algorithme va alors fonctionner ainsi :
Il explore dans l'ordre les sommets A, B, C, E, D, F, G, contrairement à l'algorithme de parcours en profondeur qui cherche dans cet ordre : A, B, D, F, C, G, E.
L'algorithme s'implémente à l'aide d'une .
ParcoursLargeur(Graphe G, Sommet s):
f = CreerFile();
f.enfiler(s);
marquer(s);
tant que la file est non vide
s = f.defiler();
afficher(s);
pour tout voisin t de s dans G
si t non marqué
f.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.