What is Breath-First Search Algorithm?

devquora
devquora

Posted On: Feb 22, 2018

 

Breath-First search involves traversing a binary search tree one level at a time. Starting with the root node, proceeding through neighboring nodes moving towards the next level of nodes. As this process can be performed utilizing FIFO (First in First Out) data structure. This strategy gives the shortest path to the solution. BFS assigns two values to each node: distance and predecessor.

  • A distance is calculated by giving the minimum number of edges in any path from the source node to node “v”.
  • The predecessor node of “v” along with some shortest path from the source node. The source node's predecessor is some special value, such as null, indicating that it has no predecessor.

If there is no path from the source node to node “v”, then v's distance is infinite, and it is assumed that predecessor has the same special value as the source's predecessor.

    Related Questions

    Please Login or Register to leave a response.

    Related Questions

    Artificial Intelligence Interview Questions

    How will you explain machine learning to a layperson?

    Basically, machine learning is pattern recognition. Like Youtube’s video recommendations, Facebook’s News Feeds, etc...

    Artificial Intelligence Interview Questions

    When will you use classification over regression?

    Classification is used when the output variable is a category such as “red” or “blue”, “spam” or “not spam”...