7

Breadth-First Search Algorithm (BFS)

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?

  1. The root node is expanded.
  2. Then,  all successors of the root node are expanded,
  3. Then all their successors.

In detail: (from Wikipedia)

  1. Enqueue the root node,
  2. 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.
  3. If the queue is empty, every node on the graph has been examined – quit the search and return “not found”.
  4. If the queue is not empty, repeat from Step 2.

In the figure below, you can see the animated figure of BFS.

Animated_BFS

Animated Figure of BFS

In the figure below, you can see the order of nodes expanded (visited)

300px-Breadth-first-tree.svg

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

 

omersezer

7 Comments

  1. Awesome blog! Is your theme custom made or did you download it from somewhere?
    A design like yours with a few simple adjustements would really make my blog
    jump out. Please let me know where you got your design. Many thanks

  2. Hello! I’ve been reading your weblog for some time now and finally got the bravery to go ahead and gkve you a shout out from Neww
    Caney Texas! Just wanted to say keep up the good job!

  3. If some one desires to be updated with hottest technologies therefore he must be go to see thhis web site and be up to date all the
    time.

  4. Greetings! Very helpful advice in this particular article!

    It’s the little changes that produce the greatest changes.
    Thanks for sharing!

  5. Hi there, just became alert to your blog through Google, and found
    that it’s really informative. I am going to watch out.

    I’ll be grateful if you continue this in future. A lot of people
    will be benefited from your writing. Cheers!

  6. Magnificent goods from you, man. I have understand your stuff prior to and you are simply extremely wonderful.

  7. I am really inspired with your writing talents and also with the format on your blog.

Leave a Reply

Your email address will not be published. Required fields are marked *