Search Algorithms in AI: From BFS and DFS to A*

When we started covering search algorithms in my Intro to AI class at USF, my first instinct was to treat Breadth-First Search (BFS), Depth-First Search (DFS), Uniform Cost Search (UCS), Greedy Best-First Search, and A* as five completely separate things to memorize.

It took me a couple of lectures to realize that they are all doing the exact same job. Every single one of them keeps a list of discovered states (the frontier) and repeatedly picks one state to expand next. The only fundamental difference between them is how they answer one question: “Out of all the states on my frontier right now, which one do I open next?”

I put together this post from my first two days of class notes, along with an interactive visualizer below that runs all five algorithms directly in the page so you can watch them step-by-step and compare their results side by side.

Interactive Search Algorithm Visualizer & Live Comparison

Pick any algorithm below and press Play or Step to watch it traverse the graph from S (Start) to G (Goal), or click Compare All 5 (or any row in the live results table) to see how their visited order, number of nodes expanded, and final path cost compare on the exact same graph.

Part 1: Setting Up the Search Problem

Before we can run any algorithm, we have to translate a real-world problem into something a program can actually search through. In AI, an agent that looks ahead at the consequences of its actions before moving is called a planning agent (as opposed to a reflex agent that just reacts to whatever is right in front of it).

Think about opening Google Maps at USF to drive to downtown Tampa:

• Start state: Your current parking lot at USF.
• Actions: The roads and turns available from where you are.
• Successor function: A rule that says, “If you are at state X and take action Y, you end up at state Z.”
• Action cost: Time, distance, or tolls on each road segment.
• Goal test: A check that asks, “Am I at my destination yet?”
• Solution: The full sequence of roads from start to goal (not just the final destination, but the path that gets you there).

Why Abstraction Matters: World State vs. Search State

One concept from lecture that really stuck with me is abstraction. A real-world state includes everything: what song is playing on your car stereo, the color of your shirt, the exact temperature outside. If you included all of that in your search state, your state space would be practically infinite.

A search state strips away everything except what affects reaching the goal. In a classic two-room vacuum cleaner problem, the search state only needs three pieces of information:

1. Is the vacuum in the Left room or Right room?
2. Is the Left room clean or dirty?
3. Is the Right room clean or dirty?

That gives just 2 × 2 × 2 = 8 total states in the entire state space. Good AI modeling is mostly about keeping the details that matter for planning and throwing away the rest.

State-Space Graph vs. Search Tree

This was another distinction that tripped me up at first:

• In a state-space graph, every unique state appears exactly once. If there are 8 possible configurations in the vacuum world, the graph has 8 nodes.
• In a search tree, we trace out paths from the start state. Because you can often reach the same state via multiple routes (or loop back and forth between two rooms), the same state can appear many times as different nodes in the search tree.

State-Space Graph:          Search Tree:
        A                         A
       / \                       / \
      B   C                     B   C
       \ /                      |   |
        D                       D   D   <-- State D appears twice!

If we don’t keep track of states we’ve already visited (using a closed set or visited set), a tiny finite graph can produce an infinite search tree if it contains a cycle.

Part 2: Uninformed Search (Blind Search)

We call the first family of algorithms uninformed search because they have no sense of direction. They know the map of roads as they discover them, and they can recognize the goal if they land on it, but they have no idea whether a step is taking them closer to the goal or straight away from it.

1. Depth-First Search (DFS): Dive All the Way Down

DFS always expands the deepest node on the frontier first. It uses a Stack (LIFO: Last In, First Out).

If you pick DFS in the visualizer above, you’ll see it go S -> A -> C, hit a dead end at C, backtrack to D, and explore the entire left side before looking at B.

• Why use it? It is remarkably light on memory. It only needs to store the current path and the unvisited siblings along that path, which takes O(b * m) space (where b is the branching factor and m is the maximum depth).
• The catch: DFS is not optimal (it will happily return a long, winding path if it stumbles onto the goal deep in its first branch) and isn’t even complete if the search tree has infinite depth or cycles that aren’t filtered out.

2. Breadth-First Search (BFS): Layer by Layer

BFS does the exact opposite: it expands the shallowest node on the frontier first, using a Queue (FIFO: First In, First Out).

It checks every node 1 step away from the start, then every node 2 steps away, and so on, like a ripple spreading out in water.

• Why use it? BFS is complete (if a solution exists at a finite depth, BFS will find it), and it guarantees the shallowest solution (fewest steps).
• The catch: Memory. Because BFS has to hold an entire level of the tree in memory at once, its space complexity grows exponentially as O(b^d), where d is the depth of the shallowest goal. And if edges have different weights, the path with the fewest steps isn’t necessarily the cheapest!

3. Uniform Cost Search (UCS): Respecting Edge Weights

