Breadth-first search

Imagine you want to find a prize in a maze.

You do not run down one path. Instead, you look at every path near you first. Then, you look at the next paths. This helps you find the shortest way out.

This way of searching is called breadth-first search. It uses a list to remember where to go next. This method is very smart. It will always find the prize if it is there. It is a great way to solve puzzles.

Imagine you are searching for a prize in a maze.

You do not run down just one path. Instead, you look at every path near you first. Then, you look at the next paths. This way of searching is called breadth-first search. It is a type of algorithm, which is a set of steps to solve a problem.

This method is very smart. It explores all nodes at the current depth first. A node is a point in a map or a tree. This search is guaranteed to find a goal if it exists. Some other searches can get lost in paths that never end.

Breadth-first search will not get lost.

To work, it needs extra memory. It uses a queue to keep track of nodes. A queue is a list of things to do. It works like a line at a store. The first node found is the first one checked.

Konrad Zuse invented this in 1945. Later, Edward F. Moore used it to find the shortest path out of a maze. It can even help find paths between cities on a map.

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.

Breadth-first search, often called BFS, is a fundamental algorithm used to explore data structures. It is specifically designed to search through trees or graphs to find a node that meets a specific property. A tree or graph is a collection of points, called nodes or vertices, connected by lines. In a tree, there is a starting point known as the root. BFS is highly valued because it is a complete algorithm. This means if a solution exists, BFS is guaranteed to find it. This completeness is vital when dealing with implicit trees that may be infinite in size.

The mechanism of BFS relies on exploring a structure level by level. It begins at the root node and examines all nodes at the current depth before moving deeper. To manage this process, the algorithm requires extra memory, typically in the form of a queue. A queue is a data structure that follows a first-in, first-out principle. The algorithm starts by labeling the root as explored and adding it to the queue. While the queue is not empty, the algorithm removes the first node and checks if it is the goal. If it is not the goal, the algorithm looks at all adjacent edges to find neighboring nodes. Any neighbor that has not been explored is labeled, assigned a parent link, and added to the queue.

There are different ways to traverse these structures, which define different types of searches. BFS is distinct from depth-first search, or DFS. While BFS explores all neighbors at one level before moving down, DFS explores a single branch as far as possible before backtracking. Because of this, DFS can sometimes get lost in an infinite branch and never find a solution. To solve this, researchers use iterative deepening depth-first search. This method avoids getting lost but must explore the top parts of the tree many times over. Additionally, BFS and DFS differ in their memory needs. While BFS requires more memory to maintain its queue, DFS typically requires much less extra memory.

The history of BFS involves several key figures and rediscoveries. Konrad Zuse is credited with inventing BFS and its application to finding connected components in 1945. He described these ideas in his Ph.D. thesis regarding the Plankalkül programming language. However, his work was not published until 1972. The algorithm was later reinvented in 1959 by Edward F. Moore. Moore applied the method to the specific problem of finding the shortest path out of a maze. In 1961, C. Y. Lee further developed the concept into a wire routing algorithm.

Mathematical analysis allows us to understand the efficiency of BFS through complexity. The time complexity is expressed as O(V + E), where V is the number of vertices and E is the number of edges. This represents the worst-case scenario where every vertex and edge must be explored. The space complexity is O(V), as the algorithm must store vertices in its queue. When dealing with very large or infinite graphs, we use the branching factor, denoted as b. In these cases, the time and memory required to find a node at distance d are expressed in terms of b and d.

BFS has many practical applications in computer science and mathematics. In artificial intelligence, chess engines use BFS to build game trees from a current position. This helps the engine identify winning positions for a player by exploring possible moves. BFS is also used for finding the shortest path between two nodes in a graph, where the path length is measured by the number of edges. Other uses include Cheney's algorithm for copying garbage collection and the Ford-Fulkerson method for computing maximum flow in networks. It can even be used to test if a graph is bipartite.

Ultimately, BFS connects to broader fields like graph theory and state space search. It can be generalized to work on both undirected and directed graphs. In directed graphs, edges act like one-way streets, but BFS still functions effectively from a starting search key. The algorithm also produces a breadth-first tree, which organizes the graph based on the order of discovery. By using parent links, the algorithm allows users to backtrack from a destination node to the starting node. This tracing provides the exact shortest path between the two points.