Depth-First Search (DFS) in TypeScript

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

• ←Previous
• Next→