DSA sheet · Graphs · Traversal pattern (BFS)

BFS Traversal of a Graph

This is the first real graph problem of the sheet. We visit every node of a graph level by level, starting from node 0, using a queue. If you did BFS on trees, the loop is almost the same. There are only two new things in a graph: the children come from an adjacency list, and we need a visited array, because a graph can lead you back to a node you already saw. Almost every later BFS problem (rotting oranges, word ladder, shortest path in a grid…) is this same code with small changes, so learn it until you can write it without thinking.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · BFS traversal from node 0 (the teacher's solution)
• Part B · Two small upgrades: levels & distances, edge lists & disconnected graphs
• Part C · Revision page

Part 0 · Before starting

Nodes and edges

A graph is a set of nodes (also called vertices; the count is usually written V) joined by edges (the count is E). An edge is just a line that says "these two nodes are connected".

• Undirected edge (0)—(1): you can walk 0 → 1 and also 1 → 0.
• Directed edge (0)→(1): you can walk 0 → 1 only.
• Weighted edge (0)—5—(1): walking it costs 5. With no number written, every edge costs 1.

A tree always has a root to start from. A graph has no root, so the question must tell you where to start. Here it says: start from node 0.

How the graph reaches your code

In this problem the adjacency list is already given, so we don't build anything. When a question gives an edge list instead, we build the list ourselves in one pass:

def build_adj(n, edges):
    adj = [[] for _ in range(n)]   # one empty list per node 0..n-1
    for u, v in edges:
        adj[u].append(v)           # u can go to v
        adj[v].append(u)           # undirected: v can also go to u
    return adj

For a directed edge u → v you would keep only the first append.

Why a visited array?

In a tree, going to the children always moves you down. In an undirected graph, if 0 is a neighbour of 2, then 2 is also a neighbour of 0. So from 2 you can step "back" to 0, then from 0 to 2 again… forever. A visited array (one True/False per node) remembers which nodes we already took. We only go to a neighbour that is not visited yet.

BFS in one picture

BFS (Breadth First Search) finishes all nodes at distance 1 from the start, then all at distance 2, and so on, like ripples in water. A queue (first in, first out) gives exactly this order: nodes found earlier are processed earlier. In Python we use collections.deque, because popleft() is O(1). (list.pop(0) shifts every element, which is O(n) per pop.)

The other traversal, DFS (go deep first), is the topic of Problem 5. Grids as graphs and connected components come in the next problems too.

Part A · BFS traversal from node 0

GFG: "BFS of graph"

1The question in simple words

You get a connected, undirected graph with V nodes numbered 0 … V−1, as an adjacency list adj. "Connected" means every node can be reached from every other node. Start at node 0, do a BFS, and return the nodes in the order you visit them. When a node has several neighbours, take them left to right, in the order they appear in adj.

The teacher's example (the same graph is used in the DFS video):

               (0)
             /  |  \
          (2)  (3)  (1)
           |   / \    \
          (4)(5) (6)  (7)

adj[0] = [2, 3, 1]     adj[4] = [2]
adj[1] = [0, 7]        adj[5] = [3]
adj[2] = [0, 4]        adj[6] = [3]
adj[3] = [0, 5, 6]     adj[7] = [1]

Expected answer: [0, 2, 3, 1, 4, 5, 6, 7]. Node 0 first (level 0), then its neighbours 2, 3, 1 (level 1), then 4, 5, 6, 7 (level 2).

2What the constraints tell us

• 1 ≤ V ≤ 10⁴ nodes → at least one node always exists, so node 0 is always there; no empty-graph case.
• The teacher's rule of thumb: about 10⁸ simple operations fit in the time limit. A linear solution (proportional to V + E) is tiny here, so aim for linear. Anything that rescans the whole input for each node is the kind of thing to avoid.
• Node values are at most 10⁴ → fit easily in a normal int (in Java/C++ an int holds about 2·10⁹; in Python ints never overflow).
• The graph is connected → one BFS from 0 reaches every node. (Part B shows what to do if it isn't.)

3Intuition: ripples from node 0

Drop a stone at node 0. The first ripple touches 0's neighbours. The next ripple touches their new neighbours, and so on. We write each node down when the ripple reaches it, so nearer nodes always come first.

A queue is the ripple: whatever we discover goes to the back, and we always take the next node from the front. So everything on level 1 is taken out before anything on level 2.

4Building the logic step by step

The teacher builds the code from the BFS on trees and asks at every line "what does the graph need differently?"

Step 1: a queue, and a start node

BFS always starts with a queue. In a tree we would put the root inside. A graph has no root, so we put the node the question names: 0.

Step 2: loop while the queue is not empty

As long as something is waiting in the queue, there is work to do. The loop can only end if we keep removing nodes, so each round we popleft() one node.

Step 3: do the node's work first, then go to its children

The question wants the visiting order, so the "work" is simple: append the popped node to ans. We do it right after the pop, before touching any neighbour.

Step 4: the children come from the adjacency list

In a tree the children are node.left and node.right. Here they are adj[node]. The node number is the index into the list: node 3's neighbours sit at adj[3], because both the nodes and the list are numbered from 0.

Step 5: why we can't push every neighbour

Suppose we push all neighbours without any check. Pop 0 → push 2, 3, 1. Pop 2 → its neighbours are 0 and 4 → we push 0 again! Later 0 is popped again, pushes 2, 3, 1 again, and the queue never empties. Infinite loop.

The fix is a visited array of size V, all False at the start. Before pushing a neighbour we ask "is it visited?". If yes, skip it. If no, push it and mark it visited right away.

5Approach steps

1. V = number of nodes = len(adj). Make visited = [False] * V and an empty ans.
2. Push 0 into a deque and mark visited[0] = True.
3. While the queue is not empty: pop the front node and append it to ans.
4. For each neighbour in adj[node], left to right: if it is not visited, mark it and push it.
5. When the queue is empty, return ans.

6Code (Python)

from collections import deque

class Solution:
    def bfs(self, adj):
        n = len(adj)                  # one sub-list per node
        visited = [False] * n
        ans = []

        queue = deque([0])            # the question says: start at 0
        visited[0] = True             # it entered the queue, so mark it

        while queue:
            node = queue.popleft()    # take the front node
            ans.append(node)          # its work: record the visit

            for nei in adj[node]:     # children, left to right
                if not visited[nei]:
                    visited[nei] = True     # mark when pushing
                    queue.append(nei)

        return ans

7Code line by line

8Dry run on the teacher's graph

        (0✓)
      /  |   \
   (2✓) (3✓) (1✓)
    |   / \     \
   (4) (5) (6)  (7)

        (0✓)
      /  |   \
   (2✓) (3✓) (1✓)
    |    / \     \
  (4✓)(5✓)(6✓) (7✓)

Every node is marked after step 4, but the loop still runs 4 more times to pop and record 4, 5, 6, 7. Marking means "found"; popping means "processed".

9Complexity & remember

• The while loop: each node enters the queue once (visited guarantees it) and leaves once → V rounds.
• The for loop looks like it could make this V × V, but it doesn't. Over the whole run, it walks every node's neighbour list exactly once. Node 0 has 3 neighbours, node 2 has 2, node 3 has 3, … Adding up the lengths of all lists gives the sum of the degrees (degree = number of edges touching a node), and that sum is 2E, since each undirected edge appears in two lists.
• Time O(V + E). Space O(V): the queue, the visited array and the answer each hold at most V items.

She also notes the space use is high on LeetCode/GFG, and that's expected: BFS needs a queue, the question needs an answer list, and the graph needs a visited array.

Part B · Two small upgrades

The teacher's code is complete for this question. The next problems need two small changes to it, so here they are while the code is fresh. (These are not in the video; they are the same BFS with one or two extra lines.)

1Level by level, and distance from the start

She points out that the answer is really 3 groups: 0 | 2 3 1 | 4 5 6 7. To get the groups explicitly, look at the queue at the start of a round: it holds exactly one whole level. So read len(queue) first and pop exactly that many.

A node's level is also its distance (fewest edges) from the start. BFS reaches a node first by the shortest route, because it finishes all nodes at distance d before any at distance d + 1. That's why BFS solves "minimum steps" questions on graphs where every edge costs 1.

from collections import deque

def bfs_levels(adj, src):
    n = len(adj)
    dist = [-1] * n              # -1 = not reached (also works as "visited")
    dist[src] = 0
    queue = deque([src])
    levels = []
    while queue:
        size = len(queue)        # exactly one level is in the queue now
        level = []
        for _ in range(size):
            node = queue.popleft()
            level.append(node)
            for nei in adj[node]:
                if dist[nei] == -1:          # not visited yet
                    dist[nei] = dist[node] + 1
                    queue.append(nei)
        levels.append(level)
    return levels, dist

On the teacher's graph: levels = [[0], [2, 3, 1], [4, 5, 6, 7]] and dist = [0, 1, 1, 1, 2, 2, 2, 2].

2Edge list input, and a graph that is not connected

If the input is an edge list, build the adjacency list first (Part 0). If the graph has several separate pieces (connected components), one BFS from 0 only reaches 0's piece. So loop over every node and start a new BFS from each node that is still unvisited. The number of BFS starts is the number of pieces; Problem 4 (Number of Provinces) is exactly this.

from collections import deque

def bfs_all(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * n
    order = []
    components = 0
    for start in range(n):           # try every node as a start
        if visited[start]:
            continue                 # already inside an earlier piece
        components += 1
        visited[start] = True
        queue = deque([start])
        while queue:                 # the same BFS as Part A
            node = queue.popleft()
            order.append(node)
            for nei in adj[node]:
                if not visited[nei]:
                    visited[nei] = True
                    queue.append(nei)
    return order, components

Example: n = 5, edges [[0,1],[3,4]] → pieces {0,1}, {2}, {3,4} → order = [0, 1, 2, 3, 4], components = 3. Node 2 has no edges, but it is still a piece of its own.

Part C · Revision page

adj = [[2, 3, 1], [0, 7], [0, 4], [0, 5, 6], [2], [3], [3], [1]]
print(Solution().bfs(adj))              # [0, 2, 3, 1, 4, 5, 6, 7]
print(Solution().bfs([[2, 1, 3], [0, 7], [0, 4], [0, 5, 6], [2], [3], [3], [1]]))  # [0, 2, 1, 3, 4, 7, 5, 6]
print(Solution().bfs([[]]))             # [0]
print(Solution().bfs([[1], [0, 2], [1, 3], [2]]))   # [0, 1, 2, 3]

Based on this video: BFS Traversal of Graph