Can we always change BFS solution to DFS solution?

When to Use BFS vs DFS

Use BFS when:

1. Shortest Path in Unweighted Graphs - BFS guarantees the shortest path because it explores nodes level by level
2. Level-order Traversal - When you need to process nodes level by level
3. Finding Minimum Steps - Any problem requiring minimum number of operations
4. Web Crawling - When you want to stay closer to the starting point
5. Social Networks - Finding connections within a certain degree

Use DFS when:

1. Cycle Detection - DFS can detect back edges efficiently using recursion stack
2. Topological Sorting - DFS naturally provides the finish order needed for topological sort
3. Path Finding - When you need to find ANY path, not necessarily the shortest
4. Connected Components - DFS is more memory efficient for finding connected components
5. Maze Solving - DFS explores deeply before backtracking
6. Tree Traversals - Preorder, inorder, postorder traversals

Key Differences:

• BFS uses Queue (FIFO) - explores breadth-first, guarantees shortest path
• DFS uses Stack (LIFO) or Recursion - explores depth-first, uses less memory for sparse graphs
• BFS Space Complexity: O(V) where V is vertices
• DFS Space Complexity: O(h) where h is height of recursion tree

The choice depends on your specific problem requirements - use BFS for shortest paths and level-based problems, use DFS for cycle detection and topological sorting.

BFS

import java.util.*;

public class GraphTraversal {

    // Graph representation using adjacency list
    static class Graph {
        private int vertices;
        private List<List<Integer>> adjList;

        public Graph(int vertices) {
            this.vertices = vertices;
            this.adjList = new ArrayList<>(vertices);
            for (int i = 0; i < vertices; i++) {
                adjList.add(new ArrayList<>());
            }
        }

        public void addEdge(int src, int dest) {
            adjList.get(src).add(dest);
            adjList.get(dest).add(src); // For undirected graph
        }

        public List<Integer> getNeighbors(int vertex) {
            return adjList.get(vertex);
        }

        public int getVertices() {
            return vertices;
        }
    }
    // BFS Implementation - Uses Queue (FIFO)
    public static List<Integer> bfs(Graph graph, int start) {
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[graph.getVertices()];
        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);

            for (int neighbor : graph.getNeighbors(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }

        return result;
    }
// WHEN TO USE BFS - Shortest Path in Unweighted Graph
    public static int shortestPath(Graph graph, int start, int target) {
        if (start == target) return 0;

        boolean[] visited = new boolean[graph.getVertices()];
        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> distance = new LinkedList<>();

        visited[start] = true;
        queue.offer(start);
        distance.offer(0);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            int currentDistance = distance.poll();

            for (int neighbor : graph.getNeighbors(current)) {
                if (!visited[neighbor]) {
                    if (neighbor == target) {
                        return currentDistance + 1;
                    }
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                    distance.offer(currentDistance + 1);
                }
            }
        }
        return -1; // Path not found
    }
    // WHEN TO USE BFS - Level Order Traversal
    public static void levelOrderTraversal(Graph graph, int start) {
        boolean[] visited = new boolean[graph.getVertices()];
        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> level = new LinkedList<>();

        visited[start] = true;
        queue.offer(start);
        level.offer(0);

        int currentLevel = 0;
        System.out.print("Level 0: ");

        while (!queue.isEmpty()) {
            int current = queue.poll();
            int nodeLevel = level.poll();

            if (nodeLevel > currentLevel) {
                currentLevel = nodeLevel;
                System.out.print("\nLevel " + currentLevel + ": ");
            }

            System.out.print(current + " ");

            for (int neighbor : graph.getNeighbors(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                    level.offer(nodeLevel + 1);
                }
            }
        }
        System.out.println();
    }
    public static void main(String[] args) {
        // Create a sample graph
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);

        System.out.println("Graph representation:");
        System.out.println("0 -- 1 -- 3");
        System.out.println("|    |");
        System.out.println("2    4");
        System.out.println("|");
        System.out.println("5");
        System.out.println();

        System.out.println("BFS traversal from node 0: " + bfs(graph, 0));
        System.out.println();

        System.out.println("Shortest path from 0 to 5: " + shortestPath(graph, 0, 5));
        System.out.println("Graph has cycle: " + hasCycle(graph));
        System.out.println();

        System.out.println("Level order traversal from node 0:");
        levelOrderTraversal(graph, 0);
    }
}

