DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master DFS traversal using recursion and stack, understand pre/post ordering, cycle detection, and connected component discovery.
The Intuition
Imagine exploring a maze. Instead of checking all nearby paths first (like BFS), you pick one direction and go as deep as possible until you hit a dead end. Then you backtrack to the last junction and try a different path. This "go deep, then backtrack" strategy is DFS.
DFS is like a curious explorer who always wants to see what is around the next corner before checking alternatives. It dives deep into one branch of the graph before exploring others.
How DFS Works
DFS uses a stack (explicitly or via recursion's call stack):
- Start at the source vertex, mark it visited
- For each unvisited neighbor, recursively visit it (go deeper)
- When all neighbors are explored, backtrack
The recursive nature makes DFS elegant and natural for problems involving paths, components, and cycles.
Dry Run Example
Graph
0 --- 1 --- 4
| |
2 --- 3
DFS from vertex 0 (choosing lowest-numbered neighbor first)
Visit 0 → go to neighbor 1
Visit 1 → go to neighbor 3 (0 already visited)
Visit 3 → go to neighbor 2 (1 already visited)
Visit 2 → all neighbors visited, backtrack
Back to 3 → backtrack
Back to 1 → go to neighbor 4
Visit 4 → all neighbors visited, backtrack
Back to 1 → backtrack
Back to 0 → all neighbors explored
DFS Order: 0, 1, 3, 2, 4
Python Implementation
Example
def dfs_recursive(graph, start, visited=None):
"""Basic recursive DFS."""
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited
def dfs_iterative(graph, start):
"""Iterative DFS using explicit stack."""
visited = set()
stack = [start]
order = []
while stack:
vertex = stack.pop()
if vertex in visited:
continue
visited.add(vertex)
order.append(vertex)
# Add neighbors in reverse to process in order
for neighbor in reversed(graph[vertex]):
if neighbor not in visited:
stack.append(neighbor)
return order
def dfs_with_timestamps(graph, n):
"""DFS with discovery and finish times (pre/post order)."""
visited = [False] * n
discovery = [0] * n
finish = [0] * n
time = [0] # Mutable container for closure
def dfs(u):
visited[u] = True
time[0] += 1
discovery[u] = time[0]
for v in graph[u]:
if not visited[v]:
dfs(v)
time[0] += 1
finish[u] = time[0]
for i in range(n):
if not visited[i]:
dfs(i)
return discovery, finish
Cycle Detection
One of DFS's most important applications is detecting cycles.
In Undirected Graphs
Example
def has_cycle_undirected(graph, n):
"""Detect cycle in undirected graph using DFS."""
visited = [False] * n
def dfs(node, parent):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(neighbor, node):
return True
elif neighbor != parent:
# Found a visited node that isn't parent = cycle!
return True
return False
for i in range(n):
if not visited[i]:
if dfs(i, -1):
return True
return False
In Directed Graphs (Three-Color Method)
Example
def has_cycle_directed(graph, n):
"""Detect cycle in directed graph using coloring."""
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
def dfs(node):
color[node] = GRAY # Currently being explored
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True # Back edge = cycle!
if color[neighbor] == WHITE:
if dfs(neighbor):
return True
color[node] = BLACK # Fully explored
return False
for i in range(n):
if color[i] == WHITE:
if dfs(i):
return True
return False
C++ Implementation
Example
#include <vector>
#include <stack>
using namespace std;
void dfsRecursive(vector<vector<int>>& graph, int node, vector<bool>& visited) {
visited[node] = true;
// Process node here
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfsRecursive(graph, neighbor, visited);
}
}
}
// Find all connected components
int countComponents(vector<vector<int>>& graph, int n) {
vector<bool> visited(n, false);
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfsRecursive(graph, i, visited);
components++;
}
}
return components;
}
Time and Space Complexity
- Time: O(V + E) — visits every vertex and edge once
- Space: O(V) — for visited array + recursion stack (or explicit stack)
- Warning: For very deep graphs, recursive DFS can cause stack overflow. Use iterative version for graphs with depth > ~1000.
DFS vs BFS
| Feature | DFS | BFS |
|---|---|---|
| Data structure | Stack/Recursion | Queue |
| Exploration | Goes deep first | Goes wide first |
| Shortest path | No (for unweighted) | Yes (for unweighted) |
| Memory | O(depth) | O(width) |
| Cycle detection | Natural | Possible but less elegant |
| Topological sort | Natural | Via Kahn's algorithm |
| Best for | Paths, components, cycles | Shortest path, levels |
Applications of DFS
- Cycle detection in directed and undirected graphs
- Topological sorting of DAGs
- Finding connected components (undirected) and strongly connected components (directed)
- Path finding (find ANY path, not necessarily shortest)
- Maze generation (randomized DFS creates good mazes)
- Solving puzzles (backtracking is DFS with pruning)
- Detecting bridges and articulation points in networks
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Depth-First Search (DFS) Algorithm.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, graphs, dfs, algorithm
Related Data Structures & Algorithms Topics
Continue learning this concept
GraphsBellman-Ford AlgorithmLearn Bellman-Ford shortest path algorithm that handles negative edge weights, detects negative cycles, with complete implementation and analysis.GraphsBreadth-First Search (BFS) AlgorithmLearn BFS traversal with queue-based implementation, level-order processing, shortest path in unweighted graphs, and real applications.GraphsDijkstra\Master Dijkstra\GraphsFloyd-Warshall AlgorithmMaster the all-pairs shortest path algorithm using dynamic programming with three nested loops, path reconstruction, and practical applications.GraphsKruskal\Learn Kruskal\GraphsPrim\Master Prim\