Python Program to Implement BFS (Breadth-First Search)

A Python program to implement BFS uses a queue to explore nodes level by level, like from collections import deque; queue = deque([start]); while queue: node = queue.popleft(); for neighbor in graph[node]: if neighbor not in visited: queue.append(neighbor).

Examples

Input{'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []}, start='A'

Output['A', 'B', 'C', 'D', 'E']

Input{0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}, start=2

Output[2, 0, 3, 1]

Input{1: [], 2: [], 3: []}, start=1

Output[1]

How to Think About It

To implement BFS, think of exploring a graph like visiting rooms in a building floor by floor. Start from the first room, visit all its neighbors, then move to neighbors of neighbors, and so on. Use a queue to keep track of which rooms to visit next and a set to remember visited rooms so you don't visit the same room twice.

Algorithm

1

Start with a queue and add the starting node to it.

2

Create a set to keep track of visited nodes and add the start node.

3

While the queue is not empty, remove the first node from the queue.

4

Add this node to the result list.

5

For each neighbor of this node, if it is not visited, add it to the queue and mark as visited.

6

Repeat until all reachable nodes are visited.

Code

python

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

# Example usage
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []}
print(bfs(graph, 'A'))

Output

['A', 'B', 'C', 'D', 'E']

Dry Run

Let's trace BFS on graph {'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []} starting at 'A'.

1

Initialize

visited = {'A'}, queue = ['A'], order = []

2

Visit 'A'

queue = [], order = ['A'], neighbors = ['B', 'C']

3

Add neighbors 'B' and 'C'

visited = {'A', 'B', 'C'}, queue = ['B', 'C']

4

Visit 'B'

queue = ['C'], order = ['A', 'B'], neighbors = ['D']

5

Add neighbor 'D'

visited = {'A', 'B', 'C', 'D'}, queue = ['C', 'D']

6

Visit 'C'

queue = ['D'], order = ['A', 'B', 'C'], neighbors = ['E']

7

Add neighbor 'E'

visited = {'A', 'B', 'C', 'D', 'E'}, queue = ['D', 'E']

8

Visit 'D'

queue = ['E'], order = ['A', 'B', 'C', 'D'], neighbors = []

9

Visit 'E'

queue = [], order = ['A', 'B', 'C', 'D', 'E'], neighbors = []

Queue	Visited	Order
['A']	{'A'}	[]
['B', 'C']	{'A', 'B', 'C'}	['A']
['C', 'D']	{'A', 'B', 'C', 'D'}	['A', 'B']
['D', 'E']	{'A', 'B', 'C', 'D', 'E'}	['A', 'B', 'C']
['E']	{'A', 'B', 'C', 'D', 'E'}	['A', 'B', 'C', 'D']
[]	{'A', 'B', 'C', 'D', 'E'}	['A', 'B', 'C', 'D', 'E']

Why This Works

Step 1: Use a queue to explore nodes

The queue ensures nodes are visited in the order they are discovered, which is key to BFS exploring level by level.

Step 2: Track visited nodes

Keeping a set of visited nodes prevents revisiting and infinite loops in cyclic graphs.

Step 3: Add neighbors to queue

Neighbors of the current node are added to the queue to be visited later, ensuring all nodes at the current depth are processed first.

Alternative Approaches

Recursive BFS using helper function

python

from collections import deque

def bfs_recursive(graph, queue, visited, order):
    if not queue:
        return order
    node = queue.popleft()
    order.append(node)
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)
    return bfs_recursive(graph, queue, visited, order)

# Example usage
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []}
print(bfs_recursive(graph, deque(['A']), {'A'}, []))

Uses recursion instead of a loop; less common and can hit recursion limits on large graphs.

BFS using list as queue

python

def bfs_list_queue(graph, start):
    visited = set([start])
    queue = [start]
    order = []
    while queue:
        node = queue.pop(0)
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

# Example usage
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []}
print(bfs_list_queue(graph, 'A'))

Uses list pop(0) as queue which is less efficient (O(n)) compared to deque (O(1)) for large graphs.

Complexity: O(V + E) time, O(V) space

Time Complexity

BFS visits each vertex (V) and edge (E) once, so the time complexity is O(V + E).

Space Complexity

The queue and visited set store up to O(V) nodes, so space complexity is O(V).

Which Approach is Fastest?

Using deque is faster than list for queue operations. Recursive BFS is elegant but less practical for large graphs.

Approach	Time	Space	Best For
Iterative BFS with deque	O(V + E)	O(V)	General use, efficient queue operations
Recursive BFS	O(V + E)	O(V)	Small graphs, elegant code but limited by recursion depth
List as queue BFS	O(V + E)	O(V)	Simple code but slower for large graphs due to list pop(0)