BFS Traversal in Graph | Explained using Code

Learn how to perform BFS Traversal in Graph represented by an adjacency list. This hands guide uses Python’s collections.deque, walks through the code line by line, and shows a simple dry run, perfect for coding interviews and GFG practice!

What the Problem Asks

BFS Traversal of Graph
Given a graph in the form of an adjacency list, perform a Breadth-First Search (BFS) starting from vertex 0 and return the order in which nodes are visited.

Input:

• adj: A list of n lists, where adj[u] contains all neighbors of node u.

Output:

• A list of vertices in the order they’re visited by BFS, beginning at node 0.

Intuition & Approach

• BFS explores a graph level by level.
• You start at the source (0), then visit all neighbors of 0, then all unvisited neighbors of those, and so on.
• A queue ensures you visit in the correct order: first-in, first-out.
• A visited array prevents revisiting nodes (and getting stuck in cycles).

Code Implementation

from collections import deque

class Solution:
    # Function that does BFS from 'start' and returns the visit order.
    def bfs_algo(self, n, adj, start):
        ans = []                  # stores the BFS order
        visited = [0] * n         # 0 = unvisited, 1 = visited
        queue = deque([start])    # our queue, seeded with the start node
        visited[start] = 1

        while queue:
            u = queue.popleft()   # take the next node
            ans.append(u)         # record it

            # enqueue all unvisited neighbors
            for v in adj[u]:
                if visited[v] == 0:
                    visited[v] = 1
                    queue.append(v)

        return ans

    def bfs(self, adj):
        n = len(adj)
        return self.bfs_algo(n, adj, 0)

Code Explanation

Initialization

ans = []
visited = [0] * n
queue = deque([start])
visited[start] = 1

• ans collects the order of visited nodes.
• visited tracks which nodes we’ve already enqueued.
• queue begins with the start node (0), and we mark it visited.

BFS Loop

while queue:
    u = queue.popleft()
    ans.append(u)
    for v in adj[u]:
        if not visited[v]:
            visited[v] = 1
            queue.append(v)

• popleft() gives the next node in FIFO order.
• We append it to our answer list.
• Then for each neighbor v, if it’s unvisited, we mark it visited and enqueue it.

Return

return ans

• Once the queue is empty, we’ve visited all reachable nodes in BFS order.

Dry Run Example

Consider this graph (n = 5):

Adjacency List:
0: [1, 2]
1: [0, 3]
2: [0, 4]
3: [1]
4: [2]

Starting at node 0:

1. Queue = [0], ans = [], visited = [1,0,0,0,0]
2. Pop 0 → ans = [0]. Enqueue its neighbors 1, 2:
   • Queue = [1,2], visited = [1,1,1,0,0]
3. Pop 1 → ans = [0,1]. Enqueue unvisited neighbor 3:
   • Queue = [2,3], visited = [1,1,1,1,0]
4. Pop 2 → ans = [0,1,2]. Enqueue unvisited neighbor 4:
   • Queue = [3,4], visited = [1,1,1,1,1]
5. Pop 3 → ans = [0,1,2,3] (no new neighbors)
6. Pop 4 → ans = [0,1,2,3,4] (no new neighbors)
7. Queue is empty → done.

Final BFS order: [0, 1, 2, 3, 4]

Time & Space Complexity

Time Complexity: O(V + 2E)

• We visit each vertex once and examine each edge once.

Space Complexity: O(3V)

• The visited array, the ans list, and the queue all use up to O(3V) space.

Conclusion

With just a few lines and Python’s deque, you can implement BFS and get the level-by-level order of any graph (or tree). BFS is essential not only for graph traversal but also for shortest-path problems, web crawling, and more. Mastering this pattern will boost your confidence for both GeeksforGeeks practice and coding interviews. Happy traversing!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.