#098 / 100•Space, Chance & Computation•MathTCG #498 / 500•★Commune•⊦Maths Discrètes•Méthode & Idée
Parcours en largeur
Période historique : 1959
Breadth-First Search (BFS) : exploration niveau par niveau d'un graphe utilisant une file FIFO.
Contenu & Formulation mathématique
Principe de la démarche
Breadth-First Search (BFS) : exploration niveau par niveau d'un graphe utilisant une file FIFO.
Champs d'application canoniques
Démonstration mathématique
Genèse & Portée historique
Algorithme fondamental de parcours explorant d'abord tous les voisins directs d'un sommet source avant de passer aux voisins des voisins. Dans un graphe non pondéré, le BFS calcule de façon optimale en O(V + E) les plus courts chemins en nombre d'arêtes.
Edward F. Moore l'a inventé en 1959 pour trouver le plus court chemin de sortie dans un labyrinthe électrique.
« Comme une onde circulaire sur l'eau, le front d'exploration gagne pas à pas toute la périphérie. »
Filiations & Relations conceptuelles (1)
Objet de collection MathTCG
#498
★Commune
⊦
Parcours en largeur
Maths Discrètes•MÉTHODE
Principe : Breadth-First Search (BFS) : exploration niveau par niveau d'un graphe utilisant une file FIFO.
1959
Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.
Extension : Space, Chance & Computation (#098 / 100)
Numéro global MathTCG : MathTCG #498 / 500
Rareté officielle : Commune (★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : parcours-en-largeur