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

The canonical input is the 6-vertex undirected graph from graph-adjacency-list (defined inline here). Starting at vertex 1, the deterministic visit order is [1, 2, 3, 4, 5, 6].

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

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.