BFS on graph

Question

Given an undirected graph represented as an adjacency list, implement a Breadth-First Search (BFS) algorithm to traverse the graph starting from a specified source node. Your function should return a list of nodes in the order they are visited. The input will consist of the graph and the starting node, and the output should be the traversal order as an array of node values.

Codemia · Accepted Answer

This problem requires us to use the Breadth-First Search (BFS) algorithm to traverse an undirected graph represented as an adjacency list. The BFS pattern is applicable here because it explores all neighbors of a node before moving on to the next level of neighbors. This level-by-level traversal is ideal for discovering the shortest path in unweighted graphs and guarantees that we visit nodes in the order of their distance from the source node. The adjacency list representation allows efficient exploration of nodes and their neighbors, making BFS a suitable choice.

We will implement the BFS algorithm using a queue to keep track of the nodes to be visited. The steps are as follows:

1. Initialize an empty list `visited` to keep track of the nodes we have already visited.
2. Initialize a queue (using collections.deque for O(1) time complexity for append and pop operations) and enqueue the starting node.
3. While the queue is not empty:
   - Dequeue a node from the front of the queue.
   - If it has not been visited, mark it as visited and add it to the result list.
   - Enqueue all its unvisited neighbors into the queue.
4. Continue this until the queue is empty.
5. Return the result list.

For example, given a graph represented as:
```
{
  0: [1, 2],
  1: [0, 3],
  2: [0, 4],
  3: [1],
  4: [2]
}
```
If we start BFS from node `0`, the traversal order will be `[0, 1, 2, 3, 4]`.

Here is the Python implementation of the BFS algorithm for the given problem:
```python
from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])
    visited_set = set([start])  # To track visited nodes efficiently
    
    while queue:
        node = queue.popleft()
        visited.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited_set:
                visited_set.add(neighbor)
                queue.append(neighbor)
    
    return visited
```
This code initializes a deque for the queue, tracks visited nodes using a set for O(1) lookups, and ensures we only visit each node once.

The time complexity of this BFS implementation is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because we visit every node once and examine each edge at most twice (once from each node it connects). The space complexity is O(V) due to the storage used for the `visited` list and the queue. This complexity is efficient given the constraints of the problem, as it ensures we handle the graph traversal within linear time relative to its size.

1. **Empty Graph**: If the graph is empty (i.e., `{}`), the function should return an empty list `[]`.
2. **Single Node**: If the graph has only one node (e.g., `{0: []}`), starting BFS from that node should return `[0]`.
3. **Disconnected Graph**: If the graph has multiple disconnected components, BFS should only return the nodes that are reachable from the starting node. For example, if the graph is `{0: [1], 1: [0], 2: []}`, starting from node `0` should return `[0, 1]`, while starting from `2` should return `[2]`.

BFS on graph

Atlassian

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Atlassian Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string