See On Github

Wikipedia Description

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, sometimes referred to as a `search key' ) and explores the neighbor nodes first, before moving to the next level neighbors. Compare BFS with the equivalent, but more memory-efficient Iterative deepening depth-first search and contrast with depth-first search . BFS was invented in the late 1950s by E. F. Moore, who used it to find the shortest path out of a maze, and discovered independently by C. Y. Lee as a wire routing algorithm (published 1961). Input : A graph G and a vertex v of G Output : All vertices reachable from v labeled as discovered A non-recursive implementation of BFS: The non-recursive implementation is similar to depth-first search but differs from it in two ways: it uses a queue instead of a stack, and it checks whether a vertex has been discovered before enqueueing the vertex rather than delaying this check until the vertex is dequeued from the queue. The function process is called on all nodes, and will have seen all nodes reachable by a length- n path from v before any of the nodes that are only reachable by a length- ( n + 1) path. https://en.wikipedia.org/wiki/Breadth-first_sear...

Tags
graph traversal, pathfinding

Implementations