BFS uses two lists in order to record the path. These are namely OPEN list and CLOSED list for implementation purpose.

OPEN list stores nodes that have been generated, but have not examined. This is organized as a priority queue, in which nodes are stored with increasing order of their heuristics value, assuming we are implementing maximization heuristic. It provides efficient selection of the current best candidate for extension.

CLOSED list stores nodes that have already been examined. Whenever a new node is generated, check whether it has been generated before. If it is already visited before, check its recorded value and change the parent if this new value is better than previous one.

Algorithm: BFS (version 1)

1. OPEN = {initial state}.

2. Loop until a goal is found or there are no nodes left in OPEN:

a. Pick the best node in OPEN.

b. Generate its successors.

c. For each successor:

i. If its new successor evaluate it, add it to OPEN, and record its parent.

ii. If the node is generated before change parent, update successors.

1. This version of the algorithm is not complete, as it doesn’t always find a possible path to a goal node, even if there is one. For example, it gets stuck in a loop if it arrives at a dead end that is a node with the only successor being its parent.

The following version improves the algorithm by using an additional list named as CLOSED list. This CLOSED list contains all nodes that have been evaluated and will not be looked at again. This will avoid any node being evaluated twice, and will never get suck into an infinite loop.

Algorithm: BFS (version 2)

OPEN = initial state]

CLOSED = []

While OPEN is not empty

Do

1. Remove the best node from OPEN, call it n, and add it to CLOSED.

2. If n is the goal state, backtrack path to n through recorded parents and return path.

3. Create n's successor.

4. For each successor do:

a. If it is not CLOSED and it is not OPEN: evaluate it, add it to OPEN, and record

Its parent.

b. Otherwise, if it is already present in OPEN with different parent node and this new path is better than previous one, change its recorded parent.

i. If it is not in OPEN add it to OPEN.

ii. Otherwise, adjust its priority in OPEN using this new evaluation.

Both these version terminates when no path is found.

Diagram: