Blog

Breadth First Search (BFS)

A Search strategy, in which the highest layer of a decision tree is searched completely before proceeding to the next layer is called Breadth-first search (BFS). In this strategy, no viable solutions are omitted and therefore it is guaranteed that an optimal solution is found. This strategy is often not feasible when the search space is large.

  • Given 
    • a graph G=(V,E) – set of vertices and edges
    • a distinguished source vertex s
  • Breadth first search systematically explores the edges of G to discover every vertex that is reachable from s.
  • It also produces a ‘breadth first tree’ with root s that contains all the vertices reachable from s.
  • For any vertex v reachable from s, the path in the breadth first tree corresponds to the shortest path in graph G from s to v.
  • It works on both directed and undirected graphs. 
  • Breadth-First Search (BFS) begins at the root node and explore level-wise al the branches
  • BFS is complete
    • If there is a solution, BFS will found it
  • BFS is optimal
    • The solution found is guaranteed to be the shortest path possible
  • The algorithm can be implemented with a First In First Out (FIFO)

Algorithm

  1. Create a variable called LIST and set it to be the starting state.
  1. Loop until a goal state is found or LIST is empty, Do
    a. Remove the first element from the LIST and call it E. If the LIST is empty, quit.
    b. For every path each rule can match the state E, Do
    (i) Apply the rule to generate a new state.
    (ii) If the new state is a goal state, quit and return this state.
    (iii) Otherwise, add the new state to the end of LIST.

Advantages

  1. Guaranteed to find an optimal solution (in terms of shortest number of steps
    to reach the goal).
  2. Can always find a goal node if one exists (complete).

Disadvantages

  1. High storage requirement: exponential with tree depth.

Python Program of BFS

graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = [] # List to keep track of visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print (s, end = " ") 

    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
bfs(visited, graph, 'A')

Leave a Reply

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