Breadth-First Search (BFS): A Deep Dive From Theory To Implementation

Introduction

Breadth-First Search or BFS in short, is one of the most commonly used traversal algorithms over graphs, also having many practical applications such as shortest path finding, web crawling and more.

What is a graph traversal algorithm?

Graph traversal algorithms are algorithms that iteratively “visit” the vertices of a graph. In a way, we could say they are used in order to “read” the information in the graph, just as you would go over an away or a list. We usually use them to process information and derive conclusions about a graph’s structure. For example, how many connected components are there, which vertices are reachable from a certain vertex and so on…

Breadth First Search

Main Idea

Imagine you are digging a hole in the ground. You can dig wide first, and then deepen the hole, or you can dig deep first, and then widen the hole. BFS uses the first approach.
In terms of graphs, this means we are first visiting all of the direct descendants of a given vertex, before moving on to their descendants.

This is done iteratively for every vertex we discover using a queue, where the order of insertion into the queue is the order of discovery.

Note the iteration order.

Algorithm

  1. Given a starting vertex s, set distance_s(s) = 0 (The distance from itself is 0)
  2. Initialize a queue q and insert s into it
  3. while q has elements:
    • Dequeue a new vertex v from q
    • For each neighbor of v that we never encountered before, u:
      • Set u‘s distance from s to distance_s(u) = distance_s(v) + 1
      • Add u to the queue

Code

from typing import List

def bfs(graph:List[List[int]], start_vertex: int):
    queue = [start_vertex]
    seen_vertices = {start_vertex}

    distances = {vertex:-1 for vertex in graph}
    distances[start_vertex] = 0

    while queue:
        curr_vertex = queue.pop(0)

        for neighbor in graph[curr_vertex]:
            if neighbor not in seen_vertices:
                queue.append(neighbor)
                seen_vertices.add(neighbor)
                distances[neighbor] = distances[curr_vertex] + 1            

    return distances

A few notes about this implementation:

  • We are using a Python list to simulate a queue, notice that when removing we are using pop(0) which removes the first element in the list.
  • We initialize the distances to -1, so any vertex that is not reachable will have a -1 distance.
  • We are using a seen_vertices set to keep track of all the vertices that we have seen during the run. This is to make sure we do not get into an infinite loop, in the case of cycles or an undirected graph.

Output of the Algorithm – A Layered Tree

One of the key properties of the BFS output is the fact that we are getting the shortest path (in terms of steps) from the starting vertex s to any other node in the graph. We say that all the vertices with the same distance from s are part of the same “layer”.

We run BFS on the graph on the left, starting from vertex s. The resulting “distance layers” are shown on the right.

If we only keep the edges that “discovered” a vertex for the first time during the run, we get a layered tree that contains the actual shortest paths to every vertex, and not just the distances.

Possible layered BFS output trees after running the algorithm on the graph.

Note that the layered trees are not unique, and they depend on the order that we traverse a specific vertexes neighbors. In our case we have 3 different possible trees, where the difference is for path to the vertex in layer 2. This is because there is more than one possible shortest paths from the starting node s.

Runtime Complexity

Let’s analyze the runtime complexity of different phases in the algorithm:

  1. Initialization: Initializing the data structures needed for the code
    • Queue and “seen vertices” set – O(1)
    • Setting the distances array – O(V)
  2. Iterations: We potentially going over all the vertices in the graph, since they all may be entered into the queue during the run. For each one of the vertices, we are also going over the edges connected to it. In total we may go over all the vertices and edges in the graph. O(V+E)

In total: O(V+E)

Something to note is that we can’t actually do any better than that. In order to traverse the graph, we actually have to “read the data in the graph”, which means we have to go over the vertices and the edges.

Example Interview Questions

Number of Connected Components

Given a graph G=(V,E), return the number of connected components in it.

Solution:

We can solve this question in many ways. Other traversal algorithms like DFS could also work, however for the sake of this article let’s use BFS.

from typing import List

def num_connected_components(graph: List[List[int]]) -> int:
    num_vertices = len(graph)
    visited = set()
    result = 0

    for curr_vertex in range(num_vertices):
        if curr_vertex in visited:
            continue
        distances, bfs_seen_vertices = bfs(graph, curr_vertex)
        visited.update(bfs_seen_vertices)
        result += 1
    return result

On first glance it may seem this solution runs BFS from every vertex in the graph, however that is incorrect. Note that we are keeping track inside a “visited” set of all the vertices we encountered during the BFS runs (We assumed the function implementation here is changed to also return the vertices seen).

We are indeed looping and traversing from each vertex, but every BFS run should “cover” an entire connected component in one go. This means in the next iteration, BFS will not run for any of the vertices already encountered.
In total, we will run BFS exactly once for each connected component that we have in the graph, so we are just counting the number of runs and returning it.

Runtime Complexity:

In total we are running BFS over the entire graph, and also looping once over the vertices.
Answer: O(V + E)

Finding The Shortest Path

You are given a list of m tuples of cities in the world, [(Berlin, Cancun), (Cairo, Madrid)…]. A tuple indicates there is a direct flight between the cities. There are n cities in total. Given a city, write an algorithm that will find the shortest number of flights needed to get from it to the others.

Solution:

We know that the BFS algorithm returns the shortest path between two vertices in a graph, in terms of number of steps. We can build a graph that represents the cities with edges between them if there is a direct flight between them. Running BFS from any of the cities will give us the shortest distance to all the others.

from collections import defaultdict
from typing import List

def build_graph(starting_city: str, flights: List[List[str]]):
    graph = defaultdict(list)

    graph[starting_city] = []
    for from_city, to_city in flights:
        graph[from_city].append(to_city)
    
    return graph

def shortest_distance(starting_city: str, flights: List[List[str]]):
    graph = build_graph(starting_city, flights)
    return bfs(graph, starting_city)

Runtime Complexity:

  1. Building the graph – Going over n cities and m pairs. O(n+m)
  2. BFS – O(V+E). In the graph that we built V = O(n), E=O(m), so running the BFS has a runtime complexity of O(n+m)

In total: O(n+m)