Search Algorithms in AI: BFS, DFS, A* and How They Work

Breadth-First Search (BFS): Explore Level by Level

What it does: BFS explores the state space layer by layer—first all states one step from start, then all states two steps away, and so on. It uses a queue (FIFO) to manage the frontier of nodes to explore [citation:1].

How it works: Start with the initial state in the queue. While the queue isn’t empty, remove the front node. If it’s the goal, you’re done. Otherwise, add all its unvisited neighbors to the back of the queue and continue [citation:3].

from collections import deque

def bfs(start, is_goal, get_neighbors):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        current = queue.popleft()
        if is_goal(current):
            return current  # Solution found
        
        for neighbor in get_neighbors(current):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return None  # No solution

When BFS shines:

• Finding the shortest path in an unweighted graph (e.g., minimum number of moves in a puzzle) [citation:5]
• Web crawling (visiting pages level by level)
• Social network analysis (“degrees of separation”)
• Any problem where all actions have equal cost

The tradeoff: BFS guarantees the shortest path in terms of number of steps, but it consumes significant memory—O(b^d) where b is the branching factor and d is the solution depth. For a problem with 10 possible moves per state and a solution 8 steps deep, BFS might store millions of nodes [citation:5].

Real-world example: In the 8-puzzle problem, BFS systematically explores all configurations one move away, then two moves away, eventually finding the optimal 25-move solution after examining 145,605 states [citation:1].

Depth-First Search (DFS): Go Deep Before Wide

What it does: DFS plunges as far down a single path as possible before backtracking. It uses a stack (LIFO)—either explicitly or through recursion—to track the current exploration path [citation:1].

How it works: Start at the initial state. Pick one neighbor and recursively explore everything reachable from there before considering any other neighbors. When you hit a dead end, backtrack to the most recent unexplored branch [citation:5].

def dfs(node, is_goal, get_neighbors, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    if is_goal(node):
        return node  # Solution found
    
    for neighbor in get_neighbors(node):
        if neighbor not in visited:
            result = dfs(neighbor, is_goal, get_neighbors, visited)
            if result:
                return result
    return None  # No solution in this branch

When DFS shines:

• Memory-constrained environments (DFS only stores the current path, O(bm) space vs BFS’s O(b^d)) [citation:5]
• Problems where any solution is acceptable, not necessarily the shortest
• Topological sorting, cycle detection, and maze generation
• Puzzle solving where the state space is deep but solutions exist at various depths

The tradeoff: DFS can get lost in infinite branches if the state space is unbounded. Even in finite spaces, it may find a long, meandering solution while missing a much shorter one. In the 8-puzzle, DFS once found a 1,157-move “solution” when an optimal 25-move path existed [citation:1].

Critical note: DFS is only complete if the state space is finite and you avoid revisiting states. Without cycle detection, DFS can loop forever [citation:5].

A* Search: The Best of Both Worlds

What it does: A* combines the systematic exploration of BFS with heuristic guidance about which direction leads to the goal. It evaluates nodes using f(n) = g(n) + h(n), where g(n) is the cost from start to current node, and h(n) is an estimate of the cost from current node to goal [citation:3].

How it works: Maintain a priority queue ordered by f(n). At each step, expand the node with the lowest f-value. This balances two competing desires: exploring promising paths (low h) while not abandoning efficient paths (low g) [citation:8].

import heapq

def a_star(start, is_goal, get_neighbors, cost_func, heuristic):
    # Priority queue stores (f_score, counter, node) to break ties
    counter = 0
    open_set = [(0, counter, start)]
    heapq.heapify(open_set)
    
    g_score = {start: 0}
    visited = set()
    
    while open_set:
        f, _, current = heapq.heappop(open_set)
        if current in visited:
            continue
            
        visited.add(current)
        if is_goal(current):
            return current
            
        for neighbor in get_neighbors(current):
            tentative_g = g_score[current] + cost_func(current, neighbor)
            if neighbor not in g_score or tentative_g < g_score[neighbor]:
                g_score[neighbor] = tentative_g
                f_score = tentative_g + heuristic(neighbor)
                counter += 1
                heapq.heappush(open_set, (f_score, counter, neighbor))
    return None

The magic is in the heuristic: The heuristic function h(n) estimates the remaining cost. For A* to be optimal, the heuristic must be admissible—it must never overestimate the true cost. For grid-based pathfinding, Manhattan distance (|x1-x2| + |y1-y2|) is a classic admissible heuristic [citation:7].

When A* dominates:

• GPS and navigation systems (finding shortest driving routes)
• Video game AI (pathfinding for characters avoiding obstacles) [citation:9]
• Robotics (autonomous navigation on 2D grids) [citation:3]
• Puzzle solving where optimal solutions matter
• Any problem where you can define a reasonable heuristic

Why it's the gold standard: A* expands significantly fewer nodes than BFS while still guaranteeing optimal solutions. In the 8-puzzle with Manhattan distance heuristic, A* expands only a fraction of the nodes BFS does to find the same optimal 25-move solution [citation:7].