Queue-Based BFS

Problem Statement

Write a Java program that implements a Breadth-First Search (BFS) algorithm for a graph using a queue. Represent the graph as an adjacency list and print the nodes visited in BFS order, starting from a specified node. The program should handle undirected graphs, enqueue nodes to explore them level by level, and mark visited nodes to avoid cycles. Test the implementation with various graph structures, including connected, disconnected, and cyclic graphs, as well as edge cases like empty graphs. You can visualize this as exploring a network of cities, visiting all cities at the current distance from the starting point before moving farther, using a queue to keep track of the next cities to visit.

Input:

• Number of nodes n (0 ≤ n ≤ 10^5).
• List of edges as pairs of nodes (e.g., [[0,1], [1,2]] for edges 0-1, 1-2).
• Starting node for BFS. Output: A string of nodes visited in BFS order (e.g., "0 1 2"). Constraints:
• Nodes are integers from 0 to n-1.
• Edges are undirected (if u-v exists, v-u exists).
• The graph may be empty, disconnected, or cyclic. Example:
• Input: n=4, edges=[[0,1], [0,2], [1,3]], start=0
• Output: "0 1 2 3"
• Explanation: Starting from node 0, visit 0, then neighbors 1 and 2, then 1’s neighbor 3.
• Input: n=3, edges=[], start=0
• Output: "0"
• Explanation: No edges, only node 0 is visited.

Pseudocode

CLASS IntQueue
    SET array to new integer array of size 1000
    SET front to 0
    SET rear to -1
    SET size to 0
    
    FUNCTION enqueue(number)
        IF size equals array length THEN
            RETURN false
        ENDIF
        INCREMENT rear
        SET array[rear] to number
        INCREMENT size
        RETURN true
    ENDFUNCTION
    
    FUNCTION dequeue()
        IF size equals 0 THEN
            RETURN null
        ENDIF
        SET number to array[front]
        INCREMENT front
        DECREMENT size
        RETURN number
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN size equals 0
    ENDFUNCTION
ENDCLASS

FUNCTION bfs(n, edges, start)
    IF n equals 0 THEN
        RETURN empty string
    ENDIF
    CREATE adjList as new list of lists for n nodes
    FOR each edge in edges
        ADD edge[1] to adjList[edge[0]]
        ADD edge[0] to adjList[edge[1]] (undirected)
    ENDFOR
    CREATE queue as new IntQueue
    CREATE visited as boolean array of size n, initialized to false
    CREATE result as new StringBuilder
    ENQUEUE start to queue
    SET visited[start] to true
    APPEND start to result
    WHILE queue is not empty
        SET node to queue.dequeue()
        FOR each neighbor in adjList[node]
            IF not visited[neighbor] THEN
                ENQUEUE neighbor to queue
                SET visited[neighbor] to true
                APPEND " " and neighbor to result
            ENDIF
        ENDFOR
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of graphs (n, edges, start)
    FOR each testCase in testCases
        PRINT test case details
        CALL bfs(testCase.n, testCase.edges, testCase.start)
        PRINT BFS order
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define an IntQueue class with: a. An array to store integers, with front, rear, and size. b. Methods: enqueue (add to rear), dequeue (remove from front), isEmpty.
2. In the bfs method: a. If n=0, return empty string. b. Build an adjacency list from edges (add u-v and v-u for undirected). c. Create a queue, a boolean array for visited nodes, and a StringBuilder for output. d. Enqueue the start node, mark it visited, append to result. e. While queue is not empty:
   • Dequeue a node.
   • For each unvisited neighbor, enqueue it, mark it visited, append to result. f. Return the result string.
3. In the main method, test with graphs of varying structures (connected, disconnected, cyclic, empty).

Java Implementation

import java.util.*;

public class QueueBasedBFS {
    // Custom queue implementation for integers
    static class IntQueue {
        private int[] array;
        private int front;
        private int rear;
        private int size;
        private static final int DEFAULT_SIZE = 1000;

        public IntQueue() {
            array = new int[DEFAULT_SIZE];
            front = 0;
            rear = -1;
            size = 0;
        }

        public boolean enqueue(int number) {
            if (size == array.length) {
                return false; // Queue full
            }
            array[++rear] = number;
            size++;
            return true;
        }

        public Integer dequeue() {
            if (size == 0) {
                return null; // Queue empty
            }
            int number = array[front++];
            size--;
            return number;
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }

