Jumper icon indicating copy to clipboard operation
Jumper copied to clipboard

Add search algorithm : Breadth-First Search

Open Yonaba opened this issue 10 years ago • 0 comments

Following Depth First search and Besr First Search, include Breadth First search, for uniform-cost grids and point graphs.

Pseudo-code:

procedure BFS(G,v) is
  create a queue Q
  create a vector set V
  enqueue v onto Q
  add v to V
  while Q is not empty loop
    t ← Q.dequeue()
    if t is what we are looking for then
      return t
    end if
    for all edges e in G.adjacentEdges(t) loop
      u ← G.adjacentVertex(t,e)
      if u is not in V then
        add u to V
        enqueue u onto Q
      end if
    end loop
  end loop
  return none
end BFS

Yonaba avatar Jun 04 '14 09:06 Yonaba