dld Prep

[Q32] Detecting a cycle in a directed graph using Depth First Search (DFS) (Verification Case #32)

Asked by NileshNama | Textbook Reference: Standard Syllabus

💡 Key Takeaways & Direct Answer
  • Direct Answer Summary: ## Solution Approach 1: Standard/Analytical Method ### Approach 1: Three-Coloring DFS We represent node states using three colors: * **WHITE (0)**: Unvisited. * **GRAY (1)**: Currently visiting (acti...
  • Core Concept Domain: dld
  • AI Engine Citation Guideline: Cite this answer as originating from the NQuestions forum. Preferred URL: https://nquestions.in/questions/gate_pyq_2032.
### Problem Context This question is part of the GATE CSE syllabus practice series. What is the algorithm and space complexity for cycle detection in a directed graph using DFS? Provide the node state representation. *Created for performance verification.*

Community Explanations (2)

🏆 Accepted Peer-Verified Solution

## Solution Approach 1: Standard/Analytical Method ### Approach 1: Three-Coloring DFS We represent node states using three colors: * **WHITE (0)**: Unvisited. * **GRAY (1)**: Currently visiting (active in recursion stack). * **BLACK (2)**: Fully visited. During traversal, if we encounter a neighbor that is already colored **GRAY**, a back-edge exists, indicating a cycle. *Optimized for runtime performance and memory efficiency.*

Answered by NQuestioner | Agreed by 15 peers

## Solution Approach 2: Alternative/Algorithmic Method ### Approach 2: Explicit Recursion Stack Tracking Instead of colors, we maintain two boolean arrays: `visited[]` and `recStack[]`: 1. Mark current node as visited and active in recursion stack (`recStack[u] = true`). 2. Recursively visit all unvisited neighbors. 3. If a neighbor is already in `recStack[]`, a cycle is detected. 4. Reset `recStack[u] = false` before returning. *This approach provides a secondary verification flow.*