Definition:
Breadth-First Search Algorithm is a graph search algorithm. It begins from root node and continues to expand all neighbour node 1- level below.
In artificial intelligence, it is categorized as Uninformed (Blind) Search.
In worst case, the time complexity of this algorithm is O ( b ^d ). ( b: maximum branching factor of the search tree ; d: depth of the least-cost solution )
In worst case, the space complexity of this algorithm is O ( b ^d ).
Properties of BFS:
- Completed,
- Finds the shallowest path,
- Generates b + b^2 + b^3 + … + b^d = O( b^d ) nodes,
- Space complexity (frontier size) is O (b ^ d ) .
How Does It Work?
- The root node is expanded.
- Then, all successors of the root node are expanded,
- Then all their successors.
In detail: (from Wikipedia)
- Enqueue the root node,
- Dequeue a node
- If the element sought is found in this node, quit the search and return a result.
- Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
- If the queue is empty, every node on the graph has been examined – quit the search and return “not found”.
- If the queue is not empty, repeat from Step 2.
In the figure below, you can see the animated figure of BFS.
Animated Figure of BFS
In the figure below, you can see the order of nodes expanded (visited)
Order of Nodes Expandend in BFS
Animation:
For better understanding, go to this animation page.
Pseudocode:
1 procedure BFS(G,v) is 2 create a queue Q 3 create a vector set V 4 enqueue v onto Q 5 add v to V 6 while Q is not empty loop 7 t ← Q.dequeue() 8 if t is what we are looking for then 9 return t 10 end if 11 for all edges e in G.adjacentEdges(t) loop 12 u ← G.adjacentVertex(t,e) 13 if u is not in V then 14 add u to V 15 enqueue u onto Q 16 end if 17 end loop 18 end loop 19 return none 20 end BFS
References:
Artificial Intelligence A Modern Approach, S.Russell, P. Norvig, Third Edition,
Figures from: http://en.wikipedia.org