Breadth First Search (BFS) For a Graph

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the neighboring nodes at the current depth/distance from the source node before moving on to the nodes at the next depth level. This means that the BFS algorithm visits nodes which are nearer to the source node first, before exploring nodes that are farther away. In more formal terms, the algorithm visits all the nodes which are at a distance d from the source/root node before moving on to the nodes at a distance d+1. This property makes BFS an ideal algorithm for finding the shortest path in unweighted graphs.

Visual Pattern of Breadth First Search

Consider the below graph to visually understand the traversal pattern of Breadth First Search. Let’s start the BFS from source node A and mark the node as visited (visited nodes are colored in green):

Next, we need to visit all the unvisited nodes connected to nodes visited in the previous step. Node A is visited in the previous step and nodes B, C are the unvisited nodes connected to it. So let’s visit nodes B, C:

Next, we need to visit all the unvisited nodes connected to nodes visited in the previous step. Nodes B,C are visited in the previous step and nodes E, D, F are the unvisited nodes connected to them. So let’s visit nodes E, D, F:

Next, we need to visit all the unvisited nodes connected to nodes visited in the previous step. Nodes E, D, F are visited in the previous step and nodes G and H are the only unvisited nodes connected to them. So let’s visit nodes E, D, F:

Next, we need to visit all the unvisited nodes connected to nodes visited in the previous step. Nodes G and H are visited in the previous step and node I is the only unvisited node connected to them. So let’s visit node I:

All the nodes are visited/traversed by now, so the breadth first search is complete. Below is the combined animation which includes all the steps of breadth first search traversal:

BFS as Layer By Layer Traversal

Breadth First Search (BFS) can also be visualized as a layer-by-layer exploration of a graph or tree structure. Each “layer” represents nodes that are at the same distance from the root/target node from which BFS starts. For example, the first layer consists of all nodes directly connected to the root, the second layer includes nodes that are two steps away from the root, and so on.

By slightly re-arranging the positions of nodes in the previous graph example, we can visualize Breadth First Search from node A as layer by layer traversal. Below is the animation which depicts BFS as a layer by layer traversal:

This visualization helps understand why BFS is particularly useful for finding the shortest path between two nodes in an unweighted graph. The nodes which are nearer to the source node are always visited first before much farther nodes are visited.

Breadth First Search Algorithm

Prerequisites

Below are some of the prerequisites for understanding Breadth First Search algorithm:

Graphs: A graph is a data structure that represents a set of objects along with the connections or relations between them. The objects are often referred to as nodes or vertices in the graph, and the connections are called edges or arcs. Click here to learn more about graph data structure.
Graph Representations: Graphs can be programmatically represented using edge lists, adjacency lists, and adjacency matrices Learning more about them helps understand the BFS algorithm and it’s variations much better.
Neighbor Nodes: All nodes reachable from a given nodes are called as neighbor nodes
Queue Data Structure: A queue is a data structure that follows the First-In-First-Out (FIFO) principle. In BFS, a queue is used to keep track of nodes to be explored in the order they are first visited. If you are new to queue data structure, you can learn more about it here.

Steps in BFS Algorithm

Below are all the steps involved in Breadth First Search (BFS) algorithm:

Start with a graph and a starting/source node.
Create a queue data structure to keep track of nodes to visit.
Create a set or array to mark and track visited nodes.
Add the starting node to the queue and mark it as visited.
While the queue is not empty:
- Remove the first node from the queue (let’s call it the current node).
- Process or examine the current node as needed.
- For each unvisited neighbor of the current node:
  - Mark the neighbor as visited.
  - Add the neighbor to the queue.
Repeat step 5 until the queue is empty.
Once the queue is empty, BFS is complete.

Step by Step Visualization of BFS Algorithm

Below is a slideshow that applies the Breadth-First Search algorithm to a graph and explains each step along with the corresponding visualization. Use the next/previous buttons to move forward/backward through the slides.

Time & Space Complexity

The time complexity of the Breadth First Search (BFS) algorithm is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because the algorithm visits each node and edge at most once.

The space complexity of BFS algorithm is O(V), where V represents the number of vertices/nodes in the graph. This complexity arises from two main factors: the queue used to store nodes awaiting processing, and the set or array used to track visited nodes. Both of these data structures may potentially need to hold all vertices in the graph simultaneously.

