Graphs

import java.util.*;
public class AdjacencyList {
    // Graph representation using adjacency list
    private Map<Integer, List<Integer>> graph;
    public AdjacencyList() {
        graph = new HashMap<>();
    }
    // Add a node to the graph
    public void addNode(int node) {
        graph.putIfAbsent(node, new ArrayList<>());
    }
    // Add an edge (for undirected graph, add both directions)
    public void addEdge(int source, int destination) {
        // Make sure both nodes exist
        addNode(source);
        addNode(destination);
        // Add edge from source to destination
        graph.get(source).add(destination);
        // For undirected graph, add reverse edge too
        graph.get(destination).add(source);
    }
    // Add directed edge (only one direction)
    public void addDirectedEdge(int source, int destination) {
        addNode(source);
        addNode(destination);
        graph.get(source).add(destination);
    }
    // Get neighbors of a node
    public List<Integer> getNeighbors(int node) {
        return graph.getOrDefault(node, new ArrayList<>());
    }
    // Print the graph
    public void printGraph() {
        for (int node : graph.keySet()) {
            System.out.print(node + " -> ");
            for (int neighbor : graph.get(node)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        AdjacencyList graph = new AdjacencyList();
        // Build a simple graph
        // 0 -- 1
        // |    |
        // 2 -- 3
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        System.out.println("Graph representation:");
        graph.printGraph();
        // Output:
        // 0 -> 1 2
        // 1 -> 0 3
        // 2 -> 0 3
        // 3 -> 1 2
    }
}

public class AdjacencyMatrix {
    private int[][] matrix;
    private int numNodes;
    // Create graph with n nodes
    public AdjacencyMatrix(int n) {
        this.numNodes = n;
        this.matrix = new int[n][n];
    }
    // Add edge between two nodes
    public void addEdge(int source, int destination) {
        // For undirected graph, set both directions
        matrix[source][destination] = 1;
        matrix[destination][source] = 1;
    }
    // Add directed edge (only one direction)
    public void addDirectedEdge(int source, int destination) {
        matrix[source][destination] = 1;
    }
    // Add weighted edge
    public void addWeightedEdge(int source, int destination, int weight) {
        matrix[source][destination] = weight;
        matrix[destination][source] = weight;
    }
    // Check if edge exists
    public boolean hasEdge(int source, int destination) {
        return matrix[source][destination] != 0;
    }
    // Remove edge
    public void removeEdge(int source, int destination) {
        matrix[source][destination] = 0;
        matrix[destination][source] = 0;
    }
    // Print the matrix
    public void printMatrix() {
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        // Create graph with 4 nodes (0, 1, 2, 3)
        AdjacencyMatrix graph = new AdjacencyMatrix(4);
        // Build the same graph as before
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.printMatrix();
        // Output:
        // 0 1 1 0
        // 1 0 0 1
        // 1 0 0 1
        // 0 1 1 0
        // Check if edge exists
        System.out.println("\nEdge 0-1 exists? " + graph.hasEdge(0, 1));  // true
        System.out.println("Edge 0-3 exists? " + graph.hasEdge(0, 3));  // false
    }
}

import java.util.*;
public class BFS {
    // Breadth-First Search - explore level by level!
    public static void bfs(Map<Integer, List<Integer>> graph, int start) {
        // Queue to keep track of nodes to visit
        Queue<Integer> queue = new LinkedList<>();
        // Set to track visited nodes (avoid visiting same node twice)
        Set<Integer> visited = new HashSet<>();
        // Start from the starting node
        queue.offer(start);
        visited.add(start);
        System.out.println("BFS Traversal:");
        while (!queue.isEmpty()) {
            // Get the next node to visit
            int current = queue.poll();
            System.out.print(current + " ");
            // Visit all neighbors
            for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        System.out.println();
    }
    // BFS to find shortest path
    public static List<Integer> bfsShortestPath(Map<Integer, List<Integer>> graph,
                                                 int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        Map<Integer, Integer> parent = new HashMap<>();
        queue.offer(start);
        visited.add(start);
        parent.put(start, null);
        while (!queue.isEmpty()) {
            int current = queue.poll();
            // Found the destination!
            if (current == end) {
                // Reconstruct path
                List<Integer> path = new ArrayList<>();
                Integer node = end;
                while (node != null) {
                    path.add(0, node);  // Add to beginning
                    node = parent.get(node);
                }
                return path;
            }
            // Explore neighbors
            for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                    parent.put(neighbor, current);
                }
            }
        }
        return new ArrayList<>();  // No path found
    }
    public static void main(String[] args) {
        // Build graph: 0 -- 1 -- 3
        //              |    |
        //              2 ---+
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 2, 3));
        graph.put(2, Arrays.asList(0, 1));
        graph.put(3, Arrays.asList(1));
        bfs(graph, 0);  // Output: 0 1 2 3
        // Find shortest path from 0 to 3
        List<Integer> path = bfsShortestPath(graph, 0, 3);
        System.out.println("Shortest path from 0 to 3: " + path);
        // Output: [0, 1, 3]
    }
}

