Intermediate LevelData Structures & Algorithms
How do you detect a cycle in an undirected and directed graph?
ā Interview Prompt: Detect cycles in undirected graphs using DFS parent tracking and in directed graphs using DFS recursion stack (coloring).
Undirected Graph ā DFS with Parent Tracking:
During DFS, if we visit a neighbour that is already visited AND is not the parent of the current node ā cycle detected.
Directed Graph ā DFS with Recursion Stack (Coloring):
Use 3 colors:
ā¢
0 (White): Not visited.
ā¢
1 (Gray): Currently in the recursion stack (being explored).
ā¢
2 (Black): Fully processed.
If we reach a Gray neighbour ā back edge ā cycle!
Code Implementation Example
typescript
// Directed graph cycle detection
function hasCycleDirected(numNodes: number, edges: number[][]): boolean {
const adj: number[][] = Array.from({ length: numNodes }, () => []);
for (const [u, v] of edges) adj[u].push(v);
const color = new Array(numNodes).fill(0); // 0=white, 1=gray, 2=black
function dfs(u: number): boolean {
color[u] = 1; // mark gray (in stack)
for (const v of adj[u]) {
if (color[v] === 1) return true; // back edge = cycle!
if (color[v] === 0 && dfs(v)) return true;
}
color[u] = 2; // mark black (done)
return false;
}
for (let i = 0; i < numNodes; i++)
if (color[i] === 0 && dfs(i)) return true;
return false;
}š”DFS 3-color cycle detection for directed graphs.
šÆ Interview Key Takeaway
Undirected cycle: DFS + parent check. Directed cycle: DFS + recursion stack (gray color). Both O(V+E).
#DSA#Graph#Cycle Detection#DFS#Intermediate
Back to all Data Structures & Algorithms Questionsā