DFS

import java.util.*;

public class GraphTraversal {

    // Graph representation using adjacency list
    static class Graph {
        private int vertices;
        private List<List<Integer>> adjList;

        public Graph(int vertices) {
            this.vertices = vertices;
            this.adjList = new ArrayList<>(vertices);
            for (int i = 0; i < vertices; i++) {
                adjList.add(new ArrayList<>());
            }
        }

        public void addEdge(int src, int dest) {
            adjList.get(src).add(dest);
            adjList.get(dest).add(src); // For undirected graph
        }

        public List<Integer> getNeighbors(int vertex) {
            return adjList.get(vertex);
        }

        public int getVertices() {
            return vertices;
        }
    }

    // DFS Implementation - Uses Stack (LIFO) or Recursion
    public static List<Integer> dfsIterative(Graph graph, int start) {
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[graph.getVertices()];
        Stack<Integer> stack = new Stack<>();

        stack.push(start);

        while (!stack.isEmpty()) {
            int current = stack.pop();

            if (!visited[current]) {
                visited[current] = true;
                result.add(current);

                // Add neighbors in reverse order to maintain left-to-right traversal
                List<Integer> neighbors = graph.getNeighbors(current);
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    if (!visited[neighbors.get(i)]) {
                        stack.push(neighbors.get(i));
                    }
                }
            }
        }

        return result;
    }

    // DFS Recursive Implementation
    public static List<Integer> dfsRecursive(Graph graph, int start) {
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[graph.getVertices()];
        dfsRecursiveHelper(graph, start, visited, result);
        return result;
    }

    private static void dfsRecursiveHelper(Graph graph, int current, boolean[] visited, List<Integer> result) {
        visited[current] = true;
        result.add(current);

        for (int neighbor : graph.getNeighbors(current)) {
            if (!visited[neighbor]) {
                dfsRecursiveHelper(graph, neighbor, visited, result);
            }
        }
    }

    // WHEN TO USE DFS - Detecting Cycles in Undirected Graph
    public static boolean hasCycle(Graph graph) {
        boolean[] visited = new boolean[graph.getVertices()];

        for (int i = 0; i < graph.getVertices(); i++) {
            if (!visited[i]) {
                if (hasCycleUtil(graph, i, visited, -1)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean hasCycleUtil(Graph graph, int current, boolean[] visited, int parent) {
        visited[current] = true;

        for (int neighbor : graph.getNeighbors(current)) {
            if (!visited[neighbor]) {
                if (hasCycleUtil(graph, neighbor, visited, current)) {
                    return true;
                }
            } else if (neighbor != parent) {
                return true; // Back edge found - cycle detected
            }
        }
        return false;
    }

    // WHEN TO USE DFS - Topological Sort (for DAG)
    public static List<Integer> topologicalSort(Graph graph) {
        boolean[] visited = new boolean[graph.getVertices()];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < graph.getVertices(); i++) {
            if (!visited[i]) {
                topologicalSortUtil(graph, i, visited, stack);
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }

    private static void topologicalSortUtil(Graph graph, int current, boolean[] visited, Stack<Integer> stack) {
        visited[current] = true;

        for (int neighbor : graph.getNeighbors(current)) {
            if (!visited[neighbor]) {
                topologicalSortUtil(graph, neighbor, visited, stack);
            }
        }

        stack.push(current);
    }

    public static void main(String[] args) {
        // Create a sample graph
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);

        System.out.println("Graph representation:");
        System.out.println("0 -- 1 -- 3");
        System.out.println("|    |");
        System.out.println("2    4");
        System.out.println("|");
        System.out.println("5");
        System.out.println();

        System.out.println("DFS iterative from node 0: " + dfsIterative(graph, 0));
        System.out.println("DFS recursive from node 0: " + dfsRecursive(graph, 0));
        System.out.println();

        System.out.println("Graph has cycle: " + hasCycle(graph));
        System.out.println();

        System.out.println("Level order traversal from node 0:");
        levelOrderTraversal(graph, 0);
    }
}