Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

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
Image

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

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

Python3
Python3
. . . .

Complexity analysis

Time Complexity

  1. Initialization:

    • The visited array is initialized to track whether a vertex has been visited. This operation is O(V), 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 O(V) 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 O(E), where E is the number of edges.

  4. Total Time Complexity:

    • The traversal involves visiting all vertices and all edges: O(V) \text{ (vertices) } + O(E) \text{ (edges) } = O(V + E)

Space Complexity

  1. Visited Array:

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

  2. Queue:

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

  3. Total Space Complexity:

    • Overall Space Requirement: O(V) (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 V^2, 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.

Mark as Completed