BFS Graph Traversal Explained — How It Works, Why It Matters, and When to Use It

import java.util.*;

public class BreadthFirstSearch {

    // Represent the graph as an adjacency list.
    // Each key is a node, its value is the list of neighbours.
    private final Map<Integer, List<Integer>> adjacencyList;

    public BreadthFirstSearch() {
        this.adjacencyList = new HashMap<>();
    }

    // Add an undirected edge between two nodes.
    public void addEdge(int nodeA, int nodeB) {
        adjacencyList.computeIfAbsent(nodeA, k -> new ArrayList<>()).add(nodeB);
        adjacencyList.computeIfAbsent(nodeB, k -> new ArrayList<>()).add(nodeA);
    }

    // Perform BFS starting from the given source node.
    // Returns the order in which nodes were visited.
    public List<Integer> bfs(int source) {
        List<Integer> visitedOrder = new ArrayList<>();

        // Track which nodes we have already enqueued so we never process a node twice.
        Set<Integer> visited = new HashSet<>();

        // The queue drives the level-by-level expansion.
        Queue<Integer> queue = new LinkedList<>();

        // Seed the BFS: mark the source visited BEFORE enqueuing,
        // so nothing else accidentally enqueues it again.
        visited.add(source);
        queue.offer(source);

        while (!queue.isEmpty()) {
            // Pull the oldest node from the front of the queue (FIFO).
            int currentNode = queue.poll();
            visitedOrder.add(currentNode);

            // Look at every neighbour of the current node.
            List<Integer> neighbours = adjacencyList.getOrDefault(currentNode, Collections.emptyList());
            for (int neighbour : neighbours) {
                if (!visited.contains(neighbour)) {
                    // Mark visited NOW, at enqueue time, not later.
                    // If we waited until dequeue, we could add the same node to the
                    // queue multiple times before we ever get around to processing it.
                    visited.add(neighbour);
                    queue.offer(neighbour);
                }
            }
        }

        return visitedOrder;
    }

    public static void main(String[] args) {
        BreadthFirstSearch graph = new BreadthFirstSearch();

        // Build a simple social-network-style graph:
        //
        //   1 -- 2 -- 5
        //   |    |
        //   3 -- 4
        //        |
        //        6
        //
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 4);
        graph.addEdge(4, 6);

        System.out.println("BFS traversal starting from node 1:");
        List<Integer> result = graph.bfs(1);
        System.out.println(result);

        // Node 1 is at distance 0.
        // Nodes 2 and 3 are at distance 1 — visited before anything further.
        // Nodes 4 and 5 are at distance 2.
        // Node 6 is at distance 3 — visited last.
    }
}

import java.util.*;

public class ShortestPathBFS {

    private final Map<String, List<String>> adjacencyList;

    public ShortestPathBFS() {
        this.adjacencyList = new HashMap<>();
    }

    public void addEdge(String cityA, String cityB) {
        adjacencyList.computeIfAbsent(cityA, k -> new ArrayList<>()).add(cityB);
        adjacencyList.computeIfAbsent(cityB, k -> new ArrayList<>()).add(cityA);
    }

    // Returns the shortest path from source to destination as an ordered list of nodes.
    // Returns an empty list if no path exists.
    public List<String> shortestPath(String source, String destination) {

        // parentMap[node] = the node that discovered it during BFS.
        // This lets us trace the path backwards once we reach the destination.
        Map<String, String> parentMap = new HashMap<>();

        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        visited.add(source);
        queue.offer(source);
        parentMap.put(source, null); // Source has no parent.

        while (!queue.isEmpty()) {
            String currentCity = queue.poll();

            // Early exit: stop as soon as we dequeue the destination.
            // BFS guarantees this is the shortest path.
            if (currentCity.equals(destination)) {
                return reconstructPath(parentMap, source, destination);
            }

            List<String> neighbours = adjacencyList.getOrDefault(currentCity, Collections.emptyList());
            for (String neighbour : neighbours) {
                if (!visited.contains(neighbour)) {
                    visited.add(neighbour);
                    parentMap.put(neighbour, currentCity); // Record who discovered this node.
                    queue.offer(neighbour);
                }
            }
        }

        return Collections.emptyList(); // No path found.
    }

