Video summary

G-11. Detect a Cycle in an Undirected Graph using BFS | C++ | Java

Main summary

Key takeaways

Educational

Main idea / concept

  • Use Breadth-First Search (BFS) to detect cycles in an undirected graph.
  • Key observation: while doing BFS from a source, if you encounter a neighbor that is already visited and that neighbor is not the current node’s parent, then there is a cycle.
  • Handle disconnected graphs by running the BFS-based cycle check from every unvisited vertex (so every component is checked).

In an undirected graph, two different BFS paths reaching the same node (at the same or different levels) where the previously visited node is not the immediate parent indicates a cycle.

Detailed methodology (step-by-step algorithm)

  1. Data structures

    • Adjacency list for the graph.
    • visited array of size V, initialized to false.
    • Queue that stores pairs (node, parent) so each queued node remembers which node it came from.

  2. Handle disconnected graphs

    • Loop over all vertices (e.g., 0..n-1 or 1..n depending on indexing).
    • If vertex i is not visited, call detectCycle(i).

  3. BFS-based detectCycle(source)

    • Mark visited[source] = true.
    • Enqueue (source, parent = -1) into the queue.
    • While the queue is not empty:
      • Dequeue (node, parent).
      • For each neighbor adj of node:
        • If adj is not visited:
          • Mark visited[adj] = true.
          • Enqueue (adj, parent = node).
        • Else (if adj is already visited):
          • If adj != parent: return true (cycle found).
          • If adj == parent: ignore (edge back to parent).
    • If BFS finishes without finding such a visited-but-not-parent neighbor, return false (no cycle in this component).

  4. Final decision

    • If any component’s detectCycle returns true, the graph has a cycle.
    • If none return true after checking all components, the graph is acyclic.

Important implementation details & tips

  • Store parent information in the queue (e.g., pair<node, parent>) rather than trying to infer parent later.
  • Mark nodes as visited when you enqueue them (not when you dequeue) to prevent multiple enqueues and make the visited-check reliable.
  • The parent check is necessary because in undirected graphs the neighbor that is the parent will always be visited — that should not be treated as a cycle.
  • Pay attention to indexing: examples in the video use zero-based indexing (0..n-1); adjust loops/arrays if using one-based indexing (1..n).
  • For multiple components, use a single global visited array and only call detectCycle on unvisited nodes.

Intuition / example

BFS explores neighbors level by level. Two nodes explored from different branches can both reach the same subsequent node; if one branch visits it first and the other later finds it already visited and it’s not its parent, that collision indicates a cycle.

Example (from the video): nodes 5 and 6 both reach node 7 — this collision signals a cycle.

Complexity

  • Time: O(V + E) — BFS visits every vertex and inspects every edge at most twice in an undirected graph.
  • Space: O(V) for the visited array and the queue (plus adjacency list storage).

Other notes

  • The video shows implementations in C++ (primary) and Java (simultaneously).
  • A DFS-based approach to cycle detection in undirected graphs is covered in a later video.

Speakers / sources featured

  • Video narrator / presenter (unnamed instructor; single speaker throughout).

Original video