Graph Traversal - Breadth First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph's vertices (nodes) level by level. It starts from a selected source node and moves outward to visit all the nodes at the same distance from the source before moving on to nodes at the following distance level.

BFS is particularly useful for finding the shortest path in unweighted graphs and for systematically exploring graphs.

Step-by-Step Algorithm for BFS

1. Graph Initialization:

   • Create a graph with V vertices.
   • Represent the graph using an adjacency list, where each vertex has a list of its adjacent vertices.

2. Mark All Vertices as Unvisited:

   • Initialize a visited boolean array of size V, with all elements set to false.

3. Initialize BFS Traversal:

   • Start from the given startVertex.
   • Mark startVertex as visited by setting visited[startVertex] = true.
   • Add startVertex to the queue.

4. Perform BFS Traversal:

   • While the queue is not empty:
     1. Dequeue a vertex (currentVertex) from the front of the queue.
     2. Process the currentVertex (e.g., print its value).
     3. For each neighbor of currentVertex (from its adjacency list):
        • If the neighbor is unvisited:
          • Mark it as visited.
          • Enqueue the neighbor into the queue.

5. End Condition:

   • The traversal ends when the queue becomes empty, meaning all reachable vertices from the startVertex have been visited.

Algorithm Walkthrough

Let's see how the Breadth First Search algorithm works with an example.

Input:

• Graph:
  • Vertices: 5 (0, 1, 2, 3, 4)
  • Edges: (0, 1), (0, 2), (0, 3), (1, 2), (2, 4)
• Starting Vertex: 0

Execution Steps

1. Initialization:

   • visited = [false, false, false, false, false]
   • queue = []

2. Start BFS Traversal:

   • Mark 0 as visited: visited = [true, false, false, false, false].
   • Enqueue 0: queue = [0].

3. First Iteration:

   • Dequeue 0: queue = [].
   • Process 0: Print 0.
   • Explore neighbors of 0:
     • 1 is unvisited: Mark as visited (visited = [true, true, false, false, false]) and enqueue: queue = [1].
     • 2 is unvisited: Mark as visited (visited = [true, true, true, false, false]) and enqueue: queue = [1, 2].
     • 3 is unvisited: Mark as visited (visited = [true, true, true, true, false]) and enqueue: queue = [1, 2, 3].

4. Second Iteration:

   • Dequeue 1: queue = [2, 3].
   • Process 1: Print 1.
   • Explore neighbors of 1:
     • 0 is already visited: Skip.
     • 2 is already visited: Skip.

5. Third Iteration:

   • Dequeue 2: queue = [3].
   • Process 2: Print 2.
   • Explore neighbors of 2:
     • 0 is already visited: Skip.
     • 1 is already visited: Skip.
     • 4 is unvisited: Mark as visited (visited = [true, true, true, true, true]) and enqueue: queue = [3, 4].

6. Fourth Iteration:

   • Dequeue 3: queue = [4].
   • Process 3: Print 3.
   • Explore neighbors of 3:
     • 0 is already visited: Skip.

7. Fifth Iteration:

   • Dequeue 4: queue = [].
   • Process 4: Print 4.
   • Explore neighbors of 4:
     • 2 is already visited: Skip.

8. End:

   • The queue is empty, so the BFS traversal is complete.

Output:

Breadth-First Traversal starting from vertex 0: 0 1 2 3 4

Implementation of Breadth First Search

Below is the implementation of Breadth-First Search (BFS) in different programming languages:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Graph {

  private int V; // Number of vertices
  private ArrayList<ArrayList<Integer>> adjList;

  public Graph(int vertices) {
    V = vertices;
    adjList = new ArrayList<>(V);
    for (int i = 0; i < V; i++) {
      adjList.add(new ArrayList<>());
    }
  }

  public void addEdge(int u, int v) {
    adjList.get(u).add(v);
    adjList.get(v).add(u); // For undirected graph
  }

  public void BFS(int startVertex) {
    boolean[] visited = new boolean[V]; // To keep track of visited vertices
    Queue<Integer> q = new LinkedList<>();

    visited[startVertex] = true;
    q.add(startVertex);

    while (!q.isEmpty()) {
      int currentVertex = q.poll();
      System.out.print(currentVertex + " ");

      // Explore adjacent vertices
      for (int neighbor : adjList.get(currentVertex)) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          q.add(neighbor);
        }
      }
    }
  }
}

class Solution {

  public static void main(String[] args) {
    Graph graph = new Graph(5); // Create a graph with 6 vertices

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(0, 3);
    graph.addEdge(1, 2);
    graph.addEdge(2, 4);

    System.out.println("Breadth-First Traversal starting from vertex 0:");
    graph.BFS(0);
  }
}

Complexity analysis

Time Complexity

1. Initialization:

   • The visited array is initialized to track whether a vertex has been visited. This operation is , where V is the number of vertices.

2. Queue Operations:

   • Each vertex is enqueued once when it is first discovered and dequeued once during processing. These operations together are over the course of the BFS traversal.

3. Exploration of Adjacent Vertices:

   • The adjacency list for each vertex is iterated over to explore its neighbors.
   • Each edge is visited exactly once when traversing its endpoints, contributing , where E is the number of edges.

4. Total Time Complexity:

   • The traversal involves visiting all vertices and all edges:

Space Complexity

1. Visited Array:

   • The visited boolean array stores one entry per vertex to track whether it has been visited. Space Requirement: .

2. Queue:

   • In the worst case, the queue can hold all vertices in a connected component, requiring space.

3. Total Space Complexity:

   • Overall Space Requirement: (from visited array and queue).

Final Words

This makes BFS efficient for graph traversal, particularly when combined with the adjacency list representation. BFS is generally efficient for searching and traversal when the graph is not too dense. For sparse graphs, where E is much smaller than , the time complexity becomes almost linear, making BFS a reasonable choice for many practical applications.

BFS guarantees it visits nodes according to their distance from the source node. It is an efficient algorithm to find the shortest path in unweighted graphs. Additionally, BFS can find connected components, detect cycles, and solve graph-related problems. However, it may consume more memory than DFS, especially in graphs with a significant or infinite branching factor.

I just read a lesson on **Graph Traversal - Breadth First Search (BFS)** (DSA) and want to truly understand it. Explain Graph Traversal - Breadth First Search (BFS) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Graph Traversal - Breadth First Search (BFS)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Graph Traversal - Breadth First Search (BFS)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Graph Traversal - Breadth First Search (BFS)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.