Breadth-first search

From YoYoGames Wiki

Breadth-first search or BFS is a search algorithm which searches each node of a graph until the endpoint is reached without using a heuristic.

Algorithm

1. Create a first-in-first-out (FIFO) queue and place the start node in the queue.
2. If the queue is not empty, dequeue a node and examine it.
   • If the node is the searched node, return a result.
   • Otherwise, push its unexamined immediate-children onto the end of the queue if any exist.
3. Return to step 2

Time complexity

In the worst case scenario a BFS must check every node and every edge before reaching the final destination. This means that the run-time of a BFS is directly dependent on the number of nodes and edges and thus the algorithm has an order of O(|E|+|V|) time complexity. This is not optimal in most cases.