Graph Traversal

Explore DFS and BFS algorithms for graph traversal

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

1

Initialize DFS

Start DFS traversal from node A

2

Visit Node A

Start exploring node A - mark as visiting

3

Mark A as Visited

Add A to visited set and process

4

Explore Neighbor B

Found unvisited neighbor B - recursively explore

5

Visit Node B

Start exploring node B - mark as visiting

6

Mark B as Visited

Add B to visited set and process

7

Explore Neighbor D

Found unvisited neighbor D - recursively explore

8

Visit Node D

Start exploring node D - mark as visiting

9

Mark D as Visited

Add D to visited set and process

10

Backtrack from D

Finished exploring D - return to previous call

11

Explore Neighbor E

Found unvisited neighbor E - recursively explore

12

Visit Node E

Start exploring node E - mark as visiting

13

Mark E as Visited

Add E to visited set and process

14

Explore Neighbor F

Found unvisited neighbor F - recursively explore

15

Visit Node F

Start exploring node F - mark as visiting

16

Mark F as Visited

Add F to visited set and process

17

Explore Neighbor C

Found unvisited neighbor C - recursively explore

18

Visit Node C

Start exploring node C - mark as visiting

19

Mark C as Visited

Add C to visited set and process

20

Backtrack from C

Finished exploring C - return to previous call

21

Backtrack from F

Finished exploring F - return to previous call

22

Backtrack from E

Finished exploring E - return to previous call

23

Backtrack from B

Finished exploring B - return to previous call

24

Backtrack from A

Finished exploring A - return to previous call

25

DFS Complete

All reachable nodes have been visited

Graph Structure

A
B
C
D
E
F

Depth-First Search (DFS)

Strategy: Go as deep as possible before backtracking
Data Structure: Recursion (implicit stack)
Use Cases: Topological sort, cycle detection, pathfinding
Unvisited
Current
Neighbor
Visited
Step 0 of 240%
0.25x4x