Breadth-First Search

From a start vertex, explore the graph layer by layer using a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours. Visited is checked before enqueue so the queue stays bounded by V.

Algorithm

Basic Implementation

basic.dart

import 'dart:collection';

void main() {
  final adj = <int, List<int>>{
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3, 5],
    5: [4, 6],
    6: [5],
  };

  const start = 1;
  final visited = <int>{start};
  final queue = Queue<int>.from([start]);
  final order = <int>[];
  while (queue.isNotEmpty) {
    final v = queue.removeFirst();
    order.add(v);
    for (final nb in adj[v]!) {
      if (!visited.contains(nb)) {
        visited.add(nb);
        queue.add(nb);
      }
    }
  }
  print(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

Dart: Queue<int> from dart:collection gives O(1) removeFirst. A plain List would do O(n) per removeAt(0). dart:collection is part of the standard library so the page still has zero pub dependencies.
The replay shows the dequeued vertex, the queue after, and the visited set after each step, matching the lesson spec.

layered exploration A queue processes the closest vertices first.