BreadthFirstSearch<E> class
final
Pathfinding
Pathfinding algorithm that search the shallowest nodes in a graph first.
Breadth-first search (BFS) 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), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Breadth-first search's main use case compared to other unweighted algorithms
is that it never gets "trapped" exploring a suboptimal path, as it will
always find the shortest path first. However, it has a higher memory
overhead than other algorithms (O(b^d) where b is the branching factor
and d is the depth of the solution) compared to DepthFirstSearch.
A default singleton instance of this class is breadthFirstSearch.
- Mixed in types
-
- Pathfinder<
E>
- Pathfinder<
Constructors
- BreadthFirstSearch()
-
Creates a new breadth-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