Scribd
Upload
8 views3 pages

Dfs Patterns Guide

DFS (Depth-First Search) is an algorithm for exploring branches in graphs, trees, and grids by going as deep as possible before backtracking. It is applicable in various scenarios such as connected components, backtracking, tree traversal, and path problems. To effectively use DFS, it is important to implement visited tracking and base conditions while practicing different problem categories.

Uploaded by

Prabhat Mutreja
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views3 pages

Dfs Patterns Guide

DFS (Depth-First Search) is an algorithm for exploring branches in graphs, trees, and grids by going as deep as possible before backtracking. It is applicable in various scenarios such as connected components, backtracking, tree traversal, and path problems. To effectively use DFS, it is important to implement visited tracking and base conditions while practicing different problem categories.

Uploaded by

Prabhat Mutreja
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DFS (Depth-First Search) Mastery Guide

🧠 What Is DFS?
DFS is an algorithm for exploring as far as possible along each branch before backtracking. It is especially
useful in grid, graph, and tree problems.

🛠️ DFS Skeleton Templates

Tree or Graph:

def dfs(node):
if not node or node in visited:
return
[Link](node)
for neighbor in [Link]:
dfs(neighbor)

Grid (Matrix):

def dfs(r, c):


if (r, c) is invalid or already visited or blocked:
return
mark (r, c) as visited
for dr, dc in directions:
dfs(r + dr, c + dc)

💡 Recognize DFS Use Cases

Pattern Description

Connected Components Number of Islands, Flood Fill

Backtracking Subsets, Permutations, Palindrome Partitioning

Tree Traversal Preorder, Inorder, Postorder

Path Problems Path Sum, All Paths to Leaf

Graph Problems Clone Graph, Detect Cycles

1
Pattern Description

Topological Sort DFS on Directed Acyclic Graph

Search in Matrix Word Search, Pacific Atlantic Water Flow

🔄 DFS with Backtracking


Used in problems where we build a solution path and then backtrack:

def dfs(path, options):


if end_condition:
[Link]([Link]())
return
for option in options:
[Link](option)
dfs(path, new_options)
[Link]() # Backtrack

🧐 Key Concepts

Concept Purpose

Visited Set / Grid Prevents revisiting

Recursion Stack Natural DFS structure

Backtracking Undo choices to explore all options

Global Variables Track answer across all paths

Base Case First Stop condition before recursion

🚩 When To Think DFS First


Ask yourself:

• Can I go from here to there, in multiple ways?


• Do I need to explore every possible path?
• Am I building combinations/subsets?
• Is it a recursive definition?
• Is it a connected components/area problem?

2
If yes → Use DFS

🎯 Practice Categories

Category Problems to Try

Tree DFS Max Depth, Path Sum, Symmetric Tree

Grid DFS Number of Islands, Flood Fill, Word Search

Backtracking Subsets, Permutations, Sudoku, N-Queens

Graph DFS Clone Graph, Detect Cycle, Topological Sort

🌍 Summary
• DFS is ideal for exploring deeply before retreating.
• Use DFS for recursion-heavy, path-based, or exhaustive problems.
• Always guard your DFS with base conditions and visited tracking.
• Master DFS by categorizing problems and practicing templates.

Want the BFS version next?

yes

You might also like