I am trying to implement the implementation of Breadth First Search (also other algorithms, but currently bfs) in Javascript.
In the end, I want to apply all the search algorithms in the grid to find the path from the beginning to the node target (I know bfs is not particularly good at this). I made an implementation, but the problem is that I do not have the whole tree in advance. What I want is to give it initial and final values and based on this find a way between them.
The problem I am facing is that when I define the neighboring squares of the grid, it returns ALL neighbors, so even those that are already passed. This makes it a graph search, not a tree search. The way to solve this is to remember all the paths so that I can check which neighbors have already been passed and, therefore, they do not need to be checked further. However, as I learned in the course on search algorithms, bfs uses the memory of all nodes at the current depth level. If I store all the paths, then it consumes much more memory than is this correct?
Is it possible to store only nodes of the current depth that bfs is looking for when I do not have a tree structure in advance and still avoid loops?
I hope I made my clear.
Thanks in advance, Stefan
source
share