import java.util.*;
public class DFS {
    // Depth-First Search (Recursive) - go deep!
    public static void dfsRecursive(Map<Integer, List<Integer>> graph,
                                     int node, Set<Integer> visited) {
        // Mark current node as visited
        visited.add(node);
        System.out.print(node + " ");
        // Visit all unvisited neighbors
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(graph, neighbor, visited);
            }
        }
    }
    // Depth-First Search (Iterative using Stack)
    public static void dfsIterative(Map<Integer, List<Integer>> graph, int start) {
        Stack<Integer> stack = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        stack.push(start);
        System.out.println("DFS Traversal (Iterative):");
        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (visited.contains(current)) {
                continue;
            }
            visited.add(current);
            System.out.print(current + " ");
            // Add neighbors to stack (add in reverse order for same result as recursive)
            List<Integer> neighbors = graph.getOrDefault(current, new ArrayList<>());
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                if (!visited.contains(neighbors.get(i))) {
                    stack.push(neighbors.get(i));
                }
            }
        }
        System.out.println();
    }
    // DFS to find all paths from start to end
    public static void findAllPaths(Map<Integer, List<Integer>> graph,
                                     int current, int end,
                                     List<Integer> path,
                                     List<List<Integer>> allPaths) {
        // Add current node to path
        path.add(current);
        // If we reached the end, save this path
        if (current == end) {
            allPaths.add(new ArrayList<>(path));
        } else {
            // Explore all neighbors
            for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
                // Only visit if not already in current path (avoid cycles)
                if (!path.contains(neighbor)) {
                    findAllPaths(graph, neighbor, end, path, allPaths);
                }
            }
        }
        // Backtrack: remove current node from path
        path.remove(path.size() - 1);
    }
    public static void main(String[] args) {
        // Build graph: 0 -- 1 -- 3
        //              |    |
        //              2 ---+
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 2, 3));
        graph.put(2, Arrays.asList(0, 1));
        graph.put(3, Arrays.asList(1));
        // Recursive DFS
        System.out.println("DFS Traversal (Recursive):");
        Set<Integer> visited = new HashSet<>();
        dfsRecursive(graph, 0, visited);
        System.out.println();
        // Iterative DFS
        dfsIterative(graph, 0);
        // Find all paths from 0 to 3
        List<List<Integer>> allPaths = new ArrayList<>();
        findAllPaths(graph, 0, 3, new ArrayList<>(), allPaths);
        System.out.println("\nAll paths from 0 to 3:");
        for (List<Integer> path : allPaths) {
            System.out.println(path);
        }
        // Output: [0, 1, 3] and [0, 2, 1, 3]
    }
}

import java.util.*;
public class FindPath {
    // Check if path exists between source and destination
    public static boolean validPath(int n, int[][] edges, int source, int destination) {
        // Edge case: source and destination are the same
        if (source == destination) {
            return true;
        }
        // Build adjacency list
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        // Add all edges (undirected graph)
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        // BFS to find path
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(source);
        visited.add(source);
        while (!queue.isEmpty()) {
            int current = queue.poll();
            // Check if we reached destination
            if (current == destination) {
                return true;
            }
            // Explore neighbors
            for (int neighbor : graph.get(current)) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        return false;  // No path found
    }
    public static void main(String[] args) {
        // Graph with 6 nodes and edges
        int n = 6;
        int[][] edges = {{0,1}, {0,2}, {3,5}, {5,4}, {4,3}};
        System.out.println("Path 0 to 2: " + validPath(n, edges, 0, 2));  // true
        System.out.println("Path 0 to 5: " + validPath(n, edges, 0, 5));  // false
        // Graph:
        // 0 -- 1    3 -- 5
        // |         |    |
        // 2         +----4
    }
}

public class NumberOfIslands {
    // Count number of islands in a 2D grid
    // '1' represents land, '0' represents water
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        int islandCount = 0;
        // Check each cell
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // Found land! Start exploring the island
                if (grid[i][j] == '1') {
                    islandCount++;
                    exploreIsland(grid, i, j);
                }
            }
        }
        return islandCount;
    }
    // DFS to explore and mark all connected land
    private static void exploreIsland(char[][] grid, int row, int col) {
        // Check boundaries and if it's water or already visited
        if (row < 0 || row >= grid.length ||
            col < 0 || col >= grid[0].length ||
            grid[row][col] == '0') {
            return;
        }
        // Mark as visited by changing '1' to '0'
        grid[row][col] = '0';
        // Explore all 4 directions (up, down, left, right)
        exploreIsland(grid, row - 1, col);  // up
        exploreIsland(grid, row + 1, col);  // down
        exploreIsland(grid, row, col - 1);  // left
        exploreIsland(grid, row, col + 1);  // right
    }
    public static void main(String[] args) {
        char[][] grid1 = {
            {'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}
        };
        System.out.println("Number of islands: " + numIslands(grid1));  // 3
        // Grid visualization:
        // X X . . .
        // X X . . .
        // . . X . .
        // . . . X X
        // 3 separate islands!
        char[][] grid2 = {
            {'1', '1', '1', '1', '0'},
            {'1', '1', '0', '1', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '0', '0', '0'}
        };
        System.out.println("Number of islands: " + numIslands(grid2));  // 1
    }
}

