Master DFS - Depth-First Search

function dfsRecursive(graph, node, visited = new Set()) {
    /**
     * Recursive Depth-First Search
     * Time: O(V + E) - visit each vertex and edge once
     * Space: O(V) - recursion stack + visited set
     */
    visited.add(node);
    console.log('Visiting node:', node);

    // Explore all neighbors
    for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
            dfsRecursive(graph, neighbor, visited);
        }
    }

    return visited;
}

function dfsIterative(graph, start) {
    /**
     * Iterative DFS using explicit stack
     */
    const visited = new Set();
    const stack = [start];

    while (stack.length > 0) {
        const node = stack.pop(); // LIFO - depth-first

        if (!visited.has(node)) {
            visited.add(node);
            console.log('Visiting node:', node);

            // Add neighbors to stack (reverse for same order as recursive)
            const neighbors = [...graph[node]].reverse();
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }

    return visited;
}

// Usage example
const graph = {
    0: [1, 2],
    1: [3, 4],
    2: [5],
    3: [],
    4: [],
    5: []
};

console.log("Recursive DFS:");
dfsRecursive(graph, 0); // Output: 0 -> 1 -> 3 -> 4 -> 2 -> 5

console.log("\nIterative DFS:");
dfsIterative(graph, 0); // Same output

package main

import "fmt"

// DFSRecursive performs recursive depth-first search
// Time: O(V + E) - visit each vertex and edge once
// Space: O(V) - recursion stack + visited map
func DFSRecursive(graph map[int][]int, node int, visited map[int]bool) {
    visited[node] = true
    fmt.Printf("Visiting node: %d\n", node)

    // Explore all neighbors
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            DFSRecursive(graph, neighbor, visited)
        }
    }
}

// DFSIterative performs iterative DFS using explicit stack
func DFSIterative(graph map[int][]int, start int) map[int]bool {
    visited := make(map[int]bool)
    stack := []int{start}

    for len(stack) > 0 {
        // Pop from stack (LIFO)
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if !visited[node] {
            visited[node] = true
            fmt.Printf("Visiting node: %d\n", node)

            // Add neighbors to stack (reverse order)
            neighbors := graph[node]
            for i := len(neighbors) - 1; i >= 0; i-- {
                if !visited[neighbors[i]] {
                    stack = append(stack, neighbors[i])
                }
            }
        }
    }

    return visited
}

func main() {
    // Usage example
    graph := map[int][]int{
        0: {1, 2},
        1: {3, 4},
        2: {5},
        3: {},
        4: {},
        5: {},
    }

    fmt.Println("Recursive DFS:")
    visited := make(map[int]bool)
    DFSRecursive(graph, 0, visited)

    fmt.Println("\nIterative DFS:")
    DFSIterative(graph, 0)
}

import java.util.*;

public class DFS {
    /**
     * Recursive Depth-First Search
     * Time: O(V + E) - visit each vertex and edge once
     * Space: O(V) - recursion stack + visited set
     */
    public static void dfsRecursive(Map<Integer, List<Integer>> graph,
                                     int node, Set<Integer> visited) {
        visited.add(node);
        System.out.println("Visiting node: " + node);

        // Explore all neighbors
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(graph, neighbor, visited);
            }
        }
    }

    /**
     * Iterative DFS using explicit stack
     */
    public static Set<Integer> dfsIterative(Map<Integer, List<Integer>> graph,
                                             int start) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop(); // LIFO - depth-first

            if (!visited.contains(node)) {
                visited.add(node);
                System.out.println("Visiting node: " + node);

                // Add neighbors to stack (reverse for same order)
                List<Integer> neighbors = new ArrayList<>(graph.get(node));
                Collections.reverse(neighbors);
                for (int neighbor : neighbors) {
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }

        return visited;
    }

    public static void main(String[] args) {
        // Usage example
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(3, 4));
        graph.put(2, Arrays.asList(5));
        graph.put(3, new ArrayList<>());
        graph.put(4, new ArrayList<>());
        graph.put(5, new ArrayList<>());

        System.out.println("Recursive DFS:");
        dfsRecursive(graph, 0, new HashSet<>());

        System.out.println("\nIterative DFS:");
        dfsIterative(graph, 0);
    }
}

#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>
#include <algorithm>
using namespace std;

/**
 * Recursive Depth-First Search
 * Time: O(V + E) - visit each vertex and edge once
 * Space: O(V) - recursion stack + visited set
 */
void dfsRecursive(const vector<vector<int>>& graph, int node,
                  unordered_set<int>& visited) {
    visited.insert(node);
    cout << "Visiting node: " << node << endl;

    // Explore all neighbors
    for (int neighbor : graph[node]) {
        if (visited.find(neighbor) == visited.end()) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

/**
 * Iterative DFS using explicit stack
 */
unordered_set<int> dfsIterative(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;
    stack<int> stk;
    stk.push(start);

    while (!stk.empty()) {
        int node = stk.top();
        stk.pop(); // LIFO - depth-first

        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            cout << "Visiting node: " << node << endl;

            // Add neighbors to stack (reverse order)
            auto neighbors = graph[node];
            reverse(neighbors.begin(), neighbors.end());
            for (int neighbor : neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    stk.push(neighbor);
                }
            }
        }
    }

    return visited;
}

int main() {
    // Usage example (adjacency list)
    vector<vector<int>> graph = {
        {1, 2},    // node 0
        {3, 4},    // node 1
        {5},       // node 2
        {},        // node 3
        {},        // node 4
        {}         // node 5
    };

    cout << "Recursive DFS:" << endl;
    unordered_set<int> visited;
    dfsRecursive(graph, 0, visited);

    cout << "\nIterative DFS:" << endl;
    dfsIterative(graph, 0);

    return 0;
}