Breadth-first search

(Posted on 2007/09/05, 18:51:40)

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 neighbour nodes, and so on, until it finds the goal.

How it works?

BFS is a uninformed search method that aims to expand and examine all nodes of a graph systematically in search of a solution. In other words, it exhaustively searches the entire graph without considering the goal until it finds it. It does not use a heuristic.

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".

Algorithm

1. Put the ending node (the root node) in the queue.
2. Pull a node from the beginning of the queue and examine it.
   • If the searched element is found in this node, quit the search and return a result.
   • Otherwise push all the (so-far-unexamined) successors (the direct child nodes) of this node into the end of the queue, if there are any.
3. If the queue is empty, every node on the graph has been examined -- quit the search and return "not found".
4. Repeat from Step 2.

References

• http://en.wikipedia.org/wiki/Breadth-first_search

Tags

search, breadth-first search, bfs, graph

Comments

Name:

Email:

Website:

Comment:

 

Tohid Delta:

Posted on 2012/02/13, 12:44:42

" Siavash you are extraordinary. کارت فوق العادس "

Amirali:

Posted on 2007/10/01, 11:08:02

" Hi there beautiful. "