Depth-first search
Depth-first search is a graph or tree traversal algorithm that explores one branch as far as possible before backtracking to explore alternatives.
Clojure: The Essential Reference
Depth-first traversal is a tree-traversal technique that visits a node and recursively explores its descendants before moving to other branches.
- How it is used
- Traverses nested collections and files to inspect nodes, transform data, or collect selected values.
- How deep it goes
- Defines visit order and works through lazy sequences, pre/post-order transformations, and optional zipper navigation.
- Examples
- Uses nested vectors, a document tree, filesystem paths, and an expression tree to make visit order and processing visible.
- What you can do after
- Apply it via tree-seq to enumerate nodes lazily or via clojure.zip to navigate and edit selected locations.
Read how Clojure: The Essential Reference explains depth-first search →
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
Depth-first search explores one path as deeply as possible before backtracking to an earlier decision point.
- How it is used
- Finds a route through a maze while providing a reusable search procedure for other state spaces.
- How deep it goes
- Builds DFS with a stack, explored set, goal test, successors, and parent-linked paths; does not develop a formal proof.
- Examples
- Uses a randomly generated grid maze, hashable row-and-column locations, and a printed path from start to goal.
- What you can do after
- Build it from scratch as a generic Swift search and apply it to a maze with supplied goal and successor functions.
Advanced Algorithms and Data Structures
Depth-first search is a graph traversal algorithm that explores a path as far as possible before backtracking to explore remaining branches.
- How it is used
- Uses graph traversal to inspect structure, visit vertices, and support algorithms such as topological sorting and strongly connected components.
- How deep it goes
- Explains recursive and stack-based traversal, visited checks, restarts, and entry or exit times, but stops short of shortest-path computation.
- Examples
- Demonstrates maze-like backtracking, graph starts at v1 or v4, disconnected components, and recursive traversal pseudocode.
- What you can do after
- Apply it to traverse graphs recursively or with an explicit stack, restart across components, and record vertex processing times.
Read how Advanced Algorithms and Data Structures explains depth-first search →
Grokking AI Algorithms, Second Edition
Depth-first search is a graph or tree traversal algorithm that explores a path as deeply as possible before backtracking to explore alternatives.
- How it is used
- Uses stack-driven traversal to explore trees, mazes, web structures, and social connections deeply before backtracking.
- How deep it goes
- Explains DFS through ordered steps, maze traces, parent links, cycle constraints, and a Python implementation.
- Examples
- Demonstrates maze movement, tree processing, web crawling, social-network connections, and actor paths.
- What you can do after
- Build it from scratch using a stack, visited tracking, neighbor expansion, and parent references for path reconstruction.
Read how Grokking AI Algorithms, Second Edition explains depth-first search →
Optimization Algorithms: AI techniques for design, planning, and control problems
Depth-first search explores a path as deeply as possible before backtracking to an alternative path.
- How it is used
- Uses blind graph traversal to find a route by exploring branches deeply before trying alternatives.
- How deep it goes
- Explains recursive backtracking, LIFO implementation, depth bounds, trade-offs, and a complete 8-puzzle procedure.
- Examples
- Demonstrates DFS on an 8-puzzle and contrasts its behavior with BFS through complexity and preference conditions.
- What you can do after
- Apply it via a stack-based implementation to search graphs and solve state-space problems while tracking routes and explored states.
Grokking Data Structures
Depth-first search is a graph traversal algorithm that explores a path as deeply as possible before backtracking.
- How it is used
- Uses graph traversal to follow paths deeply and check structural properties such as cycles and connected components.
- How deep it goes
- Explains stack-based traversal, backtracking, vertex colors, and cycle detection, but defers other major applications.
- Examples
- Demonstrates white, gray, and black vertex states and an iterative stack implementation that inspects outgoing edges.
- What you can do after
- Build it from scratch by using a stack, vertex colors, and outgoing-edge traversal to detect cycles.
Read how Grokking Data Structures explains depth-first search →
Build a Frontend Web Framework (From Scratch)
A tree traversal technique that visits a node and recursively processes its descendants before moving to the next branch.
- How it is used
- Guides virtual-DOM reconciliation and DOM patching by ordering comparisons and modifications branch by branch.
- How deep it goes
- Explains recursive traversal and ordered updates through concrete tree differences, stopping short of a complete traversal implementation.
- Examples
- Uses changed attributes, text, classes, node types, sibling positions, and an inserted validation message.
- What you can do after
- Apply it via virtual-DOM reconciliation to compare branches and apply DOM changes in traversal order.
Read how Build a Frontend Web Framework (From Scratch) explains depth-first search →
Related concepts
- breadth-first searchcontrasts with · Breadth-first search is a graph or tree traversal algorithm that explores nodes in nondecreasing order of their distance from a starting node.
- stackuses · A stack is a data structure that adds and removes elements at one end, following last-in, first-out order.
- recursionimplemented by · Recursion is a computational technique in which a definition or procedure refers to or invokes the same definition or procedure, directly or indirectly.
- backtrackinguses · Backtracking is a technique that returns to earlier decisions or states along a path to reconsider choices, explore alternatives, or reconstruct a solution.
- cycleaddresses · A cycle is a recurring sequence of connected elements or events that returns to an earlier point, forming a loop.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.