Look at the visualizer graph again: going from S -> B -> E -> G takes 3 edges (total cost 5 + 1 + 1 = 7), while S -> A -> D -> G also takes 3 edges (total cost 2 + 4 + 3 = 9). BFS only counts steps, so it treats all 3-step paths as tied.

Uniform Cost Search (UCS) fixes this by replacing the FIFO queue with a Priority Queue ordered by g(n), the actual cumulative cost from the start state to node n:

g(n) = total path cost from START to node n

At every step, UCS expands the frontier node with the lowest g(n). Assuming all action costs are positive, UCS is both complete and optimal.

The downside? Because UCS only looks backward at how much it has spent so far (g(n)), it searches outward in every direction equally. It will dutifully explore cheap side-streets (A and C in our visualizer) even when they point the wrong way.

Part 3: Informed Search and Heuristics

How do we stop our algorithm from wasting time on cheap roads leading in the wrong direction? We give it a compass: a heuristic function, written as h(n).

h(n) = estimated remaining cost from node n to the closest goal

In a road network, h(n) might be the straight-line (“as the crow flies”) Euclidean distance on a map, or Manhattan distance (|dx| + |dy|) on a city grid. A heuristic doesn’t know what traffic or walls lie ahead, so it’s just an estimate.

4. Greedy Best-First Search: Chasing the Goal

Greedy Best-First Search goes all-in on the heuristic. Its priority rule is simply:

Priority = h(n)

It ignores everything it has already paid to get to a node and always jumps to whichever frontier node looks closest to the goal.

In the visualizer above, Greedy Search sprints straight down S -> B -> E -> G in just 4 steps! In that particular graph, it gets lucky. But in general, Greedy Search is not optimal. If a shortcut looks close to the goal (h(n) is tiny) but has a massive toll road leading into it (g(n) is huge), Greedy will take it without hesitation.

5. A* Search: Combining Past Reality with Future Estimate

A* Search is what happens when you combine the caution of Uniform Cost Search with the goal-directed speed of Greedy Search.

For every node on the frontier, A* calculates:

f(n) = g(n) + h(n)

• g(n): The actual cost already spent to reach n from the start.
• h(n): The estimated cost remaining from n to the goal.
• f(n): The estimated total cost of the cheapest solution that passes through n.

Here is the mental model that made this click for me in class:

• UCS only looks at the past (g(n)).
• Greedy only looks at the future (h(n)).
• A* looks at the whole journey (g(n) + h(n)).

If you run A* in the visualizer above, watch what happens after it expands S and A:

• Node C has a cheap path cost (g(C) = 4), which tricked UCS into expanding it.
• But A* adds the heuristic (h(C) = 7), seeing that f(C) = 4 + 7 = 11.
• Meanwhile, node B has g(B) = 5 and h(B) = 3, giving f(B) = 8.
• A* skips C and D completely and heads down B -> E -> G, finding the optimal path of cost 7 while doing less work than UCS!

When Is A* Guaranteed to Find the Best Path?

A* is only as trustworthy as its heuristic h(n). If your heuristic lies and tells A* that a great path costs a million dollars, A* might never explore it and settle for a worse path instead.

That brings us to the two properties of heuristics we covered on Day 2: Admissibility and Consistency.

1. Admissibility (Never Overestimate)

Let h*(n) be the true optimal remaining cost from node n to the goal. A heuristic is admissible if, for every node:

0 <= h(n) <= h*(n)

In plain English, an admissible heuristic is optimistic. It can think the goal is closer than it really is, or it can nail the exact cost, but it can never overestimate the cost.

• Why is straight-line distance admissible for driving directions? Because the shortest physical path between two points is a straight line. No real road can ever be shorter than the straight-line distance, so straight-line distance never overestimates real driving distance.
• What if h(n) = 0 for every node? That is technically admissible (zero never overestimates a positive cost!), and A* simply turns back into Uniform Cost Search.

When h(n) is admissible, tree-search A* is guaranteed to return an optimal solution.

2. Consistency (The Triangle Inequality)

When we use a visited set (graph search) so we don’t re-expand states we’ve already seen, we need a slightly stronger rule called consistency (or monotonicity).

For every node n and each of its successors n' connected by an action with step cost cost(n, n'):

h(n) <= cost(n, n') + h(n')

Think of it like this: if my heuristic says I am 10 miles from the goal (h(n) = 10), and I drive 2 miles down the road to a neighbor n' (cost(n, n') = 2), my new estimate h(n') shouldn’t suddenly drop to 1 mile. The estimate shouldn’t drop by more than the actual distance I just traveled.

Every consistent heuristic is automatically admissible, and with a consistent heuristic, graph-search A* is guaranteed to be optimal without ever needing to re-open a visited node.

Summary Comparison

Whenever I need to keep all five algorithms straight, I come back to this table:

Writing this out and wiring up the visualizer made it much clearer why A* shows up everywhere from video game pathfinding to robotics: it doesn’t reinvent graph search, it just uses a smarter priority score on the frontier.