Graph DFS and BFS

// Adjacency List (most common in interviews)
Map<Integer, List<Integer>> adj = new HashMap<>();
adj.put(0, List.of(1, 2));
adj.put(1, List.of(0, 3));
adj.put(2, List.of(0));
adj.put(3, List.of(1));

// For grids, the graph is implicit — neighbors are up/down/left/right
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

// Recursive DFS
Set<Integer> visited = new HashSet<>();

void dfs(Map<Integer, List<Integer>> adj, int node) {
    visited.add(node);
    System.out.println("Visiting: " + node);
    for (int neighbor : adj.getOrDefault(node, List.of())) {
        if (!visited.contains(neighbor)) dfs(adj, neighbor);
    }
}

// Iterative DFS (using Stack)
void dfsIterative(Map<Integer, List<Integer>> adj, int start) {
    Set<Integer> visited = new HashSet<>();
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited.contains(node)) continue;
        visited.add(node);
        System.out.println("Visiting: " + node);
        for (int neighbor : adj.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) stack.push(neighbor);
        }
    }
}

// BFS finds shortest path (unweighted graph)
void bfs(Map<Integer, List<Integer>> adj, int start) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println("Visiting: " + node);
        for (int neighbor : adj.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

public int numIslands(char[][] grid) {
    int count = 0;
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[0].length; c++)
            if (grid[r][c] == '1') { dfs(grid, r, c); count++; }
    return count;
}
void dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
            || grid[r][c] != '1') return;
    grid[r][c] = '0'; // mark visited (in-place)
    dfs(grid, r+1, c); dfs(grid, r-1, c);
    dfs(grid, r, c+1); dfs(grid, r, c-1);
}

public int shortestPath(Map<Integer, List<Integer>> adj, int src, int dst) {
    Set<Integer> visited = new HashSet<>();
    Queue<int[]> queue = new LinkedList<>(); // [node, distance]
    queue.offer(new int[]{src, 0});
    visited.add(src);
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int node = curr[0], dist = curr[1];
        if (node == dst) return dist;
        for (int neighbor : adj.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(new int[]{neighbor, dist + 1});
            }
        }
    }
    return -1; // unreachable
}