Breadth-first-search does not prune a search space; it just sorts the search space based on depth. It also assumes the cost of every path is equal.

Example: Finding the shortest road between two cities.

With breadth-first-search, we would consider all connected cities, and then the cities they are connected to, until we reach our destination. We would end up with a route, that travels through the least amount of cities, irregardless of the lengths of the actual roads. We would get the most simple route not the shortest route nor the fastest route.

Feature: calculating using actual costs

To get the shortest route we need to be able to annotate road-length (as cost) in our graph. Using that information we can choose to expand shorter routes before we dive into the longer routes. We might expand A -> B -> C before A -> D because the cummulative road-length of A -> B -> C might be less than the direct road between A -> D. For this to happen we would constantly sort our working set, based on the calculated cost.

As soon as a completed route (to the destination) is at the top of our working set, we can stop and deliver the answer.

Optimization: Pruning

Now, this working set, gets larger with every iteration. If we were to search for the shortest route from A -> D and the answer would be 100 miles, than the working set will contain all routes from A to anywhere, that are less than a 100 miles.

This is very expensive in terms of memory and time: we need to prune the search space. Now, our working set is already sorted based on cost. So we can safely remove every route that ends in the same place as a route above it in the working set. In other words, if A -> B -> C is higher in the working set than A -> D -> C, than we remove A -> D -> C. We simply don't have to expand routes from the same origin twice.

Optimization: using a lower bound

If the costs are truly unpredictable, and we want a perfect answer, this is the best we can do. But costs are rarely unpredictable! Can we provide a lower bound? Sure! Let's use the geospatial distance between two cities. No road is shorter, than the actual distance between the cities.

In this scenario, the costs of our working-set would be calculated as the actual costs of the partial route plus the lower bound. So, the cost of A -> B -> C would be calculated as the actual road length from A upto C plus the distance from C to the destination.

Now this impacts the sorting of the working set. Which is why it is so important it is a lower bound and not an estimate. Because as soon a completed route is at the top of our working-set we call it quits, and deliver the answer.

In a nutshell: A* is a best-first-search that is capable of utilizing a lower bound to sort the search space. It's behavior is far removed from breadth-first-search.

For example, if the task is to find the shortest path between two cities on a highway map, you can calculate a straight-line "as the crow flies" distance to the goal from any point on the map - that is a usable distance metric. A* makes use of that additional information to find the shortest possible path while evaluating the fewest necessary number of alternative routes.

[Caveat: My dad invented A*, so I've probably got this laughably wrong. :-) ]