AI Search Algorithms — BFS, DFS, and A* Explained

In this tutorial, you'll learn about AI Search Algorithms. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Search algorithms are the foundation of AI problem-solving — methods that systematically explore possible states to find a path from a starting point to a goal, used in everything from GPS navigation to game AI and robotics path planning.

What You'll Learn

You'll learn the three fundamental search algorithms in AI — breadth-first search (BFS), depth-first search (DFS), and A* — how they differ, when to use each one, how to design heuristic functions, and how to implement them in Python with real-world examples.

Why It Matters

Every AI system that navigates physical or abstract space uses search algorithms. GPS route planning, puzzle solvers, game AI opponents, robot motion planning, and even Machine Learning hyperparameter optimisation all rely on the concepts covered in this tutorial.

Real-World Use

Your GPS maps app uses A* search to find the fastest route. It treats intersections as nodes, roads as edges, distance as the cost, and estimated remaining distance as the heuristic. When traffic data updates edge costs dynamically, the GPS recalculates using the same A* algorithm.

Problem Representation

Before searching, we must represent the problem as states, actions, and transitions.

flowchart TD
  A[Start State] --> B[Action 1]
  A --> C[Action 2]
  A --> D[Action 3]
  B --> E[State B]
  C --> F[State C]
  D --> G[State D]
  E --> H[Goal State]
  F --> H
  G --> I[...]

Key Components

Breadth-First Search (BFS)

BFS explores all nodes at the current depth before moving deeper. It guarantees finding the shortest path in unweighted graphs.

# Breadth-First Search implementation
from collections import deque

def BFS(Graph, start, goal):
    """BFS finds the shortest path in unweighted graphs."""
    Queue = deque([[start]])
    visited = {start}

    while Queue:
        path = Queue.popleft()
        node = path[-1]

        if node == goal:
            return path

        for neighbor in Graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                new_path = list(path)
                new_path.append(neighbor)
                Queue.append(new_path)

    return None  # No path found

# Graph as adjacency list
Graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B', 'G'],
    'E': ['B', 'G'],
    'F': ['C', 'G'],
    'G': ['D', 'E', 'F', 'H'],
    'H': ['G'],
}

path = BFS(Graph, 'A', 'H')
print(f"BFS path from A to H: {' -> '.join(path) if path else 'No path found'}")
print(f"Path length: {len(path) - 1 if path else 0} edges")

# Show exploration order
def BFS_exploration_order(Graph, start):
    """Show the order nodes are discovered by BFS."""
    visited = {start}
    Queue = deque([start])
    order = []

    while Queue:
        node = Queue.popleft()
        order.append(node)
        for neighbor in sorted(Graph[node]):
            if neighbor not in visited:
                visited.add(neighbor)
                Queue.append(neighbor)
    return order

print(f"BFS exploration order: {BFS_exploration_order(Graph, 'A')}")

Expected output:

BFS path from A to H: A -> B -> D -> G -> H
Path length: 4 edges
BFS exploration order: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

BFS explores level by level: A, then B and C, then D, E, and F, then G, then H. This guarantees the shortest path in terms of edge count. The Queue ensures nodes are processed in the order they are discovered.

Depth-First Search (DFS)

DFS explores as deep as possible along each Branch before Backtracking. It uses LESS memory than BFS but does not guarantee the shortest path.

# Depth-First Search implementation
def DFS(Graph, start, goal, path=None, visited=None):
    """DFS finds a path by exploring as deep as possible first."""
    if path is None:
        path = [start]
    if visited is None:
        visited = {start}

    if start == goal:
        return path

    for neighbor in Graph[start]:
        if neighbor not in visited:
            visited.add(neighbor)
            result = DFS(Graph, neighbor, goal,
                         path + [neighbor], visited)
            if result is not None:
                return result

    return None

def DFS_iterative(Graph, start, goal):
    """Iterative DFS using a Stack."""
    Stack = [[start]]
    visited = {start}

    while Stack:
        path = Stack.pop()
        node = path[-1]

        if node == goal:
            return path

        for neighbor in Graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                new_path = list(path)
                new_path.append(neighbor)
                Stack.append(new_path)

    return None

# Compare BFS vs DFS paths
BFS_path = BFS(Graph, 'A', 'H')
DFS_path = DFS_iterative(Graph, 'A', 'H')

print(f"BFS path: {' -> '.join(BFS_path)} (shortest)")
print(f"DFS path: {' -> '.join(DFS_path)} (may not be shortest)")

