How to Get the Breadth-First Traversal Order of a Graph in Python

Performs a breadth-first search on an adjacency list and returns the order nodes are visited, using a deque for efficient queue operations.

Easy Python 3.9+ Aug 9, 2026 Algorithms & data structures 14 views 0 copies

graph bfs queue traversal deque

Python code

30 lines
Python 3.9+
Run it 
from collections import deque

def bfs_order(adjacency, start=0):
    """Return the order nodes are visited in a breadth-first traversal."""
    visited = set()
    order = []
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        order.append(node)

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

    return order

if __name__ == "__main__":
    # Simple undirected graph: 0-1, 0-2, 1-3, 2-4
    adjacency = [
        [1, 2],      # node 0
        [0, 3],      # node 1
        [0, 4],      # node 2
        [1],         # node 3
        [2]          # node 4
    ]
    print(bfs_order(adjacency, start=0))

Output

stdout 
[0, 1, 2, 3, 4]

How it works

The deque from the collections module provides O(1) appends and pops from both ends, making it ideal for the FIFO queue behavior BFS requires. The visited set prevents revisiting nodes and avoids infinite loops in cyclic graphs. Nodes are added to the queue when first discovered, ensuring each node is processed exactly once. The order list captures the exploration sequence, which for BFS is level-by-level from the start node.

Common mistakes

  • Using a list with pop(0) instead of a deque, which gives O(n) removal cost and slows down large graphs.
  • Forgetting to mark the start node as visited before the loop, causing it to be processed twice.

Variations

  1. Use a defaultdict(list) for a sparse adjacency structure when the graph has many nodes.
  2. Replace the visited set with a color array where each node is marked as discovered or processed.

Real-world use cases

  • Finding the shortest path in an unweighted social network when mapping friend connections level by level.
  • Discovering all reachable document nodes in a web crawler starting from a single seed URL in order of their link distance.
  • Flattening a hierarchical org chart into a level-by-level employee listing for reporting or notification systems.

Sponsored

Run this sample

Open the browser IDE to tweak the example and see results without installing anything.

Open editor

More from Algorithms & data structures

Keep learning

Related tutorials and quizzes for this topic.

Tutorials

Quizzes