Python Program to Implement Breadth-First Search (BFS)

Breadth-First Search (BFS) explores a graph level by level — it visits every neighbor of the current node before moving further out, instead of diving deep like DFS does. This makes BFS the natural choice whenever you need the shortest path in an unweighted graph, such as finding the minimum number of connections between two people in a social network, or the fewest moves to solve a puzzle.

BFS is implemented with a queue rather than a stack, so this post uses Python's collections.deque, which gives O(1) additions and removals from both ends (a plain list's pop(0) is O(n), which would silently make a "BFS" slow on large graphs).

Python Program to Implement Breadth-First Search (BFS)

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}


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

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

    return visited


print("BFS traversal order:", bfs(graph, "A"))

Output:

BFS traversal order: ['A', 'B', 'C', 'D', 'E', 'F']

Notice the order differs from DFS: BFS visits both of A's direct neighbors (B, C) before going any deeper, while DFS would tunnel all the way down one branch first. Like DFS, BFS runs in O(V + E) time, but it also needs O(V) space for the queue in the worst case (a wide, shallow graph can have most of its nodes in the queue at once). A common extension is tracking each node's distance from the start alongside visited, which turns this into a shortest-path finder for unweighted graphs — for weighted edges, you'd reach for Dijkstra's algorithm instead.

---