Algorithm Code
Time: O(V + E) | Space: O(V)
1function dfs(graph, start, visited = new Set()) {
2 // Mark current node as visited
3 visited.add(start);
4 console.log(start); // Process node
5
6 // Visit all unvisited neighbors
7 for (let neighbor of graph[start]) {
8 if (!visited.has(neighbor)) {
9 dfs(graph, neighbor, visited);
10 }
11 }
12
13 return visited;
14}Algorithm Steps
Step 1 of 25
Initialize DFS
Start DFS traversal from node A
Visit Node A
Start exploring node A - mark as visiting
Mark A as Visited
Add A to visited set and process
Explore Neighbor B
Found unvisited neighbor B - recursively explore
Visit Node B
Start exploring node B - mark as visiting
Mark B as Visited
Add B to visited set and process
Explore Neighbor D
Found unvisited neighbor D - recursively explore
Visit Node D
Start exploring node D - mark as visiting
Mark D as Visited
Add D to visited set and process
Backtrack from D
Finished exploring D - return to previous call
Explore Neighbor E
Found unvisited neighbor E - recursively explore
Visit Node E
Start exploring node E - mark as visiting
Mark E as Visited
Add E to visited set and process
Explore Neighbor F
Found unvisited neighbor F - recursively explore
Visit Node F
Start exploring node F - mark as visiting
Mark F as Visited
Add F to visited set and process
Explore Neighbor C
Found unvisited neighbor C - recursively explore
Visit Node C
Start exploring node C - mark as visiting
Mark C as Visited
Add C to visited set and process
Backtrack from C
Finished exploring C - return to previous call
Backtrack from F
Finished exploring F - return to previous call
Backtrack from E
Finished exploring E - return to previous call
Backtrack from B
Finished exploring B - return to previous call
Backtrack from A
Finished exploring A - return to previous call
DFS Complete
All reachable nodes have been visited