How AI search works: BFS, DFS, greedy, and A* are one loop

Prerequisites: Python from zero and Object-oriented Python — the machinery here is built as classes, because this guide's central idea (one loop, four algorithms) is naturally one base class with four subclasses.

Three hard facts shape everything in this guide:

A computer cannot "see" a solution. It has no intuition, no overview, no gut feeling. All it can do is try possibilities, one at a time, very fast.
Possibilities multiply brutally. Choosing one of 10 vendors for each of 10 services is 10 × 10 × … = 10 billion combinations. Trying them all stops being an option almost immediately.
Memory is what separates exploring from wandering. If the computer doesn't remember where it has been and where it could go next, it will walk in circles forever.

Classic AI's answer to all three is search: turn the problem into a space of states, then explore that space systematically. And the beautiful part — the reason this guide covers four famous algorithms in one sitting — is that breadth-first search, depth-first search, greedy best-first, and A* are one loop, written once in a base class. They differ in exactly one overridden method: which discovered possibility to explore next.

Why search exists: too many possibilities, no crystal ball

Look at three problems that seem unrelated:

A café kitchen must figure out which order items can be prepared in parallel, given that some steps depend on others.
A restaurant must seat a party of 5 at the best available table tonight.
A venue must pick one vendor per service — catering, decoration, music — for the lowest total cost under a budget.

None of these has a formula you can just evaluate. Each is a sequence of choices, where every choice opens some options and closes others. Writing if/else for every situation is hopeless: the situations multiply faster than you can type.

The move that unlocks all of them — the founding idea of classic AI — is to describe the problem in three parts and let a general algorithm do the choosing (Russell & Norvig, 2021):

State — a snapshot of the situation. "Services catering and music are booked, ₨40,000 spent."
Actions — what you can do in a state, each leading to a new state. "Book vendor V for decoration."
Goal test — how to recognize that a state is a solution. "All three services booked, total under budget."

Once you've done this, something clicks: states are nodes, actions are edges — your problem is a graph. Not a graph anyone draws; it exists implicitly, one neighbors(state) call at a time. Solving the problem now means one thing only: find a path from the start state to a goal state. Solve that once, generally, and you've solved the café, the restaurant, the venue, and every maze ever printed.

One loop to rule them all: the frontier

So how do you explore a graph you can't see, without walking in circles? Derive it from the constraints. At any moment mid-exploration, every state falls into one of three groups:

States you've explored — you've seen their neighbors.
States you've discovered but not yet explored — you know they exist, you haven't looked around from them.
States you haven't discovered yet.

Group 2 is the famous one: the frontier. It's the edge of the known world — every state where exploration could continue next. And group 1 must be remembered too (the visited set), because real graphs have cycles: forget where you've been, and the loop A → B → A → B runs forever.

That's the whole design. Here it is in Python — three small classes. Problem describes the world (subclass it for your domain); Node is one frontier entry that remembers how it got there; Search is the loop itself:

class Problem:
    """Describe YOUR problem by subclassing this — the algorithms
    never need to know what domain they're exploring."""
    def neighbors(self, state): ...   # returns [(next_state, step_cost), ...]
    def is_goal(self, state): ...
    def h(self, state): return 0      # heuristic guess — we'll meet it later


class Node:
    """One frontier entry: a state, plus how we got there and what it cost."""
    def __init__(self, state, path, cost):
        self.state = state
        self.path = path
        self.cost = cost


class Search:
    """The loop, written once. Each algorithm answers ONE question:
    take() — which frontier node deserves attention next?"""

    def __init__(self, problem):
        self.problem = problem            # composition: a Search HAS a Problem

    def take(self, frontier):
        raise NotImplementedError         # ← the only thing subclasses change

    def run(self, start):
        frontier = [Node(start, [start], 0)]
        visited = set()

        while frontier:
            node = self.take(frontier)    # ← THE question: which one next?
            if self.problem.is_goal(node.state):
                return node               # found it — node.path tells the story
            if node.state in visited:
                continue
            visited.add(node.state)
            for nxt, step_cost in self.problem.neighbors(node.state):
                if nxt not in visited:
                    frontier.append(Node(nxt, node.path + [nxt], node.cost + step_cost))

        return None                       # frontier empty: no solution exists

