Completeness, Optimality, and Time and Space Complexity of BFS

1. Introduction

There are some basic search algorithms. Breadth-first search (BFS) is one of them and  very simple. I note its the completeness, optimality, and time and space complexity :)

The photo is a nostalgic Japanese toy store :)

2. Algorithm

BFS does a series of processes per depth. The processes are to find child nodes and visit them. When a node is visited, the child nodes of it are found. These child nodes are often inserted into a FIFO queue. And also, when the child node is visited, it is removed from the queue.

When we assume there are a tree like this figure and we want to find 'Cake', a series of processes are as follows.

1. When node1 is visited, node2 and node3 are found and enqueued.
2. After that, node2 is visited and dequeued. And also, node4 and node5 are found and enqueued.
3. After that, node3 is visited and dequeued. And also, node6 is found and enqueued.
4. After that, node4 is visited and dequeued.
5. After that, node5 is visited and dequeued. Node5 has 'Cake' and is a goal node, so the search task is completed :)

3. Characteristic

3.1. Completeness and Optimality

BFS is complete and optimal, beacuse it has capacity to visit all nodes and find the shallowest path. So, BFS is a good algorithm in the lights of its completeness and optimality.

3.2. Time and Space Complexity

But, in terms of its time and space complexity, BFS is not good algorithm. It is because both of them exponentially increases in association with the increase of the depth of a goal node and balancing factor.

If we define as follows, the time and space complexcity are O(b^x).

depth of a goal node: x
branching factor: b