Depth first search

Practical Applications of DFS

Path Finding: DFS can be used to find a path between two nodes in a graph.

Topological Sorting: In directed acyclic graphs (DAGs), DFS can help in ordering vertices such that every directed edge is from an earlier vertex to a later vertex.

Cycle Detection: DFS can detect cycles in a graph, which is useful for applications that need to analyze dependencies or scheduling.

Solving Puzzles: DFS is suitable for games or puzzle problems where a complete search is needed to find a solution, like in Sudoku or maze problems.

Ways to Implement DFS

DFS can be implemented both recursively and iteratively:

Recursive Approach: This is the most natural and widely used implementation of DFS. It leverages the call stack of the programming language being used, which handles the backtracking automatically. Each recursive call goes deeper into a branch and backtracks once it hits a dead end or all nodes are visited

Iterative Approach: An iterative version of DFS can be implemented using an explicit stack. This approach manually simulates the call stack that would be used in a recursive implementation. The process involves pushing a node onto the stack, processing it, and then pushing its children onto the stack. It mimics the recursive depth-first exploration.

Adjacency Matrix

function dfsMatrix(graph, start) {
    let stack = [start]; 
    let visited = new Set([start]); 

    while (stack.length > 0) {
        let node = stack.pop();

        // Explore all neighbors of the current node
        for (let i = graph[node].length - 1; i >= 0; i--) {
            let isNeighbor = graph[node][i];

            // If there is an edge and the node was not visited
            if (isNeighbor && !visited.has(i)) {
                visited.add(i);
                stack.push(i);
            }
        }
    }
}

// Example adjacency matrix
const graph = [
    [0, 1, 0, 0, 1], // Edges for 0
    [1, 0, 1, 1, 0], // Edges for 1
    [0, 1, 0, 1, 0], // Edges for 2
    [0, 1, 1, 0, 1], // Edges for 3
    [1, 0, 0, 1, 0], // Edges for 4
];

dfsMatrix(graph, 0); // Start DFS at node 0

Adjacency List

function dfsList(graph, start) {
    let stack = [start];
    let visited = new Set([start]);

    while (stack.length > 0) {
        let node = stack.pop();

        for (let i = graph[node].length - 1; i >= 0; i--) {
            let neighbor = graph[node][i];
            
            if (!visited.has(neighbor)) {
                visited.add(neighbor); 
                stack.push(neighbor);
            }
        }
    }
}

// Example adjacency list fd vs
const graph = [
    [1, 4],    // Neighbors of node 0
    [0, 2, 3], // Neighbors of node 1
    [1, 3],    // Neighbors of node 2
    [1, 2, 4], // Neighbors of node 3
    [0, 3]     // Neighbors of node 4
];

dfsList(graph, 0); // Start DFS at node 0

CALL_STACK

NODE_A

A

B

C

D

E

F

G

H

I