Master the exploration of graphs using BFS and DFS — essential for problems involving connected components, cycles, shortest paths, and maze-like challenges.
To explore all nodes in a component or check if nodes are connected
To detect cycles in directed or undirected graphs
To compute shortest path in unweighted graphs (BFS) or weighted graphs (Dijkstra)
When navigating through 2D/3D grids with obstacles or directions
Use BFS to find the shortest path in unweighted graphs
DFS is great for deep search, cycle detection, and topological sort
Always maintain a visited set/map to prevent infinite loops
Adjacency list is space-efficient for sparse graphs, matrix for dense graphs
Recursive depth-first traversal using visited set
function dfs(graph: Map<number, number[]>, node: number, visited: Set<number>) {
if (visited.has(node)) return;
visited.add(node);
console.log(node); // or push to result
for (const neighbor of graph.get(node) || []) {
dfs(graph, neighbor, visited);
}
}
// Usage:
const graph = new Map([[0, [1, 2]], [1, [0, 3]], [2, [0]], [3, [1]]]);
dfs(graph, 0, new Set());Breadth-first traversal using queue and visited set
function bfs(graph: Map<number, number[]>, start: number) {
const visited = new Set<number>();
const queue: number[] = [start];
visited.add(start);
while (queue.length > 0) {
const node = queue.shift()!;
console.log(node); // or push to result
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}DFS on a grid for maze problems
function dfsGrid(grid: number[][], i: number, j: number, visited: boolean[][]) {
const rows = grid.length, cols = grid[0].length;
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === 0 || visited[i][j]) return;
visited[i][j] = true;
const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
for (const [dx, dy] of dirs) {
dfsGrid(grid, i + dx, j + dy, visited);
}
}Clone Graph