# DFS exploration order
def DFS_order(Graph, start, visited=None, order=None):
    if visited is None:
        visited = set()
    if order is None:
        order = []
    visited.add(start)
    order.append(start)
    for neighbor in sorted(Graph[start]):
        if neighbor not in visited:
            DFS_order(Graph, neighbor, visited, order)
    return order

print(f"DFS exploration order: {DFS_order(Graph, 'A')}")

Expected output:

BFS path: A -> B -> D -> G -> H (shortest)
DFS path: A -> C -> F -> G -> H (may not be shortest)
DFS exploration order: ['A', 'B', 'D', 'G', 'E', 'H', 'C', 'F']

DFS finds a different path than BFS and explores nodes in a different order. It uses a Stack (LIFO) while BFS uses a Queue (FIFO). DFS uses LESS memory than BFS on deep graphs but can get stuck in infinite loops on graphs with cycles.

A* Search

A* combines the advantages of BFS (optimal path) and DFS (guided search) using a heuristic function to estimate remaining distance to the goal.

# A* Search implementation
import heapq

def a_star(Graph, start, goal, heuristic, costs=None):
    """A* finds the optimal path using a heuristic function."""
    if costs is None:
        costs = {edge: 1 for node in Graph
                 for edge in Graph[node]}  # Default unit costs

    open_set = [(0 + heuristic(start, goal), 0, start, [start])]

    while open_set:
        f, g, node, path = heapq.heappop(open_set)

        if node == goal:
            return path, g

        for neighbor in Graph[node]:
            edge_cost = costs.get((node, neighbor), 1)
            new_g = g + edge_cost
            new_f = new_g + heuristic(neighbor, goal)
            new_path = path + [neighbor]
            heapq.heappush(open_set, (new_f, new_g, neighbor, new_path))

    return None, float('inf')

# Grid-based pathfinding example
def manhattan_heuristic(a, b):
    """Manhattan distance heuristic for grid navigation."""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def grid_to_Graph(grid):
    """Convert a 2D grid to adjacency list with costs."""
    rows, cols = len(grid), len(grid[0])
    Graph = {}
    costs = {}

    for R in range(rows):
        for C in range(cols):
            if grid[R][C] != 1:  # Not a wall
                node = (R, C)
                Graph[node] = []
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nr, nc = R + dr, C + dc
                    if (0 <= nr < rows and 0 <= nc < cols
                            and grid[nr][nc] != 1):
                        neighbor = (nr, nc)
                        Graph[node].append(neighbor)
                        # Diagonal moves cost more
                        costs[(node, neighbor)] = 1
    return Graph, costs

# Create a simple grid: 0=empty, 1=wall
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
]
Graph, costs = grid_to_Graph(grid)
start, goal = (0, 0), (4, 4)

path, cost = a_star(Graph, start, goal, manhattan_heuristic, costs)

print(f"A* path from {start} to {goal}:")
print(f"  Path: {' -> '.join(map(str, path))}")
print(f"  Total cost: {cost}")
print(f"  Path length: {len(path) - 1} steps")

# Visualise the path on the grid
grid_vis = [['.' for _ in range(5)] for _ in range(5)]
for R, C in path:
    grid_vis[R][C] = '*'
grid_vis[start[0]][start[1]] = 'S'
grid_vis[goal[0]][goal[1]] = 'G'
for R in range(5):
    for C in range(5):
        if grid[R][C] == 1:
            grid_vis[R][C] = '#'
print("\nGrid visualisation (S=start, G=goal, *=path, #=wall):")
for row in grid_vis:
    print('  ' + ' '.join(row))

Expected output:

