Traversal is the process of visiting every node in a graph. Whether you're searching for a destination in GPS or checking connectivity, BFS (Layers) and DFS (Branches) are your primary tools.

Unvisited

Visiting

Visited

How BFS Works

STEP-BY-STEP

Working Queue (FIFO)0 elements

Empty structure... Click Play.

Visited Order

No nodes visited yet.

BFS uses a Queue to explore neighbors level-by-level. It's the standard for finding the shortest path on unweighted graphs.

Implementation Guide

Breadth-First Search

Pseudocode

1// BFS using an Adjacency List
2function bfs(graph, start) {
3  const queue = [start];
4  const visited = new Set([start]);
5  const result = [];
6 
7  while (queue.length > 0) {
8    const vertex = queue.shift();
9    result.push(vertex);
10 
11    graph[vertex].forEach(neighbor => {
12      if (!visited.has(neighbor)) {
13        visited.add(neighbor);
14        queue.push(neighbor);
15      }
16    });
17  }
18  return result;
19}

Depth-First Search (Recursive)

Pseudocode

1// DFS (Recursive)
2function dfs(graph, vertex, visited = new Set()) {
3  visited.add(vertex);
4  console.log(vertex);
5 
6  graph[vertex].forEach(neighbor => {
7    if (!visited.has(neighbor)) {
8      dfs(graph, neighbor, visited);
9    }
10  });
11}

Which one should I use?

BFS

Use BFS when...

You need the shortest path.
The destination is near the source.
You have plenty of memory for the queue.

DFS

Use DFS when...

You need to visit every node.
You want to save memory on wide graphs.
You are performing Topological Sorting.

Implementation Guide

Breadth-First Search

Pseudocode

1// BFS using an Adjacency List
2function bfs(graph, start) {
3  const queue = [start];
4  const visited = new Set([start]);
5  const result = [];
6 
7  while (queue.length > 0) {
8    const vertex = queue.shift();
9    result.push(vertex);
10 
11    graph[vertex].forEach(neighbor => {
12      if (!visited.has(neighbor)) {
13        visited.add(neighbor);
14        queue.push(neighbor);
15      }
16    });
17  }
18  return result;
19}

Depth-First Search (Recursive)

Pseudocode

1// DFS (Recursive)
2function dfs(graph, vertex, visited = new Set()) {
3  visited.add(vertex);
4  console.log(vertex);
5 
6  graph[vertex].forEach(neighbor => {
7    if (!visited.has(neighbor)) {
8      dfs(graph, neighbor, visited);
9    }
10  });
11}