Breadth-First Search

From a start vertex, explore the graph layer by layer. Use a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours.

Algorithm

Basic Implementation

Basic.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Basic {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> adj = new LinkedHashMap<>();
        adj.put(1, List.of(2, 3));
        adj.put(2, List.of(1, 4));
        adj.put(3, List.of(1, 4));
        adj.put(4, List.of(2, 3, 5));
        adj.put(5, List.of(4, 6));
        adj.put(6, List.of(5));

        int start = 1;
        Set<Integer> visited = new LinkedHashSet<>();
        visited.add(start);
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(start);
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int v = queue.pollFirst();
            order.add(v);
            for (int nb : adj.get(v)) {
                if (!visited.contains(nb)) {
                    visited.add(nb);
                    queue.addLast(nb);
                }
            }
        }
        System.out.println(order);
    }
}

BFS uses a queue, so it visits the start vertex, then its neighbours, then the next layer.

Step 1 - Start at 1

The queue starts with [1] and visited starts with {1}.

Step 2 - Visit the first layer

After processing 1, neighbours 2 and 3 are marked and queued.

Step 3 - Deterministic visit order

With insertion-ordered neighbours, BFS visits [1, 2, 3, 4, 5, 6].

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

Java: use LinkedHashMap so the adjacency list keeps insertion order, matching the lesson spec's deterministic neighbour order.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue `ArrayDeque<Integer>` doubles as a FIFO queue: `addLast` to enqueue, `pollFirst` to dequeue.

visited-before-enqueue Mark a vertex visited before pushing it onto the queue. Keeps the queue size bounded by V.