DSA sheet · Graphs · Cycle detection pattern (BFS)

Detect a Cycle in an Undirected Graph (BFS)

The same question as Problem 11 (does an undirected graph have a loop?), solved again with BFS: a queue that explores the graph level by level. The rule doesn't change: a neighbour that is already visited and is not my parent means a cycle. What changes is where the parent is kept: in DFS it was a function argument; in BFS it travels inside the queue, next to the node, as a pair (node, parent). The teacher also shows that the "story" of the cycle sounds different in BFS, even though the code check is identical.

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 · Cycle detection with BFS + parent (the teacher's solution)
• Part B · Revision page (with DFS vs BFS)

Part 0 · Before starting

Graph words used on this page

• Node (vertex), edge; V nodes numbered 0 … V−1, E edges.
• Undirected: an edge (u)—(v) works both ways. (Directed edges (u)→(v) work one way; that's Problem 12. Weighted edges carry a cost; not used here.)
• Cycle: a walk that returns to its starting node without reusing an edge, like a triangle 0—1—2—0.
• Adjacency list: graph[u] = the neighbours of u. The input is an edge list (pairs [u, v]); we build the list and add every edge in both directions. (An adjacency matrix, V×V, is too big for V = 10⁵.)
• Visited array: one mark per node, so nothing is processed twice and the search can't run forever.
• Connected components: separate pieces of the graph. The graph may have several, so we start a search from every node not yet visited.

V = 4
edges = [[0, 1], [0, 2], [1, 2], [2, 3]]

graph = [[] for _ in range(V)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)        # both ways

print(graph)   # [[1, 2], [0, 2], [0, 1, 3], [2]]

BFS in 5 lines (Problem 3 has the full version)

• Use a queue: add at the back, take from the front. In Python, collections.deque with append and popleft, both O(1).
• Put the start node in and mark it visited.
• Repeat until the queue is empty: take the front node, look at its neighbours, and push every neighbour that isn't visited yet (marking it as you push).
• This visits the start, then all nodes 1 edge away, then all 2 edges away, and so on: level by level.
• The teacher's remark: DFS uses a stack (Python's call stack, hidden inside recursion), but for BFS we create the queue ourselves.

Recap of the DFS version (Problem 11)

In DFS, each call knew its parent (the node it came from). Seeing the parent again is normal, because the edge we came along is stored in both lists. Seeing any other visited node means we reached it a second way, so there's a loop. We keep exactly this rule.

Part A · Cycle detection with BFS + parent

GFG: "Undirected Graph Cycle"

1The question in simple words

Given V and an edge list of an undirected graph (possibly in several pieces), return True if there is a cycle anywhere, else False.

  (0)———(1)
    \   /
     (2)———(3)

  (0)———(1)      (4)
    \
     (2)———(3)

2What the constraints tell us

• V and E up to 10⁵ → we need a linear O(V + E) solution; O(V²) would be around 10¹⁰ steps, which is TLE.
• Several components → an outer loop over all nodes, starting a BFS only from unvisited ones.
• A nice side effect of BFS in Python: no recursion, so no recursion-limit worries even for a 10⁵-node line.

Why the outer loop starts at 0 and goes to V−1

The teacher's example: nodes 0, 1, 2 form a triangle (a cycle), and nodes 3, 4 form a separate piece with no cycle. If you only started a search at 3, you'd never see the triangle. Starting at 0 isn't magic: any order works as long as every node gets a chance. Going 0, 1, 2, … simply makes sure no piece is skipped.

  (0)———(1)        (3)———(4)
    \   /
     (2)            start only at 3 → "no cycle" ✗   loop over all nodes → True ✓

3Intuition: two parents claim the same child

BFS spreads out from the start like a ripple in water. Each node is "discovered" by exactly one node: its parent, the one that first pushed it into the queue.

Now suppose node 1 looks at its neighbour 2, and 2 is already visited, and 2 is not 1's parent. Who discovered 2? Some other node (here 0). So 2 can be reached from the start in two different ways: through 0, and through 1. Two different routes to the same node join up into a loop. The teacher tells it as a conversation:

• Node 1: "I never visited 2, but 2 is my neighbour, and it's already marked."
• Node 0: "That was me. 2 is my child; I visited it."
• So 2 is the child of 0 and also a neighbour of 1, while 1 is itself a child of 0 → 0—1—2—0 is a cycle.

In DFS the story was a single walk 0 → 1 → 2 that bumps back into 0. In BFS it's two branches that meet. The stories differ, but the code check is the same: visited and not my parent. Her everyday picture: you're on a trip and spot a mall you have already seen earlier. You must have looped round.

4Building the logic from her example

Point 1: the queue must hold the parent too

In plain BFS the queue holds only nodes. But the rule needs "who is my parent?" when we look at a node's neighbours. There's no recursion here to carry it, so the parent travels with the node: we push the pair (node, parent). The start has no parent, so it goes in as (start, -1).

Point 2: why the parent check is needed (counter-example)

  (0)———(1)
  graph[0] = [1]
  graph[1] = [0]

  pop (0, −1): 1 new → push (1, 0)
  pop (1, 0):  0 is visited → "cycle" ✗ WRONG
  with the check: 0 is my parent → ignore ✓

Exactly as in DFS: every undirected edge is stored both ways, so a node always sees the node it came from. That alone is not a loop.

Point 3: unvisited neighbour → push it with me as its parent, and mark it right away

If the neighbour is not visited, push (nb, node): the current node becomes its parent. The teacher's question here: should we push a neighbour that's already visited? No. In her example, 1's neighbours are 0 and 2; pushing 0 again would send us back and forth forever. So we push only unvisited neighbours.

And she marks a node visited at the moment it is pushed, not when it is popped. The start node is pushed before the loop, so it's marked before the loop too.

Point 4: visited neighbour → check the parent

If the neighbour is visited and it is my parent → fine, skip. If it is visited and not my parent → return True.

            start
           /     \
         ...      ...       (parent links)
         /          \
        u ——————————— w     u—w is not a parent link → loop

Point 5: when the queue empties

If the queue runs out and we never returned True, this whole component has no cycle → return False for it. The outer loop then moves on to the next unvisited node.

5Approach steps

1. Build the adjacency list (both ways) and visited = [False] * V.
2. For each node i not yet visited: if bfs(i) is True → return True.
3. In bfs(start): push (start, -1) and mark start visited.
4. While the queue isn't empty: pop (node, parent).
5. For each neighbour: not visited → mark it and push (nb, node). Visited and ≠ parent → return True.
6. Queue empty → return False.
7. After the outer loop → return False.

6Code (Python)

from collections import deque

class Solution:
    def isCycle(self, V, edges):
        graph = [[] for _ in range(V)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = [False] * V
        for i in range(V):                 # one BFS per component
            if not visited[i]:
                if self.bfs(i, graph, visited):
                    return True
        return False

    def bfs(self, start, graph, visited):
        queue = deque()
        queue.append((start, -1))          # (node, parent); start has no parent
        visited[start] = True
        while queue:
            node, parent = queue.popleft()
            for nb in graph[node]:
                if not visited[nb]:
                    visited[nb] = True         # mark when pushing
                    queue.append((nb, node))   # I am nb's parent
                elif nb != parent:             # discovered by someone else
                    return True
        return False

Compared with the DFS code of Problem 11, the teacher changes only the helper: dfs(node, parent) becomes bfs(start), and the parent moves from the argument list into the queue pairs. The outer loop is untouched.

7Code line by line

8Dry run

Dry run 1: the teacher's graph (cycle)

V = 4, edges [[0,1],[0,2],[1,2],[2,3]] → graph 0:[1,2] · 1:[0,2] · 2:[0,1,3] · 3:[2]. Queue entries are written (node, parent).

  snapshot at step 2 ([x] = visited, * = node being processed)
  [0]———[1]*
     \   /
      [2]———(3)      1 sees 2 already discovered by 0 → two routes to 2 → loop 0-1-2

Node 3 is never even discovered: we stop at the first cycle. Notice that (2, 0) is still waiting in the queue when 1 sees it; that's fine (see the doubt above).

Dry run 2: no cycle, two components

V = 5, edges [[0,1],[0,2],[2,3]] → graph 0:[1,2] · 1:[0] · 2:[0,3] · 3:[2] · 4:[].

  level 0:  [0]
  level 1:  [1] [2]          every visited neighbour seen was the parent
  level 2:      [3]          → no second route anywhere → no cycle
  separate: [4]

9Complexity & remember

• Time O(V + 2E). Each node is pushed and popped once (V). The for loop over neighbours is not "V × V": in total it runs once per adjacency entry. Her count on the example: node 0 → 2 times, node 1 → 2, node 2 → 3, node 3 → 1, total 8 = 2 × 4 edges. In general the degrees add up to 2E. When E is about V, that's about 3V: linear.
• Space O(V + 2E): the adjacency list stores every edge twice (2E entries over V lists). The queue holds each node at most once (O(V)), and visited is O(V).
• DFS or BFS? Same time and space on paper. The teacher notes that BFS may run slightly slower in practice because of the queue's own overhead, but that's an implementation detail. In an interview, either is fine.

Part B · Revision page

s = Solution()
print(s.isCycle(4, [[0, 1], [0, 2], [1, 2], [2, 3]]))   # True
print(s.isCycle(5, [[0, 1], [0, 2], [2, 3]]))           # False
print(s.isCycle(2, [[0, 1]]))                           # False
print(s.isCycle(5, [[3, 4], [0, 1], [1, 2], [2, 0]]))   # True
print(s.isCycle(1, []))                                 # False

Based on this video: Detect Cycle in an Undirected Graph using BFS