Is the Graph DFS — cycles, components, and back-edges lesson free?

Yes. The first 5 lessons on PyRun are free forever — no signup, no card. Graph DFS — cycles, components, and back-edges runs real Python in your browser via Pyodide.

How long does the Graph DFS — cycles, components, and back-edges lesson take?

About 13 minutes end-to-end. It's a hands-on lesson — you read a paragraph, edit the code, and run it in the same tab.

Do I need to install Python to try the Graph DFS — cycles, components, and back-edges lesson?

No install required. PyRun runs real CPython in your browser via Pyodide (Python compiled to WebAssembly). Works on Chrome, Firefox, Safari, and Edge — desktop or mobile.

What level is the Graph DFS — cycles, components, and back-edges lesson?

Advanced level. Assumes comfort with classes, functions, and standard library. Not for first-time Python learners.

← All lessons

Advanced·13 min·dsa · graphs · dfs · interview

Graph DFS — cycles, components, and back-edges

Graph DFS

Depth-first search plunges as deep as possible along one path before backtracking. Where BFS explores in rings, DFS drills a tunnel — different order, different applications, same O(V + E) cost.

Two ways to write it

Recursive DFS is almost the definition. Iterative DFS uses an explicit stack — matters when depth exceeds Python's recursion limit (~1000 frames).

Connected components

Loop over every node. If unseen, run DFS from it — everything reached is one component. Count outer starts = number of components.

Cycle detection

Two flavours, easy to confuse:

Undirected: cycle exists if DFS finds a neighbour that's already visited and isn't the parent it came from. Track (node, parent) on stack.
Directed: track three colours — WHITE (unseen), GRAY (on current stack), BLACK (fully processed). A GRAY neighbour = back-edge = cycle. Plain 'visited' check is wrong for directed.

When DFS beats BFS

Finding any path (not shortest).
Topological sort.
Strongly connected components.
Backtracking search — permutations, N-queens, sudoku.

Common bugs to avoid

Recursion depth on long chains. Switch to iterative or raise limit.
Undirected cycle check without parent. Every edge u-v looks like a cycle.
Directed cycle check using just 'visited'. DAG paths that reconverge falsely report a cycle.

Try it

Rewrite the undirected cycle check recursively.
Add directed-graph cycle detector using WHITE/GRAY/BLACK. Test on [(0,1),(1,2),(2,0)] (cycle) vs [(0,1),(0,2),(1,2)] (DAG).

Practice

3 graded exercises

Write the code, click Check. We’ll tell you exactly what to fix.

Progress0 / 3

Exercise 1
Write dfs_order(graph, start) that returns nodes in the order a recursive DFS visits them. Visit neighbors in the order they appear in the adjacency list.
Exercise 2
Write path_exists(graph, src, dst) returning True if there's any path from src to dst, else False. A node reaches itself. Use DFS.
Exercise 3
Write count_components(graph) returning how many connected components the undirected graph has. Consider every key in graph as a node, even ones with an empty neighbor list.

← PreviousGraph BFS — shortest paths on unweighted graphs Next →Topological Sort — ordering DAGs

Graph DFS — cycles, components, and back-edges

Graph DFS

Depth-first search plunges as deep as possible along one path before backtracking. Where BFS explores in rings, DFS drills a tunnel — different order, different applications, same O(V + E) cost.

Two ways to write it

Recursive DFS is almost the definition. Iterative DFS uses an explicit stack — matters when depth exceeds Python's recursion limit (~1000 frames).

Connected components

Loop over every node. If unseen, run DFS from it — everything reached is one component. Count outer starts = number of components.

Cycle detection

Two flavours, easy to confuse:

Undirected: cycle exists if DFS finds a neighbour that's already visited and isn't the parent it came from. Track (node, parent) on stack.
Directed: track three colours — WHITE (unseen), GRAY (on current stack), BLACK (fully processed). A GRAY neighbour = back-edge = cycle. Plain 'visited' check is wrong for directed.

When DFS beats BFS

Finding any path (not shortest).
Topological sort.
Strongly connected components.
Backtracking search — permutations, N-queens, sudoku.

Common bugs to avoid

Recursion depth on long chains. Switch to iterative or raise limit.
Undirected cycle check without parent. Every edge u-v looks like a cycle.
Directed cycle check using just 'visited'. DAG paths that reconverge falsely report a cycle.

Try it

Rewrite the undirected cycle check recursively.
Add directed-graph cycle detector using WHITE/GRAY/BLACK. Test on [(0,1),(1,2),(2,0)] (cycle) vs [(0,1),(0,2),(1,2)] (DAG).

Practice

3 graded exercises

Write the code, click Check. We’ll tell you exactly what to fix.

Progress0 / 3

Exercise 1
Write dfs_order(graph, start) that returns nodes in the order a recursive DFS visits them. Visit neighbors in the order they appear in the adjacency list.
Exercise 2
Write path_exists(graph, src, dst) returning True if there's any path from src to dst, else False. A node reaches itself. Use DFS.
Exercise 3
Write count_components(graph) returning how many connected components the undirected graph has. Consider every key in graph as a node, even ones with an empty neighbor list.