BFS Variants and Extensions in Competitive Programming (Java)

Breadth-First Search (BFS) is a fundamental graph traversal algorithm. While the basic BFS explores a graph layer by layer, visiting all neighbors of a node before moving to the next level, many competitive programming problems require modifications and extensions to this core algorithm. This document explores some key BFS variants and extensions relevant to competitive programming, with Java code examples.

BFS Variants and Extensions

1. Bi-Directional BFS

Standard BFS starts from a single source and expands outward. Bi-directional BFS, as the name suggests, performs two simultaneous BFS traversals: one from the starting node (source) and another from the ending node (target). The algorithm stops when the two searches meet. This can significantly reduce the search space, especially when the path between the source and target is relatively short compared to the overall graph size. Bi-directional BFS is most effective when the branching factor of the graph is high.

When to use Bi-Directional BFS:

• The shortest path between two known nodes is required.
• The graph is undirected or has both forward and backward edges from each node.
• The graph has a high branching factor.

Advantages:

• Reduced search space compared to standard BFS.
• Faster execution time, especially in graphs with high branching factors.

Disadvantages:

• Requires knowing the target node in advance.
• Can be more complex to implement than standard BFS.

  import java.util.*;

class BiDirectionalBFS {

    static class Node {
        int val;
        int distance;
        boolean visited;

        public Node(int val) {
            this.val = val;
            this.distance = Integer.MAX_VALUE;
            this.visited = false;
        }
    }

    public static int biDirectionalBFS(int[][] graph, int start, int target) {
        if (start == target) return 0;

        int n = graph.length;
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(i);
        }

        Queue<Integer> queueFromStart = new LinkedList<>();
        Queue<Integer> queueFromTarget = new LinkedList<>();

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

        nodes[target].distance = 0;
        nodes[target].visited = true;
        queueFromTarget.offer(target);


        while (!queueFromStart.isEmpty() && !queueFromTarget.isEmpty()) {
            int startNode = queueFromStart.poll();
            int targetNode = queueFromTarget.poll();

            // Expand from start
            for (int neighbor : graph[startNode]) {
                if (!nodes[neighbor].visited) {
                    nodes[neighbor].visited = true;
                    nodes[neighbor].distance = nodes[startNode].distance + 1;
                    queueFromStart.offer(neighbor);

                    if(nodes[neighbor].visited && nodes[target].visited) {
                       // Check if this node was also visited in target's bfs
                        for(int neighbor2 : graph[neighbor]) {
                            if(neighbor2 == target) return nodes[neighbor].distance + 1;
                        }
                    }
                }
            }

            //Expand from target
            for (int neighbor : graph[targetNode]) {
                if (!nodes[neighbor].visited) {
                    nodes[neighbor].visited = true;
                    nodes[neighbor].distance = nodes[targetNode].distance + 1;
                    queueFromTarget.offer(neighbor);
                    if(nodes[neighbor].visited && nodes[start].visited) {
                         for(int neighbor2 : graph[neighbor]) {
                            if(neighbor2 == start) return nodes[neighbor].distance + 1;
                        }
                    }
                }
            }

             for(int i = 0; i < n; ++i){
                if(nodes[i].visited && nodes[start].visited && nodes[target].visited){
                    return nodes[i].distance;
                }
            }

        }

        return -1; // No path found
    }


    public static void main(String[] args) {
        int[][] graph = {
            {1, 2},
            {0, 3},
            {0, 4},
            {1, 5},
            {2, 5},
            {3, 4, 6},
            {5}
        };

        int start = 0;
        int target = 6;

        int shortestPath = biDirectionalBFS(graph, start, target);

        if (shortestPath != -1) {
            System.out.println("Shortest path between " + start + " and " + target + ": " + shortestPath);
        } else {
            System.out.println("No path found between " + start + " and " + target);
        }
    }
}  

2. A* Search Algorithm

A* Search is an informed search algorithm, meaning it uses a heuristic function to guide its search. It is an extension of Dijkstra's algorithm and BFS. It aims to find the least-cost path from a starting node to a goal node. It combines the cost to reach a node (g(n)) with an estimated cost to reach the goal from that node (h(n)), using the evaluation function f(n) = g(n) + h(n).

When to use A* Search:

• Finding the shortest path in a weighted graph, especially when the graph is large.
• When a good heuristic function is available.

Advantages:

• Guaranteed to find the optimal solution if the heuristic is admissible (never overestimates the cost to reach the goal).
• More efficient than Dijkstra's algorithm or BFS in many cases.

