Master BFS - O(V+E) Graph Traversal

function bfs(graph, start) {
    /**
     * Breadth-First Search (BFS) Traversal
     * Time: O(V + E), Space: O(V)
     * Returns: Array of nodes in BFS order
     */
    const visited = new Set([start]);
    const queue = [start];
    const result = [];

    while (queue.length > 0) {
        // Dequeue from front (FIFO)
        const node = queue.shift();
        result.push(node);

        // Explore all neighbors
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }

    return result;
}

// Usage example
const graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 4],
    3: [1],
    4: [2]
};

console.log(bfs(graph, 0)); // [0, 1, 2, 3, 4]

package main

import "fmt"

func bfs(graph map[int][]int, start int) []int {
    // Breadth-First Search (BFS) Traversal
    // Time: O(V + E), Space: O(V)
    visited := make(map[int]bool)
    queue := []int{start}
    result := []int{}
    visited[start] = true

    for len(queue) > 0 {
        // Dequeue from front (FIFO)
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)

        // Explore all neighbors
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }

    return result
}

func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {0, 2, 3},
        2: {0, 1, 4},
        3: {1},
        4: {2},
    }

    fmt.Println(bfs(graph, 0)) // [0 1 2 3 4]
}

import java.util.*;

public class BFS {
    /**
     * Breadth-First Search (BFS) Traversal
     * Time: O(V + E), Space: O(V)
     * Returns: List of nodes in BFS order
     */
    public static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

        visited.add(start);
        queue.offer(start);

        while (!queue.isEmpty()) {
            // Dequeue from front (FIFO)
            int node = queue.poll();
            result.add(node);

            // Explore all neighbors
            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 2, 3));
        graph.put(2, Arrays.asList(0, 1, 4));
        graph.put(3, Arrays.asList(1));
        graph.put(4, Arrays.asList(2));

        System.out.println(bfs(graph, 0)); // [0, 1, 2, 3, 4]
    }
}

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>

// Breadth-First Search (BFS) Traversal
// Time: O(V + E), Space: O(V)
std::vector<int> bfs(std::unordered_map<int, std::vector<int>>& graph, int start) {
    std::unordered_set<int> visited;
    std::queue<int> queue;
    std::vector<int> result;

    visited.insert(start);
    queue.push(start);

    while (!queue.empty()) {
        // Dequeue from front (FIFO)
        int node = queue.front();
        queue.pop();
        result.push_back(node);

        // Explore all neighbors
        for (int neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                queue.push(neighbor);
            }
        }
    }

    return result;
}

int main() {
    std::unordered_map<int, std::vector<int>> graph = {
        {0, {1, 2}},
        {1, {0, 2, 3}},
        {2, {0, 1, 4}},
        {3, {1}},
        {4, {2}}
    };

    auto result = bfs(graph, 0);
    for (int node : result) {
        std::cout << node << " ";
    }
    return 0;
}