DSA Visualizations | Hello Interview

Graphs

Like Depth-First Search, breadth-first search is also used to traverse graphs. In this section, we'll cover how to implement BFS on both adjacency lists and matrices, as well as the types of problems that are best solved using BFS.

Just like with depth-first search, the most important thing to remember when implementing BFS on a graph is to keep track of visited nodes to avoid infinite loops. If we try to enqueue a node that has already been visited, we should skip it instead of adding it to the queue.

BFS on an Adjacency List

To traverse a graph represented with an adjacency list with BFS:

Choose a starting node and add it to the queue (we start with the first node in the adjacency list Node "1" in the example below).
While the queue is not empty, remove the node at the front of the queue and add it to the set of visited nodes.
Add the children of the node to the back of the queue (if they haven't been visited yet).
Repeat steps 2 and 3 until the queue is empty.

The animation shows how BFS traverses the graph represented by:

adjList = {
    "1": ["2", "4"],
    "2": ["1", "3"],
    "3": ["2", "4"],
    "4": ["1", "3", "5"],
    "5": ["4"]
}


def bfs(start):
  visited = set([start])
  queue = [start]

  while queue:
    node = queue.pop(0)
    for neighbor in adjList[node]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

0 / 11

BFS on an Matrix (2D Grid)

To traverse a graph represented as a matrix with BFS:

Choose a starting node and add it to the queue (we start with top left node in the example below).
While the queue is not empty, remove the node at the front of the queue and add it to the set of visited nodes.
Add the four neighbors of the node to the back of the queue (if they haven't been visited yet and are within the bounds of the matrix).
Repeat steps 2 and 3 until the queue is empty.

The animation shows how BFS traverses the graph represented by:

matrix = [
    [0, 0, 0],
    [0, 1, 1],
    [0, 1, 0]
]


def bfs(grid):
  visited = set()
  # up, down, left, right
  directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

  queue = [(0, 0)]
  visited.add((0, 0))

  while queue:
    row, col = queue.pop(0)

    # enqueue neighbors
    for dr, dc in directions:
      n_row = row + dr
      m_col = col + dc

      # check bounds and if neighbor is visited
      if 0 <= n_row < len(grid) \
                and 0 <= m_col < len(grid[0]) \
                and (n_row, m_col) not in visited:
        queue.append((n_row, m_col))
        visited.add((n_row, m_col))

0 / 20

Nodes at a Level

Like binary trees, graphs can also have levels. In a graph, a level is defined as the number of edges between the root node and the current node, which is also known as the "distance" between the two nodes.

This is the primary use case of BFS in graphs: to solve questions that involve traversing the graph level-by-level, so we should be familiar with this pattern for both adjacency lists and matrices.

Nodes in a 2D-grid labeled with their distance from the top-left node.

Nodes in graph labeled with their distance from the top-left node (Node(0)).

And just like binary trees, the BFS algorithm can be extended to know when we have finished processing all nodes at a level. We can do this by adding a for-loop that iterates over the size of the queue at the beginning of each level.

Adjacency List Level-By-Level

from collections import deque

def bfs_levels(graph, start):
    queue = deque([start])
    visited = set()
    visited.add(start)
    levels = []

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        # IMPORTANT
        # we have finished processing all nodes at the current level
        levels.append(current_level)

    return levels

Matrix Level-By-Level

from collections import deque

def bfs_level_by_level(matrix):
    rows, cols = len(matrix), len(matrix[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    # start at the top-left corner
    queue = deque([(0, 0)])
    visited = set([(0, 0)])

    levels = []
    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            row, col = queue.popleft()
            current_level.append((row, col))
            for dr, dc in directions:
                r, c = row + dr, col + dc
                if 0 <= r < rows and 0 <= c < cols and (r, c) not in visited:
                    visited.add((r, c))
                    queue.append((r, c))

        # IMPORTANT
        # we have finished processing all nodes at this level
        levels.append(current_level)

    return levels

Shortest Path in a Graph

A consequence of the level-by-level nature of BFS traversal is that we can use it to find the shortest path between two nodes in a graph. Because BFS traverses the graph level-by-level, the first time we reach the destination node will be on the shortest path between the two nodes.

The animation below shows how BFS finds the shortest path between the top left node in the matrix and the first node with value "1":

0 / 8

Compare this to depth-first search, where the first path it encounters might not be the shortest path between two nodes:

0 / 10

To find the shortest path using DFS, we would have to explore all possible paths and then compare the lengths of each path to find the shortest one at the end. This makes BFS a better choice for any question that involves finding the shortest path between two nodes in a graph.

Next: Minimum Knight Moves

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Maximum Width of Binary Tree

Minimum Knight Moves

Graphs

BFS on an Adjacency List

To traverse a graph represented with an adjacency list with BFS:

Choose a starting node and add it to the queue (we start with the first node in the adjacency list Node "1" in the example below).
While the queue is not empty, remove the node at the front of the queue and add it to the set of visited nodes.
Add the children of the node to the back of the queue (if they haven't been visited yet).
Repeat steps 2 and 3 until the queue is empty.

The animation shows how BFS traverses the graph represented by:

adjList = {
    "1": ["2", "4"],
    "2": ["1", "3"],
    "3": ["2", "4"],
    "4": ["1", "3", "5"],
    "5": ["4"]
}


def bfs(start):
  visited = set([start])
  queue = [start]

  while queue:
    node = queue.pop(0)
    for neighbor in adjList[node]:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

0 / 11

BFS on an Matrix (2D Grid)

To traverse a graph represented as a matrix with BFS:

Choose a starting node and add it to the queue (we start with top left node in the example below).
While the queue is not empty, remove the node at the front of the queue and add it to the set of visited nodes.
Add the four neighbors of the node to the back of the queue (if they haven't been visited yet and are within the bounds of the matrix).
Repeat steps 2 and 3 until the queue is empty.

The animation shows how BFS traverses the graph represented by:

matrix = [
    [0, 0, 0],
    [0, 1, 1],
    [0, 1, 0]
]


def bfs(grid):
  visited = set()
  # up, down, left, right
  directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

  queue = [(0, 0)]
  visited.add((0, 0))

  while queue:
    row, col = queue.pop(0)

    # enqueue neighbors
    for dr, dc in directions:
      n_row = row + dr
      m_col = col + dc

      # check bounds and if neighbor is visited
      if 0 <= n_row < len(grid) \
                and 0 <= m_col < len(grid[0]) \
                and (n_row, m_col) not in visited:
        queue.append((n_row, m_col))
        visited.add((n_row, m_col))

0 / 20

Nodes at a Level

This is the primary use case of BFS in graphs: to solve questions that involve traversing the graph level-by-level, so we should be familiar with this pattern for both adjacency lists and matrices.

Nodes in a 2D-grid labeled with their distance from the top-left node.

Nodes in graph labeled with their distance from the top-left node (Node(0)).

Adjacency List Level-By-Level

from collections import deque

def bfs_levels(graph, start):
    queue = deque([start])
    visited = set()
    visited.add(start)
    levels = []

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        # IMPORTANT
        # we have finished processing all nodes at the current level
        levels.append(current_level)

    return levels

Matrix Level-By-Level

from collections import deque

def bfs_level_by_level(matrix):
    rows, cols = len(matrix), len(matrix[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    # start at the top-left corner
    queue = deque([(0, 0)])
    visited = set([(0, 0)])

    levels = []
    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            row, col = queue.popleft()
            current_level.append((row, col))
            for dr, dc in directions:
                r, c = row + dr, col + dc
                if 0 <= r < rows and 0 <= c < cols and (r, c) not in visited:
                    visited.add((r, c))
                    queue.append((r, c))

        # IMPORTANT
        # we have finished processing all nodes at this level
        levels.append(current_level)

    return levels

Shortest Path in a Graph

The animation below shows how BFS finds the shortest path between the top left node in the matrix and the first node with value "1":

0 / 8

Compare this to depth-first search, where the first path it encounters might not be the shortest path between two nodes:

0 / 10

Next: Minimum Knight Moves

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103