Disadvantages:

• Performance depends heavily on the quality of the heuristic function.
• Can be memory-intensive, especially in large graphs.

  import java.util.*;

class AStarSearch {

    static class Node implements Comparable<Node> {
        int x, y;
        int g, h, f; // g: cost from start, h: heuristic, f: g + h
        Node parent;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
            this.g = 0;
            this.h = 0;
            this.f = 0;
            this.parent = null;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.f, other.f);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Node node = (Node) obj;
            return x == node.x && y == node.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    // Heuristic function (Manhattan distance)
    static int heuristic(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    public static List<Node> aStarSearch(int[][] grid, int startX, int startY, int targetX, int targetY) {
        int rows = grid.length;
        int cols = grid[0].length;

        Node startNode = new Node(startX, startY);
        Node targetNode = new Node(targetX, targetY);

        PriorityQueue<Node> openSet = new PriorityQueue<>();
        Set<Node> closedSet = new HashSet<>();

        openSet.add(startNode);

        while (!openSet.isEmpty()) {
            Node current = openSet.poll();

            if (current.equals(targetNode)) {
                // Path found, reconstruct path
                return reconstructPath(current);
            }

            closedSet.add(current);

            // Explore neighbors (up, down, left, right)
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

            for (int[] dir : directions) {
                int neighborX = current.x + dir[0];
                int neighborY = current.y + dir[1];

                // Check if neighbor is within bounds and not an obstacle (e.g., grid[x][y] == 1 is an obstacle)
                if (neighborX >= 0 && neighborX < rows && neighborY >= 0 && neighborY < cols && grid[neighborX][neighborY] == 0) {
                    Node neighbor = new Node(neighborX, neighborY);
                    int tentativeG = current.g + 1; // Cost to reach neighbor is one step

                    if (closedSet.contains(neighbor) && tentativeG >= neighbor.g) {
                        continue; // Already processed and new path is not better
                    }

                    if (!openSet.contains(neighbor) || tentativeG < neighbor.g) {
                        neighbor.g = tentativeG;
                        neighbor.h = heuristic(neighborX, neighborY, targetX, targetY);
                        neighbor.f = neighbor.g + neighbor.h;
                        neighbor.parent = current;

                        if (!openSet.contains(neighbor)) {
                            openSet.add(neighbor);
                        } else {
                           //Update existing node if necessary.
                           openSet.remove(neighbor);
                           openSet.add(neighbor);
                        }
                    }
                }
            }
        }

        // No path found
        return null;
    }

    private static List<Node> reconstructPath(Node current) {
        List<Node> path = new ArrayList<>();
        while (current != null) {
            path.add(current);
            current = current.parent;
        }
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 0, 0}
        };

        int startX = 0, startY = 0;
        int targetX = 4, targetY = 4;

        List<Node> path = aStarSearch(grid, startX, startY, targetX, targetY);

        if (path != null) {
            System.out.println("Path found:");
            for (Node node : path) {
                System.out.println("(" + node.x + ", " + node.y + ")");
            }
        } else {
            System.out.println("No path found.");
        }
    }
}  

3. 0-1 BFS (Shortest Path in a 0-1 Graph)

0-1 BFS is a variant of BFS optimized for graphs where edge weights are either 0 or 1. Instead of using a standard queue, it employs a double-ended queue (Deque). When an edge with weight 0 is encountered, the neighbor is added to the front of the Deque; when an edge with weight 1 is encountered, the neighbor is added to the back. This ensures that nodes closer to the source are processed first.

When to use 0-1 BFS:

• The graph has edge weights of only 0 and 1.
• Finding the shortest path in such a graph.

Advantages:

• More efficient than Dijkstra's algorithm for 0-1 graphs.
• Simpler to implement than Dijkstra's algorithm.

Disadvantages:

• Only applicable to graphs with 0-1 edge weights.

  import java.util.*;

class ZeroOneBFS {

    static class Edge {
        int to;
        int weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static int zeroOneBFS(List<List<Edge>> adj, int start, int end) {
        int n = adj.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        Deque<Integer> deque = new LinkedList<>();
        deque.offerFirst(start);

        while (!deque.isEmpty()) {
            int u = deque.pollFirst();

            for (Edge edge : adj.get(u)) {
                int v = edge.to;
                int weight = edge.weight;

                if (dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    if (weight == 0) {
                        deque.offerFirst(v);
                    } else {
                        deque.offerLast(v);
                    }
                }
            }
        }

        return (dist[end] == Integer.MAX_VALUE) ? -1 : dist[end];
    }

