Metraipolis › archive › dc_8ec0d762e302
Breadth-first search — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Breadth-first_search
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-31T08:09:41.236Z
- SHA-256 of the archived text
de7b2b2a424e6ab5912b944467876b4a39dca6b6cda8dd332c6f3cdda291baf0- Stable URL of this page
https://metraipolis.com/documento/dc_8ec0d762e302
How to cite
Breadth-first search — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Breadth-first_search (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_8ec0d762e302 (Metraipolis archive dc_8ec0d762e302, sha256 de7b2b2a424e6ab5912b944467876b4a39dca6b6cda8dd332c6f3cdda291baf0)
BibTeX
@misc{dc8ec0d762e302,
title = {Breadth-first search — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Breadth-first_search},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_8ec0d762e302; sha256 de7b2b2a424e6ab5912b944467876b4a39dca6b6cda8dd332c6f3cdda291baf0},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Breadth-first_search. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In computer science, breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored. For example, in a chess endgame, a chess engine may build the game tree from the current position by applying all possible moves and use breadth-first search to find a winning position for White. Implicit trees (such as game trees or other problem-solving trees) may be of infinite size; breadth-first search is guaranteed to find a solution node if one exists. In contrast, (plain) depth-first search (DFS), which explores the node branch as far as possible before backtracking and expanding other nodes, may get lost in an infinite branch and never make it to the solution node. Iterative deepening depth-first search avoids the latter drawback at the price of exploring the tree's top parts over and over again. On the other hand, both depth-first algorithms typically require far less extra memory than breadth-first search. Breadth-first search can be generalized to both undirected graphs and directed graphs with a given start node (sometimes referred to as a 'search key'). In state space search in artificial intelligence, repeated searches of vertices are often allowed, while in theoretical analysis of algorithms based on breadth-first search, precautions are typically taken to prevent repetitions. BFS and its application in finding connected components of graphs were invented in 1945 by Konrad Zuse, in his (rejected) Ph.D. thesis on the Plankalkül programming language, but this was not published until 1972. It was reinvented in 1959 by Edward F. Moore, who used it to find the shortest path out of a maze, and later developed by C. Y. Lee into a wire routing algorithm (published in 1961). Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»). Fonte: Wikipedia in inglese, voce «Breadth-first search» — https://en.wikipedia.org/wiki/Breadth-first_search Wikidata Q325904: «algoritmo di ricerca per grafi che partendo da un vertice sorgente permette di cercare il cammino fino ad un altro nodo scelto e connesso al nodo sorgente» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q325904 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Breadth-first_search?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1381045311, consultata il 2026-10-31T07:55:52.765Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 6faf5db612c4e628c0f3af8bde64605db712a3e0e29b8645498f7c958374e83f