Watch this loop run on a small graph — keep your eye on the two lists at the bottom, because they are the algorithm:

Everything that follows — BFS, DFS, greedy, A* — inherits this exact run(), unchanged. The four algorithms disagree about one single method: take(). Which discovered-but-unexplored node deserves attention next? Answer that question four different ways and you get four subclasses with wildly different personalities.

The object-oriented shape isn't decoration, it's the accurate description: the shared idea lives once in the base class; each algorithm is exactly one overridden method. When you meet a design where variants differ in a single decision, this — inheritance plus overriding — is the tool that says so in code.

Take the oldest: breadth-first search

The first honest answer to "which node next?" is: the one that has waited longest. Treat the frontier as a queue — first in, first out — and the loop becomes breadth-first search (BFS):

class BreadthFirst(Search):
    def take(self, frontier):
        return frontier.pop(0)        # the oldest — that's the entire algorithm

Notice what the subclass does not contain: no loop, no visited set, no goal test — all inherited from Search. Three lines are the whole algorithm.

Why does "oldest first" matter? Because of what it implies geometrically. BFS explores every state 1 step from the start before any state 2 steps away, every 2-step state before any 3-step one — it expands in rings, like ripples on water. Which gives BFS its guarantee: the first time BFS reaches any state, it has reached it in the fewest possible steps. There is no shorter route left to find, because every shorter route was already fully explored.

The price is memory. The frontier holds an entire ring at once, and rings grow fast: if every state has 4 neighbors, ring 10 can hold thousands of states. BFS trades memory for its shortest-path certificate.

BFS earns its keep wherever "fewest steps" is the actual question — and in one less obvious place: dependency levels. Run BFS over a graph of "step X must happen before step Y" (a café's prep steps, a build system's tasks) and the rings are the schedule: ring 0 is everything you can start right now, ring 1 is everything unlocked once ring 0 finishes. Level-by-level exploration doubles as level-by-level planning.

Take the newest: depth-first search

The opposite answer — the node discovered most recently — treats the frontier as a stack, last in, first out, and the loop becomes depth-first search (DFS):

class DepthFirst(Search):
    def take(self, frontier):
        return frontier.pop()         # the newest — one argument of difference

The personality flips completely. Where BFS ripples outward evenly, DFS picks a direction and commits, diving deeper and deeper until it hits a dead end, then backtracking to the most recent fork and diving again. Watch both run on the same graph:

Why would anyone want this? Memory. DFS's frontier holds only the current path and the untried forks along it — while BFS was holding an entire exponentially-wide ring, DFS holds a sliver. On a deep graph, that's the difference between fitting in memory and not.

The price is the guarantee: DFS finds a path, not the shortest one — whatever its dive happened to stumble into first. So use DFS when path length doesn't matter: when you must visit everything anyway, or when the graph is a tree of decisions with no cycles to punish a deep dive. That second case matters more than it looks — goal-driven reasoning in rule-based expert systems is exactly a DFS over a tree of "what would prove this?" questions.

Add a compass: greedy best-first search

BFS and DFS share an embarrassing flaw: they are blind. BFS will diligently explore a thousand states in the exact opposite direction of the goal, because they're in the current ring and the ring must be finished. Neither algorithm uses the one thing you often have: a rough sense of which direction the goal is.

That rough sense has a name: a heuristic, written h(n) — a cheap function that estimates how far state n is from the goal. On a map: straight-line distance. Booking vendors: number of services still unbooked. It doesn't need to be exact; it needs to be cheap and roughly right.

Now the third answer to "which node next?": the one that looks closest to the goal — the frontier node whose state has the smallest h:

class GreedyBestFirst(Search):
    def take(self, frontier):
        best = min(frontier, key=lambda node: self.problem.h(node.state))
        frontier.remove(best)
        return best

This is greedy best-first search (the frontier now behaves as a priority queue). When the heuristic is decent, the effect is dramatic: instead of rippling in all directions, exploration streaks toward the goal, touching a fraction of the states BFS would. And note where h lives: on the Problem, not the algorithm — the domain knows its own geography; the algorithm just asks.

But the name "greedy" is a warning label. h(n) estimates the road ahead and says nothing about the road behind — greedy never checks what a path has already cost. A route can inch closer to the goal with every step while getting more expensive with every step, and greedy will take it every time. It optimizes the view, not the bill.