    // Walk the parentMap backwards from destination to source, then reverse.
    private List<String> reconstructPath(Map<String, String> parentMap, String source, String destination) {
        List<String> path = new ArrayList<>();
        String step = destination;

        // Follow the chain of parents until we hit the source (whose parent is null).
        while (step != null) {
            path.add(step);
            step = parentMap.get(step);
        }

        // We built the path backwards (destination → source), so flip it.
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        ShortestPathBFS cityGraph = new ShortestPathBFS();

        // A simplified rail network:
        //
        //  London -- Oxford -- Birmingham
        //    |                    |
        //  Brighton            Manchester
        //                         |
        //                      Edinburgh
        //
        cityGraph.addEdge("London", "Oxford");
        cityGraph.addEdge("London", "Brighton");
        cityGraph.addEdge("Oxford", "Birmingham");
        cityGraph.addEdge("Birmingham", "Manchester");
        cityGraph.addEdge("Manchester", "Edinburgh");

        List<String> path = cityGraph.shortestPath("London", "Edinburgh");
        System.out.println("Shortest path from London to Edinburgh:");
        System.out.println(String.join(" → ", path));
        System.out.println("Total stops: " + (path.size() - 1));

        // Brighton is a dead end in this network — no path to Edinburgh via Brighton.
        List<String> noPathCheck = cityGraph.shortestPath("Brighton", "Edinburgh");
        // Brighton connects only to London, so it finds London → Oxford → Birmingham → Manchester → Edinburgh
        System.out.println("\nShortest path from Brighton to Edinburgh:");
        System.out.println(String.join(" → ", noPathCheck));
    }
}

import java.util.*;

public class LevelOrderBFS {

    private final Map<Integer, List<Integer>> adjacencyList;

    public LevelOrderBFS() {
        this.adjacencyList = new HashMap<>();
    }

    public void addEdge(int nodeA, int nodeB) {
        adjacencyList.computeIfAbsent(nodeA, k -> new ArrayList<>()).add(nodeB);
        adjacencyList.computeIfAbsent(nodeB, k -> new ArrayList<>()).add(nodeA);
    }

    // Returns a list of lists. Each inner list holds nodes at the same BFS depth.
    // e.g. result.get(0) = [source], result.get(1) = direct neighbours, etc.
    public List<List<Integer>> bfsByLevel(int source) {
        List<List<Integer>> levels = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

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

        while (!queue.isEmpty()) {
            // How many nodes are in the queue RIGHT NOW?
            // All of them belong to the current level.
            int nodesAtCurrentLevel = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            // Only process the nodes that were in the queue at the start of this iteration.
            // Any nodes we add during this loop belong to the NEXT level.
            for (int i = 0; i < nodesAtCurrentLevel; i++) {
                int currentNode = queue.poll();
                currentLevel.add(currentNode);

                List<Integer> neighbours = adjacencyList.getOrDefault(currentNode, Collections.emptyList());
                for (int neighbour : neighbours) {
                    if (!visited.contains(neighbour)) {
                        visited.add(neighbour);
                        queue.offer(neighbour); // Goes into NEXT level's batch.
                    }
                }
            }

            levels.add(currentLevel);
        }

        return levels;
    }

    public static void main(String[] args) {
        LevelOrderBFS graph = new LevelOrderBFS();

        // Simulating degrees of separation in a friend network.
        // Alice(1) knows Bob(2) and Carol(3).
        // Bob knows Dave(4) and Eve(5).
        // Carol knows Frank(6).
        // Dave knows Grace(7).
        graph.addEdge(1, 2); // Alice - Bob
        graph.addEdge(1, 3); // Alice - Carol
        graph.addEdge(2, 4); // Bob   - Dave
        graph.addEdge(2, 5); // Bob   - Eve
        graph.addEdge(3, 6); // Carol - Frank
        graph.addEdge(4, 7); // Dave  - Grace

        List<List<Integer>> levels = graph.bfsByLevel(1);

        String[] names = {"", "Alice", "Bob", "Carol", "Dave", "Eve", "Frank", "Grace"};

        for (int depth = 0; depth < levels.size(); depth++) {
            List<Integer> nodesAtDepth = levels.get(depth);
            List<String> nodeNames = new ArrayList<>();
            for (int nodeId : nodesAtDepth) {
                nodeNames.add(names[nodeId]);
            }
            System.out.println("Degree " + depth + ": " + nodeNames);
        }

        System.out.println("\nPeople within 2 degrees of Alice:");
        // Degrees 0, 1 and 2 combined, excluding Alice herself.
        for (int depth = 1; depth <= 2; depth++) {
            for (int nodeId : levels.get(depth)) {
                System.out.println("  " + names[nodeId] + " (degree " + depth + ")");
            }
        }
    }
}