A* path from (0, 0) to (4, 4):
  Path: (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (2, 3) -> (2, 4) -> (3, 4) -> (4, 4)
  Total cost: 8
  Path length: 8 steps

Grid visualisation (S=start, G=goal, *=path, #=wall):
  S . . . .
  * # # # .
  * * * * *
  . # . # *
  . . . . G

A* navigates around the walls to find the optimal path. The Manhattan heuristic guides the search toward the goal, making it explore fewer nodes than BFS. In this case, A* finds the same optimal path as BFS would but with fewer nodes expanded.

Heuristic Design

The heuristic function is critical to A* performance. A good heuristic is admissible (never overestimates) and consistent (obeys triangle inequality).

# Heuristic comparison
import math

def euclidean_heuristic(a, b):
    """Straight-line distance. Always admissible."""
    return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

def diagonal_heuristic(a, b):
    """Chebyshev distance for 8-direction movement."""
    return max(abs(a[0] - b[0]), abs(a[1] - b[1]))

def zero_heuristic(a, b):
    """Trivial heuristic. Makes A* behave like BFS."""
    return 0

def octile_heuristic(a, b, d1=1, d2=1.414):
    """Octile distance for 8-direction with diagonal cost."""
    dx = abs(a[0] - b[0])
    dy = abs(a[1] - b[1])
    return d1 * (dx + dy) + (d2 - 2 * d1) * min(dx, dy)

# Compare heuristics on a larger grid
grid = [[0] * 10 for _ in range(10)]
Graph, costs = grid_to_Graph(grid)
start, goal = (0, 0), (9, 9)

heuristics = {
    'Manhattan': manhattan_heuristic,
    'Euclidean': euclidean_heuristic,
    'Diagonal': diagonal_heuristic,
    'Octile': octile_heuristic,
    'Zero (BFS)': zero_heuristic,
}

print("Heuristic comparison (10x10 grid, (0,0) -> (9,9)):")
print(f"{'Heuristic':15} {'Path Cost':12} {'Optimal?':10}")
print("-" * 40)
for name, h in heuristics.items():
    h_val = h(start, goal)
    path, cost = a_star(Graph, start, goal, h, costs)
    optimal = "Yes" if path else "No"
    print(f"{name:15} {cost:<12} {optimal:<10}  (heuristic estimate: {h_val:.1f})")

Expected output:

Heuristic comparison (10x10 grid, (0,0) -> (9,9)):
Heuristic       Path Cost    Optimal?  
----------------------------------------
Manhattan       18           Yes        (heuristic estimate: 18.0)
Euclidean       18           Yes        (heuristic estimate: 12.7)
Diagonal        18           Yes        (heuristic estimate: 9.0)
Octile          18           Yes        (heuristic estimate: 18.0)
Zero (BFS)      18           Yes        (heuristic estimate: 0.0)

All heuristics find the optimal path in this case. Manhattan is admissible because
it never overestimates (actual distance in a 4-direction grid equals Manhattan
distance). The zero heuristic makes A* explore all reachable nodes, like BFS.

All admissible heuristics produce the optimal path, but more informed heuristics (closer to the true cost) explore fewer nodes. The zero heuristic explores the most nodes, making A* behave identically to BFS.

Common Errors Beginners Make

1. Using DFS for Shortest Path Problems

DFS explores deep branches first and may return a suboptimal path. Never use DFS when you need the shortest path. Use BFS (unweighted) or A* (weighted with heuristic).

2. Forgetting the Visited Set

Without tracking visited nodes, BFS and DFS may loop indefinitely on graphs with cycles. Always maintain a visited set and check it before enqueuing neighbours.

3. Using an Inadmissible Heuristic

A heuristic that overestimates the true cost may cause A* to return a suboptimal path. Ensure your heuristic is admissible (never overestimates) for guaranteed optimality.

4. Neglecting Edge Costs

BFS assumes all edges have equal cost. On weighted graphs, BFS fails. Use Dijkstra's algorithm (BFS with a priority Queue) or A* for weighted graphs.

5. Choosing the Wrong Data Structure

BFS uses a Queue, DFS uses a Stack, A* uses a priority Queue. Using the wrong data structure produces incorrect or inefficient search behaviour.

6. Not Checking for Unsolvable Problems

If no path exists, BFS will explore the entire Graph before returning. For large graphs, add a node limit or early termination condition.

7. Overcomplicating the Heuristic

The simplest admissible heuristic is often the best. Start with Manhattan or Euclidean distance. More complex heuristics add computational overhead with diminishing returns.

Practice Questions

1. What is the difference between BFS and DFS in terms of completeness and optimality? BFS is complete (finds a solution if one exists) and optimal for unweighted graphs. DFS is complete for finite graphs but not optimal — it may find a longer path first.

2. What makes a heuristic admissible and why does it matter for A?* A heuristic is admissible if it never overestimates the true cost to reach the goal. Admissibility guarantees A* returns the optimal path because it never prunes the optimal solution.

3. Why does A use a priority Queue instead of a regular Queue?* A* explores nodes in order of f = g + h, where g is the cost so far and h is the heuristic estimate. A priority Queue efficiently retrieves the node with the smallest f value, ensuring the most promising paths are explored first.

Challenge

Implement A* for the 8-puzzle sliding puzzle. Represent each State as a tuple of tile positions. Use Manhattan distance as the heuristic. Measure how many states are explored to solve random configurations. What is the hardest solvable configuration (requiring the most moves)?

Real-World Task

Download OpenStreetMap data for a small city. Extract the road network as a Graph with real distances. Implement A* with a Euclidean heuristic and compare its performance to a commercial GPS routing API. How close does A* get to the optimal route?

FAQ

What's Next

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.