bfs function

void bfs(Adjacency graph, int start, void visit(int node, int depth), { int maxDepth = -1, })

BFS from start; calls visit(node, depth) for each node. maxDepth caps depth (-1 = no limit). Audited: 2026-06-12 11:26 EDT

Implementation

void bfs(
  Adjacency graph,
  int start,
  void Function(int node, int depth) visit, {
  int maxDepth = -1,
}) {
  // Nothing to traverse from an out-of-range/empty start; return before
  // indexing `seen[start]` so a bad start index does not throw a RangeError.
  if (start < 0 || start >= graph.length) return;
  // Breadth-first: a FIFO queue of (node, depth) pairs. Mark each node seen
  // when it is ENQUEUED, not when visited, so it can never be queued twice.
  final List<bool> seen = List.filled(graph.length, false);
  final List<(int, int)> queue = <(int, int)>[(start, 0)];
  seen[start] = true;
  while (queue.isNotEmpty) {
    final (int u, int d) = queue.removeAt(0);
    visit(u, d);
    // Stop descending past the optional depth bound, but still finish the queue.
    if (maxDepth >= 0 && d >= maxDepth) continue;
    for (final int v in graph[u]) {
      if (!seen[v]) {
        seen[v] = true;
        queue.add((v, d + 1));
      }
    }
  }
}