How Do You Detect a Cycle in a Graph
💡 Concept Name
Cycle Detection in Graphs – The process of checking whether a graph contains a closed path, meaning you can start at a node and come back to it by following the edges. Techniques vary for directed and undirected graphs, but all aim to prevent infinite loops or circular dependencies.
📘 Quick Intro
Cycle detection is fundamental in graph theory, helping you spot feedback loops in networks, deadlocks in systems, and bugs in dependency chains. For undirected graphs, the Union-Find method and DFS with parent tracking are standard. For directed graphs, DFS with recursion tracking or Kahn’s Algorithm (topological sorting) are preferred.
🧠 Analogy / Short Story
Imagine organizing a relay race. If the baton keeps coming back to the same runner before the finish line, something is wrong—a cycle! Similarly, in a project where task A relies on B, B on C, and C again on A, you’re stuck running in circles with no end—an endless loop or cycle.
🔧 Technical Explanation
-
Undirected Graphs:
- DFS + Parent Tracking: Run DFS from every node. If you visit a neighbor that’s not the parent and already marked as visited, a cycle exists.
- Union-Find (Disjoint Set): Each edge connects nodes; if two nodes are already in the same set, a cycle is present.
-
Directed Graphs:
- DFS + Recursion Stack: Track nodes on the current path. If a node is revisited while still on the stack, you have a cycle.
- Kahn’s Algorithm (Topological Sort): If not all nodes can be removed (in-degree drops to zero), there’s a cycle.
- Time Complexity: Most cycle detection runs in O(V + E), where V = vertices, E = edges.
🎯 Purpose & Use Case
- ✅ Preventing deadlocks in operating systems and databases
- ✅ Detecting circular dependencies in compilers, package managers, and build tools
- ✅ Validating workflows and ensuring data pipelines or tasks don't loop forever
- ✅ Finding bugs in real-world networks (e.g., social media connections, internet routing)
💻 Real Code Example
// Detecting a cycle in a directed graph using DFS
bool HasCycle(List<int>[] graph, int v)
{
bool[] visited = new bool[v];
bool[] recStack = new bool[v];
for (int i = 0; i < v; i++)
if (DfsHasCycle(i, graph, visited, recStack))
return true;
return false;
}
bool DfsHasCycle(int node, List<int>[] graph, bool[] visited, bool[] recStack)
{
if (recStack[node])
return true;
if (visited[node])
return false;
visited[node] = true;
recStack[node] = true;
foreach (var neighbor in graph[node])
if (DfsHasCycle(neighbor, graph, visited, recStack))
return true;
recStack[node] = false;
return false;
}
❓ Interview Q&A
Q1: What is the simplest way to detect a cycle in an undirected graph?
A: Use DFS with parent tracking, or apply Union-Find to find repeated connections.
Q2: How does cycle detection differ in directed and undirected graphs?
A: Directed graphs require recursion stack or topological sort; undirected use parent tracking or disjoint sets.
Q3: What does Kahn’s Algorithm tell you about cycles?
A: If not all nodes are sorted (removed), a cycle is present.
Q4: Can a tree ever contain a cycle?
A: No. Trees are, by definition, acyclic connected graphs.
Q5: Why do we use Union-Find in undirected graphs?
A: To quickly check if two nodes already belong to the same component before adding an edge.
Q6: What are practical uses for detecting cycles?
A: Preventing infinite loops in task management, or circular dependencies in package management.
Q7: In DFS, what does it mean if you find a visited node on the recursion stack?
A: There is a cycle (the path loops back to itself).
Q8: Which real-world systems rely on cycle detection?
A: Operating system schedulers, workflow engines, dependency checkers, and even some networking protocols.
Q9: How can topological sort detect cycles?
A: If the sort cannot remove all nodes due to nonzero in-degree, a cycle exists.
Q10: What is the overall time complexity of standard cycle detection?
A: O(V + E) for both DFS and Union-Find methods.
📝 MCQs
Q1. Which approach uses a recursion stack to find cycles?
- DFS (Directed)
- BFS
- Dijkstra
- Prim
Q2. Cycle detection in undirected graphs can use?
- Kahn’s Algorithm
- Union-Find
- Bellman-Ford
- Breadth-First Search
Q3. What does topological sorting detect in graphs?
- Cycle in undirected
- Path length
- Cycles in directed graphs
- Spanning trees
Q4. What is the key in DFS-based cycle detection (directed)?
- Distance array
- Parent pointer
- Recursion stack
- Visited only
Q5. Which graph can never have a cycle?
- Tree
- Complete graph
- Graph with loop
- Bipartite
Q6. Union-Find is mainly for?
- Directed graphs
- Undirected graphs
- Trees
- Sparse graphs
Q7. If you visit a node twice in DFS (and it’s on stack), you have?
- No path
- A cycle
- A bridge
- Disconnected graph
Q8. Kahn’s algorithm is used for?
- Shortest path
- Topological sorting
- Finding leaves
- Cycle removal
Q9. Cycle detection is important in?
- Dependency management
- Sorting
- Searching
- Compression
Q10. Which operation is O(V + E) in cycle detection?
- DFS traversal
- Heapify
- Matrix inversion
- Graph coloring
💡 Bonus Insight
If you ever find your build system, database, or workflow engine “hanging forever,” suspect a hidden cycle! Mastering cycle detection will make you the go-to problem solver in code reviews, systems design, and tech interviews.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!