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

Canonical adjacency list:

1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 4]
4 -> [2, 3, 5]
5 -> [4, 6]
6 -> [5]

Starting at vertex 1, the BFS visit order is [1, 2, 3, 4, 5, 6].

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);
    }
}

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.