import java.util.*;
// Node definition
class Node {
    public int val;
    public List<Node> neighbors;
    public Node(int val) {
        this.val = val;
        this.neighbors = new ArrayList<>();
    }
    public Node(int val, List<Node> neighbors) {
        this.val = val;
        this.neighbors = neighbors;
    }
}
public class CloneGraph {
    // Clone a graph using DFS
    public static Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        // Map to store original node -> cloned node
        Map<Node, Node> visited = new HashMap<>();
        return cloneDFS(node, visited);
    }
    private static Node cloneDFS(Node node, Map<Node, Node> visited) {
        // If already cloned, return the clone
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        // Create a clone of current node
        Node clone = new Node(node.val);
        visited.put(node, clone);
        // Clone all neighbors recursively
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneDFS(neighbor, visited));
        }
        return clone;
    }
    // Alternative: Clone using BFS
    public static Node cloneGraphBFS(Node node) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> visited = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        // Clone the starting node
        Node clone = new Node(node.val);
        visited.put(node, clone);
        queue.offer(node);
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            // Clone all neighbors
            for (Node neighbor : current.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    // Clone neighbor if not yet cloned
                    visited.put(neighbor, new Node(neighbor.val));
                    queue.offer(neighbor);
                }
                // Add the cloned neighbor to current clone's neighbors
                visited.get(current).neighbors.add(visited.get(neighbor));
            }
        }
        return clone;
    }
    public static void main(String[] args) {
        // Create a simple graph: 1 -- 2
        //                        |    |
        //                        4 -- 3
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.neighbors.add(node2);
        node1.neighbors.add(node4);
        node2.neighbors.add(node1);
        node2.neighbors.add(node3);
        node3.neighbors.add(node2);
        node3.neighbors.add(node4);
        node4.neighbors.add(node1);
        node4.neighbors.add(node3);
        // Clone the graph
        Node cloned = cloneGraph(node1);
        System.out.println("Original node value: " + node1.val);
        System.out.println("Cloned node value: " + cloned.val);
        System.out.println("Are they the same object? " + (node1 == cloned));  // false
        System.out.println("Do they have same neighbors? " +
                          (node1.neighbors.size() == cloned.neighbors.size()));  // true
    }
}

import java.util.*;
public class AllPaths {
    // Find all paths from source to target in a directed acyclic graph
    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        // Start DFS from node 0
        path.add(0);
        dfs(graph, 0, graph.length - 1, path, result);
        return result;
    }
    private static void dfs(int[][] graph, int current, int target,
                            List<Integer> path, List<List<Integer>> result) {
        // If we reached the target, save this path
        if (current == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        // Explore all neighbors
        for (int neighbor : graph[current]) {
            path.add(neighbor);
            dfs(graph, neighbor, target, path, result);
            path.remove(path.size() - 1);  // Backtrack
        }
    }
    // Alternative: BFS approach to find all paths
    public static List<List<Integer>> allPathsBFS(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<List<Integer>> queue = new LinkedList<>();
        // Start with initial path containing just node 0
        List<Integer> initialPath = new ArrayList<>();
        initialPath.add(0);
        queue.offer(initialPath);
        int target = graph.length - 1;
        while (!queue.isEmpty()) {
            List<Integer> path = queue.poll();
            int lastNode = path.get(path.size() - 1);
            // If reached target, add to result
            if (lastNode == target) {
                result.add(path);
                continue;
            }
            // Explore all neighbors
            for (int neighbor : graph[lastNode]) {
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(neighbor);
                queue.offer(newPath);
            }
        }
        return result;
    }
    public static void main(String[] args) {
        // Graph: 0 -> 1 -> 3
        //        |    |
        //        v    v
        //        2 -> 3
        int[][] graph = {
            {1, 2},     // 0 -> [1, 2]
            {3},        // 1 -> [3]
            {3},        // 2 -> [3]
            {}          // 3 -> []
        };
        List<List<Integer>> paths = allPathsSourceTarget(graph);
        System.out.println("All paths from 0 to " + (graph.length - 1) + ":");
        for (List<Integer> path : paths) {
            System.out.println(path);
        }
        // Output:
        // [0, 1, 3]
        // [0, 2, 3]
        // Another example
        int[][] graph2 = {
            {4, 3, 1},  // 0 -> [4, 3, 1]
            {3, 2, 4},  // 1 -> [3, 2, 4]
            {3},        // 2 -> [3]
            {4},        // 3 -> [4]
            {}          // 4 -> []
        };
        List<List<Integer>> paths2 = allPathsBFS(graph2);
        System.out.println("\nAll paths from 0 to " + (graph2.length - 1) + ":");
        for (List<Integer> path : paths2) {
            System.out.println(path);
        }
        // Output: Multiple paths from 0 to 4
    }
}