DepthFirstSearch<E> class
final
Pathfinding
Pathfinding algorithm that explores the graph in depth first order.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.
Depth-first search is often compared to breadth-first search (BFS). The
biggest difference between the two is that depth-first search can get
"trapped" exploring a suboptimal path, as it will always find the deepest
path first. However, it has a lower memory overhead than other algorithms
(O(bd) where b is the branching factor and d is the depth of the
solution) compared to BreadthFirstSearch.
A default singleton instance of this class is depthFirstSearch.
- Mixed-in types
-
- Pathfinder<
E>
- Pathfinder<
Constructors
- DepthFirstSearch.new()
-
Creates a new depth-first search algorithm.
const
Properties
- hashCode → int
-
The hash code for this object.
no setterinherited
- runtimeType → Type
-
A representation of the runtime type of the object.
no setterinherited
Methods
-
findPath<
T extends E> (WalkableBase< T> graph, T start, Goal<T> goal, {Tracer<T> ? tracer}) → Path<T> -
Returns a path in
graphfromstartto a node that satisfiesgoal.inherited -
findPathExclusive<
T extends E> (WalkableBase< T> graph, T start, Goal<T> goal, {Tracer<T> ? tracer}) → Path<T> -
Returns a path in
graphfromstartto a node that satisfiesgoal.override -
noSuchMethod(
Invocation invocation) → dynamic -
Invoked when a nonexistent method or property is accessed.
inherited
-
toString(
) → String -
A string representation of this object.
inherited
Operators
-
operator ==(
Object other) → bool -
The equality operator.
inherited