A graph traversal algorithm that explores as far as possible along each branch before backtracking.
Depth-First Search (DFS) is another fundamental graph traversal algorithm, but it explores the graph in a different manner than BFS. Instead of exploring layer by layer, DFS goes as deep as possible down one path before backtracking. It starts at a source vertex, explores one of its neighbors, then explores one of that neighbor's neighbors, and so on, until it reaches a node with no unvisited neighbors. At that point, it backtracks to the previous node and explores another of its unvisited neighbors. This process continues until all reachable nodes have been visited. DFS is typically implemented recursively, which naturally handles the backtracking process. Alternatively, it can be implemented iteratively using a stack. The properties of DFS make it well-suited for a different set of problems than BFS. It is commonly used for cycle detection in graphs, finding connected components, topological sorting of a directed acyclic graph (DAG), and solving puzzles like mazes. The time complexity of DFS is also O(V + E), as it visits each vertex and edge once. The choice between DFS and BFS depends entirely on the problem you are trying to solve and the structure of the graph.