Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Visualization
Interactive visualization for Depth-First Search (DFS)
Interactive visualization with step-by-step execution
Implementation
1function dfs(graph: Map<number, number[]>, start: number): number[] {
2 const visited = new Set<number>();
3 const result: number[] = [];
4
5 function traverse(node: number): void {
6 if (visited.has(node)) return;
7 visited.add(node);
8 result.push(node);
9
10 const neighbors = graph.get(node) || [];
11 for (const neighbor of neighbors) {
12 traverse(neighbor);
13 }
14 }
15
16 traverse(start);
17 return result;
18}Deep Dive
Theoretical Foundation
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack data structure (either implicitly through recursion or explicitly with an iterative approach). DFS starts at a source vertex, marks it as visited, then recursively explores each unvisited adjacent vertex. When a vertex has no unvisited neighbors, the algorithm backtracks to explore other paths. DFS is similar to preorder tree traversal. The algorithm maintains a visited array to avoid infinite loops in graphs with cycles. DFS can be used for both directed and undirected graphs, and it's particularly efficient for problems that require exploring all possible paths or detecting cycles.
Complexity
Time
O(V + E)
O(V + E)
O(V + E)
Space
O(V)
Applications
Industry Use
Maze solving and pathfinding in games
Topological sorting for task scheduling
Cycle detection in dependency resolution
Finding strongly connected components
Solving puzzles with backtracking (Sudoku, N-Queens)
Web crawlers for deep link exploration
Version control systems (Git) for commit history
Network connectivity testing
Detecting deadlocks in operating systems
AI game playing algorithms (Chess, Go)
Use Cases
Related Algorithms
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.
Kruskal's Algorithm
Minimum Spanning Tree algorithm using greedy approach and Union-Find data structure. Sorts edges by weight and selects minimum weight edges that don't create cycles. Named after Joseph Kruskal, it's one of the most efficient MST algorithms for sparse graphs.