Graph DFS
MediumDepth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Used for topological sorting and cycle detection.
Time Complexity
O(V + E)Space Complexity
O(V)Category
Graph
Introduction to Depth-First Search (DFS)
DFS is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's one of the most important algorithms for graph problems and has numerous applications.
How It Works
DFS can be implemented using recursion or an explicit stack:
**Recursive Approach**:
1. Visit a vertex and mark it as visited
2. Recursively visit all unvisited neighbors
3. Backtrack when all neighbors are visited
**Stack-based Approach**:
1. Push starting vertex onto stack
2. While stack is not empty:
- Pop vertex from stack
- If not visited, mark as visited
- Push all unvisited neighbors
Algorithm Complexity
Key Characteristics
1. Uses stack (LIFO) - either explicit or call stack
2. Explores deeply before exploring siblings
3. Can find connected components
4. Good for topological sorting
5. Useful for cycle detection
Advantages
1. Simple implementation using recursion
2. Memory efficient for breadth-limited graphs
3. Good for finding connectivity
4. Useful for topological sorting
5. Natural for problems requiring path finding
Disadvantages
1. May use significant stack space for deep graphs
2. Not optimal for finding shortest paths
3. Can be slower than BFS for certain problems
4. May revisit the same path in complex graphs
When to Use
Applications
Comparison with BFS
Key Takeaways
- Explores deeply first
- Uses stack or recursion
- Backtracking approach
- Useful for topological sorting
- Detects cycles in graphs
- Space-efficient with recursion
Implementation
function dfs(graph, start, visited = new Set()) {
visited.add(start);
console.log(start);
for (let neighbor of graph[start] || []) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited);
}
}
return visited;
}