Breadth First Search(BFS) Algorithm

BFS can be used to search the shortest path from the start node to the target node in a an unweighted graph or a graph having the same edge weight. It visits all neighbor nodes first and then moving on to next-level neighbors, and so on. This algorithm uses queue to store nodes to visit next and traverses every node and edge in the graph exactly once.

BFS algorithm summary card

Table of Contents
· How BFS Algorithm Works?
· Graphical Explanation
  ∘ demo iteration 1
  ∘ demo iteration 2
  ∘ demo iteration 3
  ∘ demo iteration 4
  ∘ demo iteration 5
  ∘ final result
· Code Implementation
  ∘ Data Structure
  ∘ Complexity
  ∘ Pseudocode
  ∘ Golang
  ∘ Python

How BFS Algorithm Works?

Breadth-First Search(BFS) is an algorithm to traverse a tree or graph data structure in a breadth-ward fashion. It won’t move toward the next-level neighbor nodes unless it has explored all it adjacent nodes at the present level. It uses queue to store the nodes that will be visited next and keep track of visited nodes to avoid cycles in the graph. Therefore, BFS traverses every node/vertex and edge exactly once in a layer-wise order to find the shortest path between the start node and the target node.

Graphical Explanation

graph example

• Step1:
  - Initialize a queue and add the start node to the queue
  - Initialize a visited map to remember nodes we have visited and store the previous node for backtracking the shortest path later.
  - Mark the start node as visited and set its previous node to None(start node has no previous node).

step 1

• Step2: If the queue is not empty, follow below steps. Otherwise, stop search.
  -a: Extract the node from the front of the queue and denote as current
  -b: If the current node is the target node, stop search.
  -c: Explore all the current node’s neighbors and do following checks for every neighbor node

Is the node visited?
 - Yes => skip
 - No =>
  1. mark it as visited and store current node as its previous node
  2. append to the back of the queue

step 2

• Step3: repeat Step2 until the queue is empty

demo iteration 1

iteration 1

demo iteration 2

iteration 2–1

iteration 2–2

demo iteration 3

iteration 3

demo iteration 4

iteration 4

demo iteration 5

iteration 5

final result

final result

Code Implementation

Data Structure

Use queue to follow first in first out for the nodes we store to visit next.

Complexity

Time: O(v+e), Space: O(v)
v: the total number of vertices in the graph
e: the total number of edges in the graph

Pseudocode

# initialize a queue contains the start node
queue = Queue([start])
# initialize a visited map. 
# Mark the start node as visited and set its previous node to None
visited = {start: None}
while queue is not empty:
  # remove the node from the front of the queue 
  # denote as current
  current = queue.pop(0)
  
  if current == target:
     stop search
  
  # find all the current's neighbor nodes
  for neighbor in current.neighbors:
    if neighbor is not in visited:
       # mark it as visited and save current as its previous node
       visited[neighbor] = current
       # append to the back of the queue
       queue.append(neighbor)

Golang

Python

You can access the source code here.

Other shortest path algorithms

• Dijkstra’s algorithm
• Bellman-Ford algorithm
• A* search algorithm
• The comparison of shortest path algorithms