Depth First Search (DFS)
Definition
DFS is a traversal algorithm that explores a path as deep as possible before backtracking. It dives into a “branch” of the graph all the way to the end, then steps back to try other paths.
How it Works
- Start at a node.
- Mark it as visited.
- Pick an adjacent unvisited neighbor and move to it.
- Repeat step 3 until you hit a dead end.
- Backtrack (return to the previous node) and check for other unvisited neighbors.
Real-World Analogy
Solving a Maze: You pick a path and keep walking until you hit a wall. Once you hit a wall, you retrace your steps back to the last intersection and try a different path.
Code Example
PythonJavaCC++
# Depth First Search (DFS)
def dfs(graph, node, visited):
if node not in visited:
print(node, end=" ")
visited.add(node)
# Visit neighbors
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
# Graph using adjacency list
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': [],
'F': []
}
print("DFS Traversal:")
dfs(graph, 'A', set())
import java.util.*;
public class DFSExample {
static void dfs(Map<String, List<String>> graph,
String node,
Set<String> visited) {
if (!visited.contains(node)) {
System.out.print(node + " ");
visited.add(node);
for (String neighbor : graph.get(node))
dfs(graph, neighbor, visited);
}
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B","C"));
graph.put("B", Arrays.asList("D","E"));
graph.put("C", Arrays.asList("F"));
graph.put("D", new ArrayList<>());
graph.put("E", new ArrayList<>());
graph.put("F", new ArrayList<>());
System.out.println("DFS Traversal:");
dfs(graph, "A", new HashSet<>());
}
}
#include <stdio.h>
#define N 6
void dfs(int graph[N][N], int node, int visited[]) {
printf("%d ", node);
visited[node] = 1;
for (int i = 0; i < N; i++) {
if (graph[node][i] && !visited[i])
dfs(graph, i, visited);
}
}
int main() {
int graph[N][N] = {
{0,1,1,0,0,0},
{0,0,0,1,1,0},
{0,0,0,0,0,1},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0}
};
int visited[N] = {0};
printf("DFS Traversal:\n");
dfs(graph, 0, visited);
return 0;
}
#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
void dfs(map<char, vector<char>>& graph,
char node,
set<char>& visited) {
if (visited.count(node) == 0) {
cout << node << " ";
visited.insert(node);
for (char neighbor : graph[node])
dfs(graph, neighbor, visited);
}
}
int main() {
map<char, vector<char>> graph;
graph['A'] = {'B','C'};
graph['B'] = {'D','E'};
graph['C'] = {'F'};
graph['D'] = {};
graph['E'] = {};
graph['F'] = {};
set<char> visited;
cout << "DFS Traversal:" << endl;
dfs(graph, 'A', visited);
return 0;
}
Complexity & Use Cases
- Time: O(V + E) – You visit every node and edge once.
- Space: O(V) – Stack space for recursion.
- Use Cases: Solving puzzles (mazes, Sudoku), detecting cycles in a graph, finding connected components.