Search Algorithms: BFS, DFS, A* and Minimax For students.

Search algorithms explore possible options step by step to find a goal. Most computer science problems — shortest routes, puzzles, chess moves — can be drawn as a graph: nodes are states and edges are moves. A search algorithm starts at the start node and visits nodes systematically until it reaches the goal.

Smart search matters because brute force explodes: a chess position has about 35 legal moves, so looking 4 moves ahead means roughly 35 to the power 4, about 1.5 million positions. BFS, DFS, A*, and minimax prune, order, and guide exploration so computers solve problems far too large to check by hand.

Key Concepts

• Node and edge: a node is one state of the problem; an edge is one action connecting two states.
• Frontier: nodes discovered but not yet explored; the algorithm always picks its next node here.
• Visited set: already-explored nodes; stops the search looping forever.
• Branching factor (b): the average number of moves available from each node.
• Heuristic h(n): an educated guess of the remaining cost from node n to the goal; guides A*.
• Game tree: all possible moves in a two-player game, with scores at the leaves; minimax searches it.

Formulas

• BFS complexity: time O(b^d) and space O(b^d), where d is the depth of the shallowest goal. Finds the shortest path in unweighted graphs but uses huge memory.
• DFS complexity: time O(b^m) and space O(b times m), where m is the maximum depth explored. Tiny memory, but it may dive down a wrong path and misses shortest paths.
• A* evaluation: f(n) = g(n) + h(n), where g(n) is the exact cost from the start and h(n) the heuristic estimate to the goal. Expands the smallest f first; optimal only if h(n) never overestimates (admissible) and edge costs are non-negative.

Worked Example

Consider a tiny game tree: the root is a MAX node (our turn) with two MIN-node children (opponent's turn). The left MIN node has leaf scores 3 and 5; the right MIN node has 2 and 9. The opponent minimizes: left evaluates to min(3, 5) = 3, right to min(2, 9) = 2. Then we maximize at the root: max(3, 2) = 3. The game value is 3, so our best first move goes left. Total work: 2 comparisons at the MIN level plus 1 at the root = 3 comparisons. Traversal orders are easy to see on a small tree too: with root A, children B and C, B's children D and E, and C's child F, breadth-first order is A, B, C, D, E, F (level by level), while left-first depth-first order is A, B, D, E, C, F.

Common Misconceptions

• DFS finds the shortest path. It finds a path, often a long one; BFS (unweighted graphs) or A* (admissible heuristic) guarantee the shortest.
• A* is always optimal. Only with an admissible heuristic; an overestimating h(n) can skip the true best path.
• Minimax works directly on any game. Real game trees are astronomically large; engines add alpha-beta pruning and depth limits.

Real-World Applications

• Navigation: A* variants find driving routes through road networks.
• Web crawlers: search engines crawl breadth-first from seed URLs.
• Puzzles: DFS backtracking solves mazes and Sudoku.
• Games: chess engines choose moves with minimax plus alpha-beta pruning.

BFS explores level by level, DFS dives deep on little memory, A* steers with a heuristic, and minimax optimizes against an opponent. Know their costs and guarantees, and you can match the right search to any problem.