    // Performs BFS and returns nodes in visit order
    public String bfs(int n, int[][] edges, int start) {
        if (n == 0) {
            return "";
        }

        // Build adjacency list
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]); // Undirected
        }

        // BFS
        IntQueue queue = new IntQueue();
        boolean[] visited = new boolean[n];
        StringBuilder result = new StringBuilder();

        queue.enqueue(start);
        visited[start] = true;
        result.append(start);

        while (!queue.isEmpty()) {
            Integer node = queue.dequeue();
            if (node == null) break;
            for (int neighbor : adjList.get(node)) {
                if (!visited[neighbor]) {
                    queue.enqueue(neighbor);
                    visited[neighbor] = true;
                    result.append(" ").append(neighbor);
                }
            }
        }

        return result.toString();
    }

    // Helper class for test cases
    static class GraphTestCase {
        int n;
        int[][] edges;
        int start;

        GraphTestCase(int n, int[][] edges, int start) {
            this.n = n;
            this.edges = edges;
            this.start = start;
        }
    }

    // Main method to test BFS
    public static void main(String[] args) {
        QueueBasedBFS bfs = new QueueBasedBFS();

        // Test cases
        List<GraphTestCase> testCases = new ArrayList<>();
        
        // Test case 1: Connected graph
        testCases.add(new GraphTestCase(
            4,
            new int[][]{{0,1}, {0,2}, {1,3}},
            0
        ));
        
        // Test case 2: Cyclic graph
        testCases.add(new GraphTestCase(
            4,
            new int[][]{{0,1}, {1,2}, {2,3}, {3,0}},
            1
        ));
        
        // Test case 3: Disconnected graph
        testCases.add(new GraphTestCase(
            5,
            new int[][]{{0,1}, {2,3}},
            0
        ));
        
        // Test case 4: Empty graph
        testCases.add(new GraphTestCase(
            0,
            new int[][]{},
            0
        ));
        
        // Test case 5: Single node
        testCases.add(new GraphTestCase(
            1,
            new int[][]{},
            0
        ));

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            GraphTestCase test = testCases.get(i);
            System.out.println("Test case " + (i + 1) + ": n=" + test.n + ", start=" + test.start);
            System.out.println("Edges: " + Arrays.deepToString(test.edges));
            String result = bfs.bfs(test.n, test.edges, test.start);
            System.out.println("BFS order: " + (result.isEmpty() ? "[]" : result) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1: n=4, start=0
Edges: [[0, 1], [0, 2], [1, 3]]
BFS order: 0 1 2 3

Test case 2: n=4, start=1
Edges: [[0, 1], [1, 2], [2, 3], [3, 0]]
BFS order: 1 0 2 3

Test case 3: n=5, start=0
Edges: [[0, 1], [2, 3]]
BFS order: 0 1

Test case 4: n=0, start=0
Edges: []
BFS order: []

Test case 5: n=1, start=0
Edges: []
BFS order: 0

Explanation:

• Test case 1: From node 0, visits 0, then 1 and 2, then 3 (via 1).
• Test case 2: From node 1 in a cycle (0-1-2-3-0), visits 1, then 0 and 2, then 3.
• Test case 3: From node 0, visits 0 and 1; nodes 2, 3, 4 are disconnected.
• Test case 4: Empty graph returns empty string.
• Test case 5: Single node 0, no edges, visits only 0.

How It Works

• IntQueue:
  • Uses an array with front, rear, and size for FIFO operations.
  • enqueue: Adds to rear if not full.
  • dequeue: Removes from front if not empty.
• bfs:
  • Builds an adjacency list from edges (undirected: add u-v and v-u).
  • Uses a queue to explore nodes level by level, a boolean array to track visited nodes, and a StringBuilder for output.
  • Enqueues start node, marks visited, appends to result.
  • Dequeues nodes, enqueues unvisited neighbors, appends them to result.
• Example Trace (Test case 1):
  • n=4, edges=[[0,1], [0,2], [1,3]], start=0.
  • Adjacency list: [0: [1,2], 1: [0,3], 2: [0], 3: [1]].
  • Enqueue 0: queue=[0], visited=[T,F,F,F], result="0".
  • Dequeue 0, enqueue 1,2: queue=[1,2], visited=[T,T,T,F], result="0 1 2".
  • Dequeue 1, enqueue 3: queue=[2,3], visited=[T,T,T,T], result="0 1 2 3".
  • Dequeue 2, 3: queue=[], result="0 1 2 3".
• Main Method: Tests connected, cyclic, disconnected, empty, and single-node graphs.

Complexity Analysis Table

Note:

• V is the number of vertices, E is the number of edges.
• Time complexity: O(V + E) for visiting all nodes and edges via adjacency list.
• Space complexity: O(V) for queue and visited array, O(E) for adjacency list.
• Worst case: O(V + E) time and space for dense graphs.

✅ Tip: Use a queue for BFS to ensure level-by-level traversal, and an adjacency list for efficient neighbor access. Test with cyclic and disconnected graphs to verify correct handling of visited nodes.

⚠ Warning: Always mark nodes as visited before enqueuing to avoid infinite loops in cyclic graphs. Ensure the queue size is sufficient for large graphs.