Depth-First Search (DFS)

DSA · Graphs

Theory

DFS explores as far as possible along one branch before backtracking, using recursion or an explicit stack and a visited set. It visits every reachable vertex in O(V + E) time. DFS is the basis for detecting cycles, finding connected components, topological sorting and solving mazes.

Why we use it

It explores complete paths and naturally fits recursive problems on graphs and grids.

When to use it

Use DFS to check connectivity, count islands in a grid, detect cycles, topological sort, and explore all paths (backtracking).

How it works

  1. dfs(u): mark u visited
  2. For each neighbour v of u
  3. v not visited? Yes: dfs(v). No: Skip.
  4. Backtrack when all neighbours are done

Syntax

def dfs(v):
    visited.add(v)
    for nb in graph[v]:
        if nb not in visited:
            dfs(nb)

Time: O(V + E)   Space: O(V)

Example

grid = [
    "11000",
    "11000",
    "00100",
    "00011",
]
rows, cols = len(grid), len(grid[0])
seen = set()

def dfs(r, c):
    if r < 0 or c < 0 or r >= rows or c >= cols:
        return
    if grid[r][c] != "1" or (r, c) in seen:
        return
    seen.add((r, c))
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)

islands = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == "1" and (r, c) not in seen:
            islands += 1
            dfs(r, c)
print("Number of islands:", islands)

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic