BFS – Breadth-first search algorithm

Categories: Algorithms

BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph by exploring all the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes. Basically traversing the tree or graph layer by layer.


Pseudocode

1  procedure BFS(G, start_v) is
2      let Q be a queue
3      label start_v as discovered
4      Q.enqueue(start_v)
5      while Q is not empty do
6          v := Q.dequeue()
7          if v is the goal then
8              return v
9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered then
11                 label w as discovered
12                 w.parent := v
13                 Q.enqueue(w)

Python Implementation

class GraphTraversals:
  def __init__(self, graph):
    self.graph = graph

  def __str__(self):
    return str(self.graph)

  def bfs(self, source):
    visited = []
    queue = []
    # add the initial source
    queue.append(source)
    visited.append(source)

    while len(queue) > 0:
      s = queue.pop(0)
      node = self.graph[s]
      for children in node:
        if children not in visited:
          visited.append(children)
          queue.append(children)

    print(visited)

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

g = GraphTraversals(graph)
print(g.bfs('A'))