Cycle Detection in Directed Graph in DSA C - 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 structures are commonly used to detect cycles in a directed graph?

Depth-First Search (DFS) with recursion stack or colors (white, gray, black) is commonly used to detect cycles in directed graphs.

intermediate

What does the recursion stack represent in DFS cycle detection?

The recursion stack keeps track of vertices currently in the path of DFS. If a vertex is revisited while still in the recursion stack, a cycle exists.

intermediate

Explain the color method for cycle detection in directed graphs.

Vertices are colored white (unvisited), gray (visited but not finished), or black (finished). Encountering a gray vertex during DFS means a cycle is detected.

intermediate

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

Because revisiting a vertex that is already visited but not in the current DFS path does not mean a cycle. We need to track the current path (recursion stack or colors) to detect cycles.

What indicates a cycle during DFS in a directed graph?

A Visiting a vertex with only one incoming edge

B Visiting a vertex that is currently in the recursion stack

C Visiting a vertex with no outgoing edges

D Visiting a vertex that was visited in a previous DFS call

A cycle is detected if DFS visits a vertex that is still in the recursion stack (current path).

Which color represents a vertex that is currently being explored in the color method?

A Gray

B White

C Black

D Blue

Gray means the vertex is visited but DFS has not finished exploring all its descendants.

What is the time complexity of cycle detection using DFS in a directed graph with V vertices and E edges?

A O(V + E)

B O(V^2)

C O(E^2)

D O(V * E)

DFS visits each vertex and edge once, so the time complexity is O(V + E).

If no cycle is found in a directed graph, what does that imply about the graph?

A The graph is a tree

B The graph is disconnected

C The graph has no edges

D The graph is acyclic

No cycle means the graph is acyclic, also called a Directed Acyclic Graph (DAG).

Which of the following is NOT a valid method to detect cycles in a directed graph?

A DFS with recursion stack

B Color method with white, gray, black

C Breadth-First Search (BFS) with queue only

D Topological sort failure detection

BFS alone cannot detect cycles in directed graphs without additional mechanisms.

Describe how DFS can be used to detect a cycle in a directed graph.

Think about how to know if a vertex is revisited in the current path.

Explain the difference between visited array and recursion stack in cycle detection.

Focus on why just knowing if a vertex was visited before is not enough.