Depth-first search

 Depth-first search (DFS) is an uninformed search strategy used to explore a graph or tree data structure. It starts at a root node and explores as far as possible along each branch before backtracking. In other words, it goes deep first before exploring wider.

DFS uses a stack data structure to keep track of the nodes to be visited. It starts by adding the initial node to the stack. Then it pops the top node from the stack and visits it. If the node is the goal state, the search is complete. Otherwise, it checks if the node has any unexplored children, and if so, it adds them to the stack. The algorithm repeats this process until the goal state is found or the stack is empty.

DFS has the advantage of requiring less memory compared to other search algorithms like breadth-first search (BFS) as it only needs to store the path from the root node to the current node being explored. However, it is not guaranteed to find the optimal solution since it does not consider the cost of each path. Moreover, DFS can get stuck in an infinite loop if there are cycles in the graph.

There are several variations of DFS, such as iterative deepening depth-first search (IDDFS), which gradually increases the maximum depth limit until the goal state is found. Another variation is recursive depth-first search, which uses recursive function calls to explore the nodes.

DFS is commonly used in applications such as maze-solving, finding connected components in a graph, and generating permutations and combinations. It is also used as a building block for more complex algorithms like minimax search and backtracking.