Breadth-First Search (BFS) for Graphs – Explained, with Examples

Computer scientists use graphs often to represent data. Graphs can represent various relationships, from maps and chemical compounds to social relationships and computer networks. We can use many algorithms with graphs, such as Dijkstra’s algorithm, the Depth-First Search (DFS) algorithm and the Breadth-First Search (or BFS) algorithm. While you can use both algorithms to traverse the nodes of a graph, BFS is better for unweighted graphs. In this article, we’re going to explore how BFS works and its applications.

What is BFS?

BFS is a search algorithm. The algorithm begins its traversal at the source node and then visits the neighboring nodes. After this, the algorithm chooses the nearest node at the next depth level and then the visits the unexplored nodes next to this, and so on. Since the BFS algorithm visits the nodes at each level before moving on to the next level, this is where the name “Breadth-first” comes from. We ensure we only visit each node once by tracking visited and unvisited nodes. You can use BFS to calculate path distances, just like with Dijkstra’s algorithm.

The Algorithm Behind BFS

We can represent the basic algorithm with the following pseudocode:

BFS(graph, start):
    queue = [start]
    visited = set(start)

    while queue is not empty:
        node = dequeue(queue)
        process(node)

        for neighbor in graph.neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                enqueue(queue, neighbor)

In this case, we’re defining a graph as “graph”, and “start” is the starting node.

We implement a queue structure to hold the unvisited nodes, as well as a “visited” set to hold the visited nodes.

The “while” loop continues until the queue is empty, and initiates processing of the nodes level-by-level. The “dequeue” function removes the first node from the queue as it is being visited.

The “process” function performs some desired function on the node, such as updating the distance to its neighbors or printing data to the console.

The “for” loop iterates over all neighbors to the current node, checking if the node has been visited already. If not, it’s added to the queue using the “enqueue” function. In essence, the nodes at each level are stored in the queue, with their neighbors added to be visited at the next depth level. This allows us to determine the shortest path between the source node and every other node in the graph.

The Working of BFS

With the basics explained, it’s time to see how BFS works in practice. We’re going to illustrate this using a graph with nodes A, B, C, D, E and F, as shown in the image. The code below shows how to implement BFS for this graph using the Python programming language.

from collections import defaultdict, deque

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

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = defaultdict(list)
edges = [("A", "B"), "A", "C"), ("B", "C"), ("C", "D"), ("C", "E"), ("C", "F"), ("D", "F"), ("E", "F")

for edge in edges:
    graph[edge[0]].append(edge[0])
    graph[edge[1]].append(edge[0])

bfs(graph, "A")

Explanation of the Code

First, we’re importing the “defaultdict” and “deque” classes from the “collections” module. These are used to create a dictionary with default key values, and to create a queue that allows adding and removing elements.

Next, we’re defining the “bfs” function with two arguments, “graph” and “start”. We take the “graph” argument as a dictionary with the vertices as keys and neighboring vertices as values. Here, “start” refers to the source node, where the algorithm begins.

“queue = deque([start])” creates a queue with the source node as the only element, and “visited = set([start])” creates a set of visited nodes with the source node as the only element.

The “while” loop continues until the queue is empty. “node = queue.popleft()” removes the leftmost element from the queue and stores it in the “node” variable. “print(node)” prints these node values.

The “for” loop iterates over each neighbor node. “if neighbor not visited” checks if the neighbor has been visited. “visited.add(neighbor)” adds the neighbor to the visited list, and “queue.append(neighbor)” adds the neighbor to the right end of the queue.

After this, we create a default dictionary called “graph”, and define the edges of the graph. The “for” loop iterates over each edge. “graph[edge[0]].append(edge[1])” adds the second element of the edge as a neighbor of the first element, and the first element of the edge as a neighbor of the second. This constructs the graph.

Finally, we call the “bfs” function on “graph”, with the source node as “A”.

Implementation of Code

In the screenshot, we can see the output [A, B, C, D, E F]. This is what we’d expect since BFS explores the nodes at each depth level before moving on to the next. Referring back to the graph, we see that B and C will be added to the queue and visited first. B is visited, and then A and C are added to the queue. Since A has been visited already, C is visited next, and A is removed. After this, C’s neighbors, D, E and F, are added to the queue. These are then visited, and the output is printed.

Using BFS for Disconnected Graphs

We used BFS for a connected graph previously. However, we can also use BFS when nodes are not all connected. We’re going to use the same graph data since the modified algorithm can be illustrated with either kind of graph. The modified code is:

from collections import defaultdict, deque

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

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    for node in graph.keys():
        if node not in visited:
            queue = deque([node])
            visited.add(node)

            while queue:
                node = queue.popleft()
                print(node)

                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)


graph = defaultdict(list)
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D"), ("C", "E"), ("C", "F"), ("D", "F"), ("E", "F")]
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])

bfs(graph, "A")

We have used an additional “for” loop. The loop iterates over all the nodes using the “graph.keys()” method. BFS starts a new queue if it finds an unvisited node and works recursively. By doing this, we visit all disconnected nodes. See the image below for an illustration.

Best and Worst Use Cases for BFS

Now we know how BFS works, we should look at the time and space complexity of the algorithm to get an idea of its best and worst use cases.

Time Complexity of BFS

We can see that the time complexity is the same in all cases, and is equal to O(V + E), where V is the number of vertices and E is the number of edges. In the best case, where we only have one node, the complexity will be O(1), because V = 1 and E = 0. In the average and worst cases, the algorithm visits all nodes that it can reach from the source node, so the complexity depends on the structure and size of the graph in both cases.

Space Complexity of BFS

Again, we see that the complexity is the same for all cases. The algorithm visits each node no matter the graph structure. Therefore, the complexity depends on the number of vertices in the graph.

Wrapping Up

BFS is one way to traverse the nodes in a graph, calculate path distances, and explore relationships between nodes. It’s a very useful algorithm for exploring network systems and detecting graph cycles. BFS is relatively easy to implement for both connected and disconnected graphs. A benefit is that the time and space complexity are the same for all cases.