Depth-First Search (DFS) is one of the most fundamental algorithms used in computer science for exploring graphs and trees. It works by starting at a source node and exploring as far as possible along each branch before backtracking. This makes it ideal for solving problems where you need to traverse an entire structure, such as maze solving, finding paths, detecting cycles, and analyzing networks. For beginners learning TypeScript, DFS is an excellent algorithm to understand recursion, stacks, and how to efficiently explore complex structures.
with hands-on learning.
get the skills and confidence to land your next move.
DFS is widely used in applications such as social network analysis, puzzle solving, and route planning. Unlike Breadth-First Search (BFS), which explores nodes level by level, DFS dives deep into one path first. This characteristic makes it particularly useful when searching for solutions that may be located far from the starting point. Learning DFS in TypeScript not only helps beginners practice loops, recursion, and data structures, but also gives a solid foundation for tackling more advanced algorithms.
Program 1: Recursive DFS for Graph Traversal
This program demonstrates the classic recursive approach to DFS, exploring all nodes of a graph from a given starting point.
class Graph {
adjacencyList: Map<number, number[]>;
constructor() {
this.adjacencyList = new Map();
}
addEdge(u: number, v: number) {
if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
this.adjacencyList.get(u)!.push(v);
this.adjacencyList.get(v)!.push(u); // For undirected graph
}
dfs(start: number, visited: Set<number> = new Set()) {
visited.add(start);
console.log(start);
for (let neighbor of this.adjacencyList.get(start) || []) {
if (!visited.has(neighbor)) {
this.dfs(neighbor, visited);
}
}
}
}
let graph = new Graph();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 5);
console.log("DFS Recursive Traversal:");
graph.dfs(1);In this program, the DFS function uses recursion to visit each node. The visited set ensures that nodes are not revisited. Beginners can easily follow how DFS dives deep into one branch before moving to another.
Program 2: Iterative DFS Using a Stack
DFS can also be implemented iteratively using a stack. This is especially useful when recursion depth might become too large.
function dfsIterative(graph: Map<number, number[]>, start: number) {
let visited = new Set<number>();
let stack: number[] = [start];
while (stack.length > 0) {
let node = stack.pop()!;
if (!visited.has(node)) {
console.log(node);
visited.add(node);
for (let neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) stack.push(neighbor);
}
}
}
}
let graphMap: Map<number, number[]> = new Map([
[1, [2, 3]],
[2, [1, 4]],
[3, [1, 5]],
[4, [2]],
[5, [3]]
]);
console.log("DFS Iterative Traversal:");
dfsIterative(graphMap, 1);The iterative version achieves the same traversal as recursion but avoids stack overflow issues for very deep graphs. Beginners can see how a stack explicitly keeps track of nodes to visit next.
Program 3: DFS for Detecting Cycles in a Graph
DFS can also help detect cycles in a graph by keeping track of visited nodes and parent relationships.
function hasCycle(graph: Map<number, number[]>, node: number, visited: Set<number>, parent: number | null): boolean {
visited.add(node);
for (let neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
if (hasCycle(graph, neighbor, visited, node)) return true;
} else if (neighbor !== parent) {
return true;
}
}
return false;
}
let graphMap: Map<number, number[]> = new Map([
[1, [2, 3]],
[2, [1, 4]],
[3, [1, 5]],
[4, [2]],
[5, [3]]
]);
let visitedSet = new Set<number>();
console.log("Graph has cycle:", hasCycle(graphMap, 1, visitedSet, null));This demonstrates how DFS can be used for practical applications like detecting loops in networks or dependencies. Beginners can learn to use recursion for problem-solving beyond simple traversal.
Program 4: DFS for Weighted Graphs (Simple Example)
DFS can also traverse weighted graphs if we only need to explore nodes without considering weights for path cost.
let weightedGraph: Map<number, [number, number][]> = new Map([
[1, [[2, 5], [3, 3]]],
[2, [[1, 5], [4, 2]]],
[3, [[1, 3], [5, 7]]],
[4, [[2, 2]]],
[5, [[3, 7]]]
]);
function dfsWeighted(graph: Map<number, [number, number][]>, start: number, visited: Set<number> = new Set()) {
visited.add(start);
console.log(start);
for (let [neighbor, weight] of graph.get(start) || []) {
if (!visited.has(neighbor)) dfsWeighted(graph, neighbor, visited);
}
}
console.log("DFS Weighted Graph Traversal:");
dfsWeighted(weightedGraph, 1);Even with weights, DFS can explore all nodes. Beginners learn that traversal logic is similar, regardless of edge weights, unless path cost is relevant.
Program 5: DFS on a 2D Grid (Maze Example)
DFS can be applied to grids for tasks like maze solving or pathfinding.
let maze: number[][] = [
[0, 1, 0, 0],
[0, 0, 0, 1],
[1, 0, 1, 0],
[0, 0, 0, 0]
];
function dfsGrid(grid: number[][], x: number, y: number, visited: boolean[][]) {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === 1 || visited[x][y]) return;
visited[x][y] = true;
console.log(`Visited cell: (${x}, ${y})`);
dfsGrid(grid, x + 1, y, visited);
dfsGrid(grid, x - 1, y, visited);
dfsGrid(grid, x, y + 1, visited);
dfsGrid(grid, x, y - 1, visited);
}
let visitedGrid: boolean[][] = Array.from({ length: maze.length }, () => Array(maze[0].length).fill(false));
console.log("DFS Grid Traversal:");
dfsGrid(maze, 0, 0, visitedGrid);This example helps beginners see DFS applied beyond graphs, showing how to explore grids for solving practical problems like finding paths.
Frequently Asked Questions (FAQ)
DFS often raises questions for beginners:
Q1. Can DFS work on both directed and undirected graphs?
Yes, DFS can traverse both types; logic may slightly differ when detecting cycles.
Q2. How is DFS different from BFS?
DFS dives deep along one path first, while BFS explores level by level.
Q3. Can DFS handle weighted graphs?
Yes, DFS can traverse weighted graphs, but it does not automatically find shortest paths.
Q4. Is DFS safe for large graphs?
Recursive DFS may cause stack overflow on very deep graphs; iterative DFS with a stack can prevent this.
Q5. Can DFS solve maze or grid problems?
Yes, DFS can explore all paths in a maze, making it useful for pathfinding and puzzle-solving.
Conclusion
Depth-First Search is a versatile and essential algorithm for exploring graphs, trees, and grids. In this article, we explored TypeScript implementations of DFS using recursion, iteration, cycle detection, weighted graphs, and grid traversal. Beginners can practice these examples to understand how DFS systematically explores nodes, how recursion and stacks work, and how DFS can be applied in real-world applications like maze solving, network analysis, and graph processing.
Mastering DFS in TypeScript not only strengthens understanding of traversal algorithms but also prepares beginners for more complex concepts like pathfinding, graph optimization, and advanced search techniques.