Remember what you paid: A*

The fix is almost anticlimactic. Greedy judged a state by h(n) alone — the estimated cost remaining. But you know something else about every frontier state with perfect accuracy: g(n), the cost you actually paid to reach it. Judge each state by the whole journey:

f(n) = g(n) + h(n)
       ^      ^
       paid   estimated remaining

Take the frontier node with the smallest f, and the loop becomes A* (pronounced "A-star"; Hart, Nilsson, & Raphael, 1968):

class AStar(Search):
    def take(self, frontier):
        best = min(frontier, key=lambda node: node.cost + self.problem.h(node.state))
        frontier.remove(best)
        return best

node.cost is g — and notice it was there all along: every Node has been carrying its cost since the base class, but A* is the first algorithm to look at it. A state that's close to the goal but was expensive to reach now competes fairly against one that's farther away but cheap — exactly the comparison greedy refused to make.

A* comes with a guarantee, on one condition: the heuristic must be admissible — it must never overestimate the true remaining cost. Under-promising is safe; over-promising is fatal. Here's the intuition: A* only commits to the goal when the goal has the lowest f in the entire frontier. If h never overestimates, then every other frontier state's f is an honest "this route will cost at least this much" — so if all of them already exceed the goal's actual price, no cheaper route can possibly be hiding behind them. Overestimate, and that reasoning collapses: a genuinely cheap route can look expensive and get skipped.

Admissible heuristics are usually easy to build: relax the problem. Straight-line distance is admissible because the real path can't beat a straight line. "Sum of each remaining service's cheapest vendor" is admissible because you can't book a service for less than its cheapest option. Drop a constraint, cost the relaxed problem, and you have a promise that can't overshoot.

Watch greedy and A* race across the same terrain — the orange cells are mud, costing 5 to enter instead of 1:

Greedy plows straight through the mud (the view is great; it never checks the bill). A* explores more cells but returns the genuinely cheapest path — and notice in the sim's final step what happens when the mud gets cheaper: A* changes its mind, because the costs changed, not the geometry. One more connection worth knowing: set h(n) = 0 — no compass at all — and A* degrades gracefully into Dijkstra's algorithm (Dijkstra, 1959), pure lowest-cost-first caution. A* is Dijkstra with a sense of direction.

Choosing your discipline

Four algorithms, one loop, one swapped line:

Algorithm	`take()` picks	Guarantee	Cost	Reach for it when
BFS	oldest (queue)	fewest steps	memory-hungry	steps are what count, or you need dependency levels
DFS	newest (stack)	none	can find long paths	you must visit everything, or you're proving goals in a tree
Greedy best-first	smallest `h(n)`	none	can be fooled by `h`	speed matters more than optimality and `h` is decent
A*	smallest `g(n) + h(n)`	cheapest path, if `h` admissible	explores more than greedy	costs differ and the answer must be right

And a practical note for your own projects: the formulation is the real work. The four algorithm classes above never change; your work is a Problem subclass — neighbors, is_goal, and (for A*) an admissible h for your domain: orders, tables, vendors. Write that, hand it to any of the four algorithms, and search just works. That clean split — domain in one class, strategy in another — is composition doing what it's for.

Takeaways

Search exists because state spaces explode. 10 choices with 10 options each is 10 billion combinations; systematic exploration with memory is the only honest way through.
Formulation is the work. State + actions + goal test turns any decision problem into a graph; the algorithm is generic after that.
One loop, one overridden method. The Search base class owns the frontier and the visited set; BFS, DFS, greedy, and A* are subclasses that override take() alone — inheritance carrying a real algorithmic idea, not a textbook exercise.
BFS buys "fewest steps" with memory; DFS buys memory with the guarantee. Pick by which resource — and which promise — your problem actually needs.
Greedy optimizes the view, not the bill. h(n) alone ignores cost already paid; that's why it's fast and why it's fooled.
A* is greedy with a memory of costs — f = g + h — and it's optimal exactly when h never overestimates. Build admissible heuristics by relaxing the problem.

References

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271. https://doi.org/10.1007/BF01386390
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136
Patel, A. (n.d.). Introduction to the A* algorithm. Red Blob Games. Retrieved August 23, 2026, from https://www.redblobgames.com/pathfinding/a-star/introduction.html
Russell, S., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson.