Breadth first search

Breadth-first search

A simple strategy in which the root node is expanded first, followed by its successors, and so on, expanding all nodes at a given depth before moving to the next level.

Graph-search algorithm

A general algorithm in which the shallowest unexpanded node is chosen for expansion. In breadth-first search, this is achieved by using a FIFO queue for the frontier.

Frontier

The set of nodes that have been generated but not yet expanded in the search algorithm. In breadth-first search, new nodes are added to the back of the queue.

Goal test

A test applied to each node when it is generated to determine if it is a goal state. In breadth-first search, the goal test is applied when a node is generated, not when it is selected for expansion.

Explored set

The set of nodes that have been expanded in the search algorithm. In breadth-first search, old nodes, which are shallower than new nodes, get expanded first.

Time complexity

The measure of the amount of time taken by an algorithm to run. In breadth-first search, the decision to apply the goal test when generating nodes affects the time complexity of the algorithm.

Shallowest path

The path that has the fewest number of edges or steps to reach a specific node. In breadth-first search, the algorithm always finds the shallowest path to every node on the frontier.