Implementation of Breadth First Search

Let’s now look at implementing the Breadth first search algorithm discussed in the previous section:


from collections import deque

def breadth_first_traversal(start_node, graph, visited):
  """
  Function to perform a Breadth First Search (BFS)
  starting from the start_node.
  
  Args:
  start_node: The node from which BFS starts.
  graph: The graph represented as an adjacency list.
  visited: A set to keep track of all visited nodes.
  """

  # Create a queue to store the nodes to be visited
  queue = deque()

  # Add the starting node to the queue and mark it as visited
  queue.append(start_node)
  visited.add(start_node)

  # Traverse the graph using BFS
  while queue:
    # Dequeue a node from the front of the queue
    current_node = queue.popleft()

    # Process the dequeued node (e.g., print it)
    print(current_node, end=' ')

    # Add all the unvisited neighbors of the dequeued node to the queue and mark them as visited
    for neighbor in graph[current_node]:
      if neighbor not in visited:
        queue.append(neighbor)
        visited.add(neighbor)

# Let's test BFS algorithm on the sample graph below
graph = {
    'A' : ['B', 'C'],
    'B' : ['A', 'C', 'D'],
    'C' : ['A', 'B', 'E', 'F'],
    'D' : ['B'],
    'E' : ['C'],
    'F' : ['C']
}

# Initialize an empty set to store all visited elements
visited = set()

# Perform breadth_first_traversal for each node in the graph
for node in graph:
  if node not in visited:
    # Start BFS at the current node
    breadth_first_traversal(node, graph, visited)


#include <iostream>
#include <queue>
#include <unordered_set>
#include <map>
#include <vector>

using namespace std;

// Function to perform Breadth First Search (BFS) starting from the start_node
void breadth_first_traversal(string start_node, map<string, vector<string>>& graph, unordered_set<string>& visited) {
  // Create a queue to store the nodes to be visited
  queue<string> q;

  // Add the starting node to the queue and mark it as visited
  q.push(start_node);
  visited.insert(start_node);

  // Traverse the graph using BFS
  while (!q.empty()) {
    // Dequeue a node from the front of the queue
    string current_node = q.front();
    q.pop();

    // Process the dequeued node (e.g., print it)
    cout << current_node << " ";

    // Add all the unvisited neighbors of the dequeued node to the queue and mark them as visited
    for (const string& neighbor : graph[current_node]) {
      if (visited.find(neighbor) == visited.end()) {
        q.push(neighbor);
        visited.insert(neighbor);
      }
    }
  }
}

int main() {
  // Define the sample graph
  map<string, vector<string>> graph = {
      {"A", {"B", "C"}},
      {"B", {"A", "C", "D"}},
      {"C", {"A", "B", "E", "F"}},
      {"D", {"B"}},
      {"E", {"C"}},
      {"F", {"C"}}
  };

  // Initialize an empty set to store all visited elements
  unordered_set<string> visited;

  // Perform breadth_first_traversal for each node in the graph
  for (const auto& node : graph) {
    if (visited.find(node.first) == visited.end()) {
      // Start BFS at the current node
      breadth_first_traversal(node.first, graph, visited);
    }
  }

  return 0;
}


// Function to perform Breadth First Search (BFS)
function breadthFirstTraversal(startNode, graph, visited) {
  // Create a queue to store the nodes to be visited
  const queue = [];

  // Add the starting node to the queue and mark it as visited
  queue.push(startNode);
  visited.add(startNode);

  // Traverse the graph using BFS
  while (queue.length > 0) {
    // Dequeue a node from the front of the queue
    const currentNode = queue.shift();

    // Process the dequeued node (e.g., print it)
    console.log(currentNode);

    // Add all the unvisited neighbors of the dequeued node to the queue and mark them as visited
    for (const neighbor of graph[currentNode]) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
        visited.add(neighbor);
      }
    }
  }
}

// Sample graph
const graph = {
  A: ['B', 'C'],
  B: ['A', 'C', 'D'],
  C: ['A', 'B', 'E', 'F'],
  D: ['B'],
  E: ['C'],
  F: ['C']
};

// Initialize an empty set to store all visited elements
const visited = new Set();

