Breadth-First Search Algorithm

From GM-RKB
(Redirected from Breadth-first search (BFS))
Jump to navigation Jump to search

A Breadth-First Search Algorithm is an iterative Lattice Search Algorithm that beings its test at an Extremum, identifies all neighboring nodes tests all of these nodes and then repeats the process.



References

2012

2010

  • http://en.wikipedia.org/wiki/Breadth-first_search
    • In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.

      BFS is a uninformed search method that aims to expand and examine all nodes of a graph or combination of sequences by systematically searching through every solution. In other words, it exhaustively searches the entire graph or sequence without considering the goal until it finds it. It does not use a heuristic algorithm.

      From the standpoint of the algorithm, all child nodes obtained by expanding a node are added to a FIFO queue. In typical implementations, nodes that have not yet been examined for their neighbors are placed in some container (such as a queue or linked list) called "open" and then once examined are placed in the container "closed".