See On Github

Wikipedia Description

In computer science depth-limited search is an algorithm to explore the vertices of a graph. It is a modification of depth-first search and is used for example in the iterative deepening depth-first search algorithm. Like the normal depth-first search, depth-limited search is an uninformed search. It works exactly like depth-first search, but avoids its drawbacks regarding completeness by imposing a maximum limit on the depth of the search. Even if the search could still expand a vertex beyond that depth, it will not do so and thereby it will not follow infinitely deep paths or get stuck in cycles. Therefore depth-limited search will find a solution if it is within the depth limit, which guarantees at least completeness on all graphs. Since depth-limited search internally uses depth-first search, the space complexity is equivalent to that of normal depth-first search. Since depth-limited search internally uses depth-first-search, the time complexity is equivalent to that of normal depth-first search, and is O( ) where stands for the number of vertices and for the number of edges in the explored graph. Note that depth-limited search does not explore the entire graph, but just the part that lies within the specified bound. https://en.wikipedia.org/wiki/Depth-limited_sear...

Tags
graph traversal, pathfinding

Implementations