Breadth-first search

Imagine you are looking for a hidden treasure in a giant maze. Instead of running down one long path to see where it goes, you decide to look at every path right next to you first. You check every nearby turn before you move any further away. This way of searching is called a breadth-first search. It is a special way to explore a structure called a tree or a graph.

In these structures, points are called nodes or vertices. A breadth-first search is very helpful because it is guaranteed to find a goal if one exists. It will not get lost in paths that never end like some other search methods might.

To work correctly, this method follows a specific set of steps. It starts at a single starting node, often called the root. The search looks at all the nodes at the current depth before moving to the next level. To remember where it has been, it uses extra memory called a queue. A queue works just like a line of people waiting for a snack. The first node the search finds is the first one it explores.

As it finds new nodes, it adds them to the end of the queue. This keeps the search organized and steady.

People have been working on these ideas for a long time. Konrad Zuse first invented this method in 1945. He wrote about it in a paper about a programming language called Plankalkül. Even though he wrote it then, it was not published until 1972. Later, in 1959, Edward F. Moore reinvented the idea. He used it to find the shortest path out of a maze.

Another person named C. Y. Lee developed it further in 1961. He used it to help find paths for wires.

There are many important facts about how this search behaves. It can be used on both directed and undirected graphs. A directed graph is like a one-way street where you can only go in one direction. The search is very good at finding the shortest path between two points. This is because it explores everything level by level.

If you use a different tool called a stack instead of a queue, you get a different kind of search. That other search is called a depth-first search. Depth-first search explores one branch as far as it can go before turning back.

You can see this math in action in many parts of our world. Computer engines use it to find winning moves in games like chess. It can also help computers find the best way to connect cities on a map. Even the way computers clean up memory uses these kinds of steps. It helps machines solve hard jobs by looking at many small options at once. By checking everything close by first, the search stays on the right track. It turns a huge, confusing problem into a simple series of steps.