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.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 Graph and a starting vertex root of GraphOutput: All vertices reachable from root labeled as explored.A non-recursive implementation of breadth-first search:This non-recursive implementation is similar to the non-recursive implementation of depth-first search, but differs from it in two ways:The distance attribute of each vertex (or node) is needed for example when searching for the shortest path between nodes in a graph. At the beginning of the algorithm, the distance of each vertex is set to INFINITY, which is just a word that represents the fact that a node has not been reached yet, and therefore it has no distance from the starting vertex. We could have used other symbols, such as -1, to represent this concept. https://en.wikipedia.org/wiki/Breadth-first_sear...

Tags
graph traversal, pathfinding

Implementations