Breadth-first search: Difference between revisions

Revision as of 20:15, 6 June 2005

Revision as of 05:36, 7 June 2005

Line 7:

When searching in an unweighted cyclic graph (one that is not a tree) for a shortest path, BFS may be adapted by keeping a bit on each node to indicate that it has already been visited.

* BFS is complete so long as the tree it is searching has a finite number of branches - it finds a goal-state if one exists. (That is, it reaches every node on the tree.)

* BFS is optimal if step costs are identical - BFS will find the shallowest solution in a search tree, not necessarily the best one. In the case of non-uniform step costs, the shallowest solution is not necessarily the best one.

* BFS is optimal - it finds the smallest number of steps to reach the goal.

* BFS has space [[Computational complexity theory|complexity]] linear in the size (edges plus vertices) of the tree/graph searched as it needs to store all expanded nodes in memory.

* BFS has time complexity linear in the size (edges plus vertices) of the graph or tree searched.