What does breadth-first search mean?

Definitions for breadth-first search
breadth-first search

This dictionary definitions page includes all the possible meanings, example usage and translations of the word breadth-first search.

Wiktionary

  1. breadth-first searchnoun

    a search algorithm that begins at the root node and explores all the neighboring nodes

Wikipedia

  1. Breadth-first search

    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 win 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, 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 get along without extra memory. Breadth-first search can be generalized to graphs, when the start node (sometimes referred to as a 'search key') is explicitly given, and precautions are taken against following a vertex twice. 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 1961).

Wikidata

  1. Breadth-first search

    In graph theory, breadth-first search is a strategy for searching in a graph when search is limited to essentially two operations: visit and inspect a node of a graph; gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Compare BFS with the equivalent, but more memory-efficient Iterative deepening depth-first search and contrast with depth-first search.

How to pronounce breadth-first search?

How to say breadth-first search in sign language?

Numerology

  1. Chaldean Numerology

    The numerical value of breadth-first search in Chaldean Numerology is: 6

  2. Pythagorean Numerology

    The numerical value of breadth-first search in Pythagorean Numerology is: 4


Translations for breadth-first search

From our Multilingual Translation Dictionary

Get even more translations for breadth-first search »

Translation

Find a translation for the breadth-first search definition in other languages:

Select another language:

  • - Select -
  • 简体中文 (Chinese - Simplified)
  • 繁體中文 (Chinese - Traditional)
  • Español (Spanish)
  • Esperanto (Esperanto)
  • 日本語 (Japanese)
  • Português (Portuguese)
  • Deutsch (German)
  • العربية (Arabic)
  • Français (French)
  • Русский (Russian)
  • ಕನ್ನಡ (Kannada)
  • 한국어 (Korean)
  • עברית (Hebrew)
  • Gaeilge (Irish)
  • Українська (Ukrainian)
  • اردو (Urdu)
  • Magyar (Hungarian)
  • मानक हिन्दी (Hindi)
  • Indonesia (Indonesian)
  • Italiano (Italian)
  • தமிழ் (Tamil)
  • Türkçe (Turkish)
  • తెలుగు (Telugu)
  • ภาษาไทย (Thai)
  • Tiếng Việt (Vietnamese)
  • Čeština (Czech)
  • Polski (Polish)
  • Bahasa Indonesia (Indonesian)
  • Românește (Romanian)
  • Nederlands (Dutch)
  • Ελληνικά (Greek)
  • Latinum (Latin)
  • Svenska (Swedish)
  • Dansk (Danish)
  • Suomi (Finnish)
  • فارسی (Persian)
  • ייִדיש (Yiddish)
  • հայերեն (Armenian)
  • Norsk (Norwegian)
  • English (English)

Word of the Day

Would you like us to send you a FREE new word definition delivered to your inbox daily?

Please enter your email address:


Citation

Use the citation below to add this definition to your bibliography:

Style:MLAChicagoAPA

"breadth-first search." Definitions.net. STANDS4 LLC, 2024. Web. 5 Nov. 2024. <https://www.definitions.net/definition/breadth-first+search>.

Discuss these breadth-first search definitions with the community:

0 Comments

    Are we missing a good definition for breadth-first search? Don't keep it to yourself...

    Image or illustration of

    breadth-first search

    Credit »

    Free, no signup required:

    Add to Chrome

    Get instant definitions for any word that hits you anywhere on the web!

    Free, no signup required:

    Add to Firefox

    Get instant definitions for any word that hits you anywhere on the web!

    Quiz

    Are you a words master?

    »
    something many people believe that is false
    A match
    B rogue
    C model
    D fancy

    Nearby & related entries:

    Alternative searches for breadth-first search: