BFS Implementation in Java for Competitive Programming

Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level. It starts at a given node and explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. BFS is often used to find the shortest path in an unweighted graph, or to solve problems where the number of steps to reach a solution is minimized.

BFS Implementation Explanation

The core idea of BFS is to maintain a queue of nodes to visit. We start with the initial node, add it to the queue, mark it as visited, and then iteratively process the queue. For each node dequeued from the queue, we explore its unvisited neighbors, enqueue them, and mark them as visited. This process continues until the queue is empty.

Step-by-Step Guide to Implementing BFS in Java

1. Graph Representation

There are two common ways to represent a graph: Adjacency Matrix and Adjacency List. For BFS, an Adjacency List is generally preferred because it's more memory-efficient for sparse graphs (graphs with fewer edges).

Adjacency List: An array where each index represents a node, and the value at each index is a list of its adjacent nodes (neighbors).

 import java.util.*;

    public class Graph {
        private int numVertices;
        private LinkedList<Integer>[] adjList;

        public Graph(int numVertices) {
            this.numVertices = numVertices;
            adjList = new LinkedList[numVertices];
            for (int i = 0; i < numVertices; i++) {
                adjList[i] = new LinkedList<>();
            }
        }

        public void addEdge(int u, int v) {
            adjList[u].add(v);
            adjList[v].add(u); // For undirected graph
        }

        public LinkedList<Integer>[] getAdjList() {
            return adjList;
        }
    } 

2. BFS Algorithm Implementation

The BFS algorithm utilizes a queue and a `visited` array to keep track of explored nodes.

 import java.util.*;

    public class BFS {

        public static void bfs(Graph graph, int startNode) {
            int numVertices = graph.numVertices;
            LinkedList<Integer>[] adjList = graph.getAdjList();
            boolean[] visited = new boolean[numVertices];
            Queue<Integer> queue = new LinkedList<>();

            // Mark the starting node as visited and enqueue it
            visited[startNode] = true;
            queue.offer(startNode);

            while (!queue.isEmpty()) {
                // Dequeue a vertex from queue and print it
                int u = queue.poll();
                System.out.print(u + " ");

                // Get all adjacent vertices of the dequeued vertex u
                // If a adjacent has not been visited, then mark it
                // visited and enqueue it
                Iterator<Integer> i = adjList[u].listIterator();
                while (i.hasNext()) {
                    int v = i.next();
                    if (!visited[v]) {
                        visited[v] = true;
                        queue.offer(v);
                    }
                }
            }
        }

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

            System.out.println("BFS traversal starting from vertex 0:");
            bfs(graph, 0); // Start BFS from vertex 0
            System.out.println();
        }
    } 

3. Key Data Structures and Logic

• visited array: A boolean array to mark nodes that have been visited. This prevents cycles and ensures that each node is processed only once.
• Queue: A data structure that follows the FIFO (First-In, First-Out) principle. Nodes are added to the rear of the queue (enqueue) and removed from the front (dequeue). The `LinkedList` class is used to implement the Queue interface.
• Looping through neighbors: For each dequeued node, iterate through its neighbors (using the adjacency list) and enqueue any unvisited neighbors.

Competitive Programming Examples and Solutions

Here are some examples of how BFS can be applied in competitive programming problems. These examples are designed to illustrate common patterns and challenges.

 import java.util.*;

        class MazeSolver {

            static class Point {
                int x, y, dist;

                public Point(int x, int y, int dist) {
                    this.x = x;
                    this.y = y;
                    this.dist = dist;
                }
            }

            public static int shortestPath(char[][] maze) {
                int rows = maze.length;
                int cols = maze[0].length;

                Point start = null, end = null;
                for (int i = 0; i < rows; i++) {
                    for (int j = 0; j < cols; j++) {
                        if (maze[i][j] == 'S') {
                            start = new Point(i, j, 0);
                        } else if (maze[i][j] == 'E') {
                            end = new Point(i, j, 0);
                        }
                    }
                }

                if (start == null || end == null) {
                    return -1; // Start or end not found
                }

                boolean[][] visited = new boolean[rows][cols];
                Queue<Point> queue = new LinkedList<>();
                queue.offer(start);
                visited[start.x][start.y] = true;

                int[] dx = {0, 0, 1, -1};
                int[] dy = {1, -1, 0, 0};

                while (!queue.isEmpty()) {
                    Point current = queue.poll();

                    if (current.x == end.x && current.y == end.y) {
                        return current.dist;
                    }

                    for (int i = 0; i < 4; i++) {
                        int newX = current.x + dx[i];
                        int newY = current.y + dy[i];

                        if (newX >= 0 && newX < rows && newY >= 0 && newY < cols &&
                            maze[newX][newY] != '#' && !visited[newX][newY]) {
                            visited[newX][newY] = true;
                            queue.offer(new Point(newX, newY, current.dist + 1));
                        }
                    }
                }

                return -1; // No path found
            }

            public static void main(String[] args) {
                char[][] maze = {
                    {'S', '.', '#', '#', '.'},
                    {'.', '#', '.', '.', '.'},
                    {'.', '.', '.', '#', 'E'},
                    {'#', '.', '#', '.', '.'}
                };

                int shortestDistance = shortestPath(maze);
                if (shortestDistance != -1) {
                    System.out.println("Shortest distance from S to E: " + shortestDistance);
                } else {
                    System.out.println("No path from S to E");
                }
            }
        } 

 import java.util.*;

        class GraphConnectivity {

            public static int minEdgesToConnect(int n, List<List<Integer>> adj) {
                if (n <= 0 || adj == null || adj.size() != n) {
                    return -1; // Invalid input
                }

                boolean[] visited = new boolean[n];
                int components = 0;

                for (int i = 0; i < n; i++) {
                    if (!visited[i]) {
                        bfs(i, adj, visited);
                        components++;
                    }
                }

                return components - 1; // Number of edges needed to connect components
            }

            private static void bfs(int startNode, List<List<Integer>> adj, boolean[] visited) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(startNode);
                visited[startNode] = true;

                while (!queue.isEmpty()) {
                    int u = queue.poll();

                    for (int v : adj.get(u)) {
                        if (!visited[v]) {
                            visited[v] = true;
                            queue.offer(v);
                        }
                    }
                }
            }

            public static void main(String[] args) {
                int n = 6; // Number of nodes
                List<List<Integer>> adj = new ArrayList<>();

                // Initialize adjacency list
                for (int i = 0; i < n; i++) {
                    adj.add(new ArrayList<>());
                }

                // Create the graph
                adj.get(0).add(1);
                adj.get(1).add(0);

                adj.get(2).add(3);
                adj.get(3).add(2);

                adj.get(4).add(5);
                adj.get(5).add(4);

                int minEdges = minEdgesToConnect(n, adj);
                System.out.println("Minimum edges to connect: " + minEdges);  //Output: 2
            }
        } 

Tips for Competitive Programming

• Choose the right data structure: Adjacency lists are generally more efficient for sparse graphs.
• Handle edge cases: Consider cases like empty graphs, disconnected graphs, or invalid inputs.
• Optimize for performance: In competitive programming, efficiency is crucial. Minimize unnecessary operations and use efficient data structures.
• Practice: The best way to master BFS is to solve a variety of problems.
• Understand the problem constraints: Carefully analyze the size of the input graph, the range of values, and the time/memory limits.