Home

 › 

Articles

 › 

Concepts

 › 

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

What is dynamic programming?

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

bfs example graph
We will be using this graph for the following code examples.

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

bfs example code for connected graph
This is what the BFS algorithm looks like when implemented and running through a connected graph.

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.

bfs example code for disconnected graph
This is an example of the BFS algorithm when implemented and running through a disconnected graph.

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

CaseComplexity
BestO(V + E)
AverageO(V + E)
WorstO(V + E)

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

CaseComplexity
BestO(V)
AverageO(V)
WorstO(V)

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.

Frequently Asked Questions

What is BFS?

BFS is an algorithm used for traversing trees or graphs, usually those representing networks such as social or computer networks. It can also detect graph cycles or if a graph is bipartite, as well as calculate the shortest path distances. Breadth-first means that each node is explored at a particular depth level before moving onto the next.

What is the time complexity of BFS?

The time complexity of BFS is O(V + E) in all cases.

What is the space complexity of BFS?

The space complexity of BFS is O(V) in all cases.

When should you use BFS?

If you need to calculate the shortest path distance, or explore all vertices in an unweighted graph.

How is BFS implemented?

We typically implement BFS using a queue data structure and a set to keep track of visited and unvisited nodes. The source node is added to the queue and marked as visited. Then, the algorithm recursively operates on neighboring nodes, adding and removing nodes as it goes to ensure no node is visited twice.

How does BFS compare to Dijkstra's algorithm?

These algorithms can both be used to calculate shortest path distances, but BFS works with unweighted graphs. In contrast, Dijkstra’s algorithm works with weighted graphs.

How does DFS compare to BFS?

Both are used to traverse a graph, but they differ in how they do this. While BFS searches each node at a given depth level before moving on, DFS visits nodes at as far a depth as possible before going back on itself to explore another branch. DFS usually uses a stack data structure as opposed to a queue.

To top