GraphBFS

Utility class to perform Breadth-First Search (BFS) on a graph. BFS is a graph traversal algorithm that explores nodes level by level. The algorithm works as follows:

• Start from a source node
• Visit all its neighbors
• Then visit neighbors of neighbors

Use Cases:

• Shortest path in unweighted graph
• Level order traversal
• Finding connected components Time Complexity: O(V + E) Space Complexity: O(V)

bfs

Performs BFS traversal from a given source node.

List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);
    visited.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.add(neighbor);
            }
        }
    }
    return result;
}

Usage

    Map<Integer, List<Integer>> graph = new HashMap<>();
    graph.put(1, List.of(2, 3));
    graph.put(2, List.of(4, 5));
    graph.put(3, List.of(6));
    graph.put(4, List.of());
    graph.put(5, List.of());
    graph.put(6, List.of());
    List<Integer> traversal = bfs(graph, 1);
    System.out.println(traversal);