Graph Traversals: Depth-First Search (DFS) vs Breadth-First Search (BFS)
5.0|1 ratingLog in to rate
Learn the fundamentals of graph traversals, and when to use DFS versus BFS in interview problems.
#dsa#graphs#algorithms#traversals
Breadth-First Search (BFS)
BFS explores nodes layer-by-layer, starting from a root source. It utilizes a Queue (FIFO) to record adjacent nodes and guarantees finding the shortest path in unweighted graphs.
BFS JavaScript Implementation:
javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bfs(graph, start) {
const queue = [start];
const visited = new Set([start]);
while (queue.length > 0) {
const node = queue.shift();
console.log(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}Depth-First Search (DFS)
DFS probes paths as deeply as possible before backtracking. It uses recursion or a Stack (LIFO) and is well-suited for connectivity testing, cycle detection, and topological sorting.
DFS Recursive Implementation
javascript
1
2
3
4
5
6
7
8
9
10
function dfs(graph, node, visited = new Set()) {
visited.add(node);
console.log(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}Discussion
Loading discussion...