bfs function

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

BFS from start; calls visit(node, depth) for each node. maxDepth caps depth (-1 = no limit).

Implementation

void bfs(
  Adjacency graph,
  int start,
  void Function(int node, int depth) visit, {
  int maxDepth = -1,
}) {
  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);
    if (maxDepth >= 0 && d >= maxDepth) continue;
    for (final int v in graph[u]) {
      if (!seen[v]) {
        seen[v] = true;
        queue.add((v, d + 1));
      }
    }
  }
}