Breadth-first search Review

2 0

Review of Breadth-first search powered by the Slant community.

Ranked in these QuestionsQuestion Ranking

What are the best 2D pathfinding algorithms?

Pros

Pro
Complete

BFS is complete, which means that it will always find a solution if it exists.

Pro
Optimal for finding the shortest path in a graph

BFS is very useful when you want to find the shortest and most optimal path by traversing as few edges as possible.

Cons

Con
Requires a large amount of memory

When traversing one tree level, you need a way to know which nodes to traverse once you get to the next one. The way this is done is by storing the pointers to a level's child nodes while searching it. The pointers are stored in a FIFO way, this means that BFS needs a relatively large amount of memory in order to store the pointers. The amount of course depends on the complexity of the graph tree and the amount of nodes and/or levels.