// Perform breadthFirstTraversal for each node in the graph
for (const node in graph) {
  if (!visited.has(node)) {
    // Start BFS at the current node
    breadthFirstTraversal(node, graph, visited);
  }
}


import java.util.*;

public class Main {
  public static void breadthFirstTraversal(String startNode, Map<String, List<String>> graph, Set<String> visited) {
    // Create a queue to store the nodes to be visited
    Queue<String> queue = new LinkedList<>();

    // Add the starting node to the queue and mark it as visited
    queue.offer(startNode);
    visited.add(startNode);

    // Traverse the graph using BFS
    while (!queue.isEmpty()) {
      // Dequeue a node from the front of the queue
      String currentNode = queue.poll();

      // Process the dequeued node (e.g., print it)
      System.out.println(currentNode);

      // Add all the unvisited neighbors of the dequeued node to the queue and mark them as visited
      for (String neighbor : graph.get(currentNode)) {
        if (!visited.contains(neighbor)) {
          queue.offer(neighbor);
          visited.add(neighbor);
        }
      }
    }
  }

  public static void main(String[] args) {
    // Let's test BFS algorithm on the sample graph below
    Map<String, List<String>> graph = new HashMap<>();
    graph.put("A", Arrays.asList("B", "C"));
    graph.put("B", Arrays.asList("A", "C", "D"));
    graph.put("C", Arrays.asList("A", "B", "E", "F"));
    graph.put("D", Arrays.asList("B"));
    graph.put("E", Arrays.asList("C"));
    graph.put("F", Arrays.asList("C"));

    // Initialize an empty set to store all visited elements
    Set<String> visited = new HashSet<>();

    // Perform breadthFirstTraversal for each node in the graph
    for (String node : graph.keySet()) {
      if (!visited.contains(node)) {
        // Start BFS at the current node
        breadthFirstTraversal(node, graph, visited);
      }
    }
  }
}

Applications of Breadth First Search

Below are some of the real-world use cases of breadth-first search (BFS):

Finding nearby locations: Mobile apps use BFS to find nearby restaurants, gas stations, or other points of interest, searching in expanding circles from the user’s location.
Network broadcasting: In computer networks, BFS can efficiently broadcast a message to all nodes, spreading the information layer by layer from the source.
Puzzle solving: For games like Rubik’s Cube or sliding puzzles, BFS can find the minimum number of moves to reach the solution by exploring all possible moves at each step.
Computer vision: In image processing, BFS can be used for flood fill algorithms to color or select connected regions in an image.
Web crawling: Search engines use BFS to discover and index web pages, starting from a seed page and following links to explore the web in expanding layers.
Recommendation systems: E-commerce platforms use BFS to explore product relationships and suggest similar or complementary items to customers.

Bidirectional BFS

In a standard BFS, the algorithm explores all neighbors of the current node before moving to the next level. It continues this process until it reaches the goal node or exhausts all possibilities. Bidirectional BFS, on the other hand, runs two separate BFS searches concurrently - one from the start node and another from the goal node. The search terminates when the two searches meet, indicating a path has been found. This version of BFS is more efficient on large graphs, particularly when the start and goal nodes are far apart.

BFS vs DFS

BFS (Breadth First Search) explores a graph level by level, visiting all neighbors of a node before moving to the next level. It uses a queue data structure to keep track of nodes to visit next. BFS is ideal for finding the shortest path in an unweighted graph and is often used when the target node is likely to be close to the starting point.

In contrast, DFS (Depth First Search) explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of nodes to visit next. DFS goes deep into the graph first before exploring other branches. It is useful for tasks like topological sorting, finding connected components, or exploring all possible paths.

BFS generally requires more memory but guarantees the shortest path in unweighted graphs, while DFS uses less memory but may not find the shortest path without traversing the entire graph.

Click here to learn more about Depth First Search (DFS)

BFS vs Dijkstra’s Algorithm

BFS algorithm works well for unweighted graphs (for graphs which do not have any edges with weights), while Dijkstra’s algorithm is designed for weighted graphs.
BFS uses a simple queue, whereas Dijkstra’s uses a priority queue.
BFS has a time complexity of O(V + E), while Dijkstra’s has O((V + E) log V) with a binary heap implementation.

Click here to learn more about Dijkstra’s algorithm