Depth-first search

Imagine you are in a maze.

You pick one path. You walk as far as you can.

If you hit a wall, you turn back. You go back to where you could have turned. This is called backtracking.

This way of searching helps you find your way. A man named Charles Trémaux used this idea. He used it to solve mazes.

Computers can use this too. They use it to look through big groups of things. It is a very smart way to explore.

Imagine you are exploring a deep cave. You pick one tunnel and walk as far as you can.

If you hit a dead end, you turn back. You go back to the last place where you had a choice. This way of searching is called depth-first search. It is a set of steps used to explore shapes called graphs. A graph is a group of points connected by lines.

To keep track of where it has been, the search uses a stack. A stack is a way to store items in a pile. This helps the search know how to backtrack. In the 1800s, a man named Charles Pierre Trémaux studied this. He used it as a way to solve mazes.

Computers use this to look through many things. They might use it to search the web. Sometimes, the web is too big to see all at once. In those cases, the search only goes to a certain depth. This means it only goes so far into a branch before stopping. This saves memory and space.

Scientists also use this to study how living things are related. It helps them build trees that show how species change over time.

Imagine you are exploring a vast, branching cave system. You decide to pick one tunnel and walk as far as you can.

You do not stop to look at every side tunnel right away. Instead, you push forward until you hit a dead end. When that happens, you backtrack to the last place where you had a choice. This way of searching is called a depth-first search. It is a smart way to explore structures called graphs. A graph is a collection of points connected by lines.

To make this search work, the computer needs a special tool. It uses something called a stack to remember the path it has taken. A stack works like a pile of trays in a cafeteria. You add new points to the top and take them off from the top too. This helps the search know exactly how to backtrack when it hits a wall. If the search does not remember where it has been, it might get stuck. It could walk in a circle forever and never find the exit.

People have studied this idea for a very long time. In the 1800s, a French mathematician named Charles Pierre Trémaux looked at this method. He was a telegraph engineer who lived from 1859 to 1882. He used these steps as a strategy to solve tricky mazes.

His work helped people understand how to navigate paths. Today, we use his ideas to help computers solve many different puzzles.

Computers use this search for many important jobs. They might use it to crawl through the huge web. Sometimes the web is so big it is almost infinite. In those cases, the search only goes to a certain depth. This means it only goes so far down a branch before it stops. This helps the computer save memory and disk space.

It also helps scientists study how different species of living things are related. They use it to build trees that show how life changes.

When a search is finished, it leaves behind a special map. This map is called a spanning tree. This tree helps us group the lines of the graph into different types. Some lines are called forward edges because they point to a descendant. Other lines are called back edges because they point to an ancestor. There are also cross edges that do neither.

By looking at these edges, we can understand the shape of the whole graph.

Depth-first search, or DFS, is a fundamental algorithm used to explore or traverse data structures known as trees and graphs. A graph is a collection of points, called vertices, connected by lines, called edges. The core logic of DFS is to start at a specific point, often called the root, and travel as deep as possible along a single branch before turning back. This process of turning back is known as backtracking. By following this method, the algorithm can systematically visit the different parts of a complex network.

To manage this exploration, the algorithm requires extra memory to keep track of its progress. It typically uses a data structure called a stack. A stack follows a specific order where the last item added is the first one removed. This is essential for backtracking because it allows the algorithm to remember the exact path it took to reach a dead end. When the search reaches a point with no new directions, it pops the last location off the stack to return to a previous junction. Without this memory, a search might enter an infinite loop, circling the same points forever without ever reaching new areas.

There are different ways to implement this search depending on the needs of the computer. A recursive implementation uses a function that calls itself to move deeper into the graph. An iterative implementation, however, uses a manual stack to manage the vertices. These two methods can actually visit neighbors in different orders. For example, in a specific graph with nodes A, B, D, F, E, C, and G, a recursive search might visit them in one sequence, while an iterative search might follow a different path.

History shows that these ideas have been used for solving physical puzzles for a long time. In the 19th century, a French mathematician and telegraph engineer named Charles Pierre Trémaux investigated DFS. He lived from 1859 to 1882 and studied these methods as a strategy for solving mazes. His work helped define how one might navigate through complex, branching paths. Today, his legacy lives on in how we program computers to handle digital networks.

In theoretical computer science, the efficiency of DFS is measured by time and space complexity. The time it takes to complete a search is linear, meaning it depends on the number of vertices and edges in the graph. The space needed depends on how much information the computer must store. In some cases, such as web-crawling or artificial intelligence, the graph might be too large or even infinite. To prevent the computer from running out of memory or disk space, engineers often use a limited-depth search. This version only searches to a specific depth limit. This makes the space complexity proportional to that limit rather than the size of the entire graph.

When a DFS is finished, the paths it took form a structure called a spanning tree. This tree allows us to categorize the edges of the original graph into three distinct types. Forward edges point from a node to one of its descendants in the tree. Back edges point from a node back to one of its ancestors. Cross edges are those that do neither. If the original graph is undirected, all edges will be either tree edges or back edges.

DFS is also used to create specific orderings of vertices. A preordering lists vertices in the order they were first visited. A postordering lists them in the order they were last visited. These orderings are useful for organizing data, such as expression trees in Polish notation. In directed acyclic graphs, a reverse postordering can produce a topological sorting. This is a way of lining up tasks so that every dependency is respected.

Because of its versatility, DFS serves as a building block for many advanced tasks. It is used to find connected components and to identify bridges in a graph. Scientists also use it to determine how closely related different species are in a phylogenetic tree. It can even be used to test for planarity, which asks if a graph can be drawn without edges crossing. Whether it is solving a puzzle or mapping the web, DFS remains a vital tool in the world of mathematics and computing.