Cycle Detection in Directed Graph in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a cycle in a directed graph?

A cycle in a directed graph is a path that starts and ends at the same vertex, following the direction of edges.

beginner

Which data structure is commonly used to detect cycles in a directed graph using DFS?

A recursion stack (or call stack) is used to keep track of vertices in the current path during DFS to detect cycles.

intermediate

What does it mean if a node is found in the recursion stack during DFS?

It means a cycle is detected because the node is already in the current path of traversal.

intermediate

Why can't we use a simple visited set alone to detect cycles in directed graphs?

Because a node can be visited multiple times in different paths; only tracking nodes in the current path (recursion stack) can detect cycles.

intermediate

What is the time complexity of cycle detection in a directed graph using DFS?

The time complexity is O(V + E), where V is vertices and E is edges, because each vertex and edge is visited once.

What indicates a cycle during DFS in a directed graph?

A Finding a node with no outgoing edges

B Finding a node already in the recursion stack

C Finding a node never visited before

D Finding a node with no incoming edges

A cycle is detected if a node is found in the recursion stack, meaning it is part of the current path.

Which of these is NOT used in cycle detection in directed graphs?

A Recursion stack

B Visited set

C Queue for BFS

D Adjacency list

Cycle detection in directed graphs commonly uses DFS with recursion stack and visited set, not BFS queue.

What is the purpose of the visited set in cycle detection?

A To store all edges

B To mark nodes currently in the path

C To store the cycle nodes

D To mark nodes that are fully processed

The visited set marks nodes that have been fully processed to avoid reprocessing.

If no cycle is found, what does the DFS finish with?

A All nodes visited and no node found in recursion stack twice

B Some nodes unvisited

C Recursion stack never emptied

D Cycle nodes stored

If DFS finishes visiting all nodes without finding a node in recursion stack twice, no cycle exists.

What is the main difference between cycle detection in directed and undirected graphs?

A Directed graphs use recursion stack; undirected graphs use parent tracking

B Directed graphs use BFS; undirected graphs use DFS

C Directed graphs have no cycles

D Undirected graphs do not need visited sets

Directed graphs detect cycles using recursion stack; undirected graphs detect cycles by checking visited nodes excluding the parent.

Explain how DFS with recursion stack helps detect cycles in a directed graph.

Think about how the current path is remembered during DFS.

Describe the difference between visited set and recursion stack in cycle detection.

Consider what each set tracks during DFS.