    public static void main(String[] args) {
        int n = 6; // Number of nodes
        List<List<Edge>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        // Example graph with 0-1 weights
        adj.get(0).add(new Edge(1, 0));
        adj.get(0).add(new Edge(2, 1));
        adj.get(1).add(new Edge(3, 1));
        adj.get(2).add(new Edge(3, 0));
        adj.get(2).add(new Edge(4, 0));
        adj.get(3).add(new Edge(5, 1));
        adj.get(4).add(new Edge(5, 0));

        int start = 0;
        int end = 5;

        int shortestPath = zeroOneBFS(adj, start, end);

        if (shortestPath != -1) {
            System.out.println("Shortest path from " + start + " to " + end + ": " + shortestPath);
        } else {
            System.out.println("No path found from " + start + " to " + end);
        }
    }
}  

4. Multi-Source BFS

In standard BFS, the exploration starts from a single source node. Multi-source BFS extends this concept by allowing the algorithm to begin the traversal from multiple source nodes simultaneously. All source nodes are initially added to the queue, and the algorithm proceeds as usual. This is particularly useful when finding the shortest distance from any of several starting points to other nodes in the graph.

When to use Multi-Source BFS:

• You have multiple starting points, and you want to find the shortest distance from any of them to other nodes.
• Finding the closest element of a particular type in a grid or graph.

Advantages:

• Efficiently calculates distances from multiple sources.
• Suitable for problems where the specific source is not important, but proximity to any source is.

Disadvantages:

• Requires identifying all source nodes beforehand.

  import java.util.*;

class MultiSourceBFS {

    public static int[][] multiSourceBFS(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        int[][] dist = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(dist[i], -1); // Initialize distances to -1 (unvisited)
        }

        Queue<int[]> queue = new LinkedList<>();

        // Add all source cells (cells with value 1) to the queue
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0; // Distance from source to itself is 0
                    queue.offer(new int[]{i, j});
                }
            }
        }

        // Perform BFS
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Possible movement directions

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && dist[newRow][newCol] == -1) {
                    dist[newRow][newCol] = dist[row][col] + 1;
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0},
            {1, 0, 0}
        };

        int[][] distances = multiSourceBFS(grid);

        System.out.println("Distances from nearest source:");
        for (int i = 0; i < distances.length; i++) {
            System.out.println(Arrays.toString(distances[i]));
        }
    }
}  

5. Flood Fill (Connected Component Labeling)

Flood Fill, also known as connected component labeling, is a variant of BFS (or DFS) that identifies and labels connected regions in a multi-dimensional array (e.g., an image or a grid). Starting from a seed point, it recursively explores neighboring cells with the same characteristic (e.g., the same color or value) and marks them as part of the same connected component. This process continues until all reachable cells within the component have been labeled.

When to use Flood Fill:

• Identifying and labeling connected regions in images or grids.
• Solving puzzles or games that involve finding connected components.

Advantages:

• Simple and intuitive algorithm.
• Effective for finding connected components.

Disadvantages:

• Can be memory-intensive for very large grids or images.
• Performance depends on the size of the connected components.

  import java.util.*;

class FloodFill {

    public static void floodFill(int[][] image, int sr, int sc, int newColor) {
        int rows = image.length;
        int cols = image[0].length;
        int originalColor = image[sr][sc];

        if (originalColor == newColor) {
            return; // No change needed
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});
        image[sr][sc] = newColor; // Mark the starting cell

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && image[newRow][newCol] == originalColor) {
                    image[newRow][newCol] = newColor;
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] image = {
            {1, 1, 1, 1, 1},
            {1, 1, 0, 1, 1},
            {1, 0, 0, 0, 1},
            {1, 1, 0, 1, 1},
            {1, 1, 1, 1, 1}
        };

        int startRow = 2;
        int startCol = 2;
        int newColor = 2;

        floodFill(image, startRow, startCol, newColor);

        System.out.println("Image after Flood Fill:");
        for (int i = 0; i < image.length; i++) {
            System.out.println(Arrays.toString(image[i]));
        }
    }
}  

Conclusion

These are just a few examples of BFS variants and extensions commonly encountered in competitive programming. The key to successfully applying these techniques is to understand the problem constraints and adapt the core BFS algorithm to meet the specific requirements. Practice with different types of problems is essential for mastering these techniques and improving your problem-solving skills.