BFS (Breadth-First Search) est une méthode de parcours de graphe, très souvent utilisée dans les algorithmes simples et avancés. La recherche étendue d'abord fonctionne en parcourant les niveaux individuels du graphique, en commençant par le nœud source et en s'en éloignant progressivement. Ceci est clairement montré dans l'animation.
Pour écrire un BFS simple, vous devez être capable de travailler avec une file d'attente, une structure de données qui vous permet de prendre du début et de la mettre à la fin, et également de pouvoir stocker un graphique sous la forme d'une liste de contiguïté.
Description formelle de l'algorithme
1) Placer le numéro du sommet à partir duquel la recherche commence dans la file d'attente initialement vide.
2) Extrayez le sommet U du début de la file d'attente et marquez-le comme utilisé dans un tableau séparé.
3) A la fin de la file d'attente, ajouter tous les sommets que l'on peut atteindre en utilisant l'arête du sommet U et qui ne sont pas encore marqués.
4) Si la file d'attente est vide, alors tous les nœuds du graphe connexe ont été scannés, sinon retournez à l'étape 2.
Difficulté de travail
Puisque, dans le pire des cas, l'algorithme visite tous les nœuds du graphe, lors du stockage du graphe sous forme de listes d'adjacence, la complexité temporelle de l'algorithme est O(|V| + |E|), où V est l'ensemble des sommets du graphe, et E est l'ensemble des arêtes. ;
En d'autres termes, l'algorithme fonctionne dans le pire des cas pour le nombre d'arêtes + le nombre de sommets.