How do you detect a cycle in a directed graph?

You can detect cycles in a directed graph by using DFS with a recursion stack or Kahn’s Algorithm (topological sort). A cycle exists if you revisit a node on the current recursion stack, or if topological sort fails to visit all nodes.

How do you detect a cycle in an undirected graph?

Cycle detection in undirected graphs can be achieved using DFS with parent tracking, or by using the Union-Find (Disjoint Set) structure to identify connections that would create a loop.

How Do You Detect a Cycle in a Graph | FullStackPrep.Dev

💡 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!

📄 PDF Download Coming Soon

How Do You Detect a Cycle in a Graph