depthFirst<T> function Graphs

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

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

Depth-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 as far as possible along each branch before backtracking.

A depth-first traversal is typically used for:

  • Wander deep into the graph before exploring closer nodes;
  • In cases where deep branches or cycles are less likely to be found;

Depth-first traversals typically have lower memory overhead than other algorithms (O(d), where d is the depth of the deepest node); consider using breadthFirst when a shallower traversal is needed.

Example

final graph = Graph<int>();

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

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

Implementation

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