Depth-First Search (DFS) in TypeScript

Depth-First Search (DFS) is a fundamental algorithm in computer science used for traversing or searching tree or graph data structures. It explores as far as possible along each branch before backtracking. TypeScript, a superset of JavaScript, provides strong typing and object-oriented features that can be effectively used to implement DFS algorithms. In this blog, we will explore the fundamental concepts of DFS in TypeScript, how to use it, common practices, and best practices.

Table of Contents#

  1. Fundamental Concepts of DFS
  2. Implementing DFS in TypeScript
  3. Usage Methods
  4. Common Practices
  5. Best Practices
  6. Conclusion
  7. References

Fundamental Concepts of DFS#

What is DFS?#

DFS is a graph traversal algorithm that starts at a given vertex (or node) and explores as far as possible along each branch before backtracking. It uses a stack data structure (either explicitly or implicitly through recursion) to keep track of the nodes to visit.

How it Works#

  1. Start Node: Begin at a specified start node.
  2. Explore Neighbors: Visit an unvisited neighbor of the current node. Mark the neighbor as visited and make it the current node.
  3. Backtracking: If there are no unvisited neighbors, backtrack to the previous node and continue exploring its other unvisited neighbors.

Implementing DFS in TypeScript#

Recursive DFS#

// Define a graph using an adjacency list
type Graph = { [key: number]: number[] };
 
function recursiveDFS(graph: Graph, start: number, visited: Set<number> = new Set()): void {
    if (visited.has(start)) {
        return;
    }
    console.log(start);
    visited.add(start);
 
    const neighbors = graph[start];
    for (const neighbor of neighbors) {
        recursiveDFS(graph, neighbor, visited);
    }
}
 
// Example graph
const graph: Graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
};
 
recursiveDFS(graph, 0);

Iterative DFS#

function iterativeDFS(graph: Graph, start: number): void {
    const visited = new Set<number>();
    const stack: number[] = [start];
 
    while (stack.length > 0) {
        const current = stack.pop()!;
        if (visited.has(current)) {
            continue;
        }
        console.log(current);
        visited.add(current);
 
        const neighbors = graph[current];
        for (let i = neighbors.length - 1; i >= 0; i--) {
            if (!visited.has(neighbors[i])) {
                stack.push(neighbors[i]);
            }
        }
    }
}
 
iterativeDFS(graph, 0);

Usage Methods#

Searching in Graphs#

DFS can be used to find a specific node in a graph. You can modify the DFS functions to return the node when it is found.

function searchDFS(graph: Graph, start: number, target: number): boolean {
    const visited = new Set<number>();
    const stack: number[] = [start];
 
    while (stack.length > 0) {
        const current = stack.pop()!;
        if (visited.has(current)) {
            continue;
        }
        if (current === target) {
            return true;
        }
        visited.add(current);
 
        const neighbors = graph[current];
        for (let i = neighbors.length - 1; i >= 0; i--) {
            if (!visited.has(neighbors[i])) {
                stack.push(neighbors[i]);
            }
        }
    }
    return false;
}
 
const found = searchDFS(graph, 0, 3);
console.log(found);

Detecting Cycles in Graphs#

DFS can also be used to detect cycles in a graph. By keeping track of the nodes in the current path, if we encounter a node that is already in the path, then there is a cycle.

Common Practices#

Using Sets for Visited Nodes#

In both recursive and iterative DFS, using a Set to keep track of visited nodes is a common practice. It provides efficient lookups (O(1) on average) to check if a node has been visited.

Handling Disconnected Graphs#

If the graph is disconnected, you need to run DFS from each unvisited node to ensure that all nodes are traversed.

function dfsDisconnectedGraph(graph: Graph): void {
    const visited = new Set<number>();
    for (const node in graph) {
        const numNode = parseInt(node);
        if (!visited.has(numNode)) {
            recursiveDFS(graph, numNode, visited);
        }
    }
}
 
dfsDisconnectedGraph(graph);

Best Practices#

Error Handling#

When working with graphs, it's important to handle cases where the input graph is not valid, such as having nodes with undefined neighbors.

function isValidGraph(graph: Graph): boolean {
    for (const node in graph) {
        const neighbors = graph[parseInt(node)];
        for (const neighbor of neighbors) {
            if (!graph.hasOwnProperty(neighbor)) {
                return false;
            }
        }
    }
    return true;
}
 
if (isValidGraph(graph)) {
    recursiveDFS(graph, 0);
} else {
    console.log('Invalid graph');
}

Code Readability#

Use descriptive variable names and add comments to your code to make it more understandable. Also, modularize your code by separating different functions for different tasks, such as the main DFS function, the search function, etc.

Conclusion#

DFS is a powerful algorithm for traversing and searching graphs. TypeScript provides a great environment to implement DFS algorithms with its strong typing and object-oriented features. By understanding the fundamental concepts, usage methods, common practices, and best practices, you can efficiently use DFS in your TypeScript projects. Whether you are searching for a specific node, detecting cycles, or just exploring a graph, DFS is a valuable tool in your programming arsenal.

References#

  1. Cormen, Thomas H., et al. Introduction to Algorithms. MIT press, 2009.
  2. MDN Web Docs - JavaScript Sets: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
  3. Wikipedia-Depth-First Search: https://en.wikipedia.org/wiki/Depth - first_search
2025-10