breadthFirst<T> function Graphs

Iterable<T> breadthFirst<T>(
  1. WalkableBase<T> graph, {
  2. required T start,
  3. Tracer<T>? tracer,
})

Visits nodes in a graph structure, shallowest nodes first, from start.

Breadth-first traversal is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, i.e., the start node), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

A breath-first traversal is typically used for:

  • Analyze the levels of connectedness between nodes;
  • Visit all reachable nodes in a connected component;
  • Early termination of search when the goal is close to the start node.

Breadth-first traversals typically have higher memory overhead than other algorithms (O(b^d), where b is the branching factor and d is the depth of the shallowest goal); consider using depthFirst for memory-constrained environments.

Example

final graph = Graph<int>();

graph.addEdge(Edge(1, 2));
graph.addEdge(Edge(2, 3));

final reachable = breadthFirst(graph, start: 1);
print(reachable); // (1, 2, 3)

Implementation

Iterable<T> breadthFirst<T>(
  WalkableBase<T> graph, {
  required T start,
  Tracer<T>? tracer,
}) {
  return _BfsReachable(graph.asUnweighted(), tracer, start);
}