« Algorithme de parcours en largeur » : différence entre les versions
m (Remplacement de texte : « ↵↵<small> » par « ==Sources== ») |
m (Remplacement de texte : « ↵↵↵ » par « ») |
||
| Ligne 11 : | Ligne 11 : | ||
* [https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur Sourc : Wikipedia IA, ''Algorithme de parcours en largeur''.] | * [https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur Sourc : Wikipedia IA, ''Algorithme de parcours en largeur''.] | ||
Version du 29 janvier 2024 à 10:24
Définition
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.
Français
algorithme de parcours en largeur
Anglais
Breadth First Search
Sources
Contributeurs: Evan Brach, Jacques Barolet, Patrick Drouin, wiki
