[salamanderman]

Breadth-first is a queue. Depth-first is a stack. A* is a priority queue.

[cornstalks]

More specifically Dijkstra's is a priority queue. A* is a priority queue with an added estimate to the cost function to prioritize searching nodes closer to the destination.

[JohnKemeny]

OP's point is that

· BFS is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = #edges

· Dijkstra's is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = sum over edges

· A* is priority queue with key h(n) + g(n), where h(n) = heuristic(n), g(n) = sum over edges

It's cute.

[nostrademons]

Likewise, you can represent a queue as a priority queue with key = i, where i is an integer monotonically increasing at insertion time. And you can represent a stack as a priority queue where key = -i.

This is the insight behind the decorate-sort-undecorate pattern; it's just heapsort, with a different key function allowing you to represent several different algorithms.

[thaumasiotes]

> OP's point is that

> BFS is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = #edges

He doesn't say that, and it isn't true.

[JohnKemeny]

In (theoretical) computer science, we write "#xs" to denote "number of xs".

My sentence was supposed to be read as "g(n) = number of edges", and implicitly, of course (since we're talking about BFS), that means number of edges seen up until now, from ns perspective. And yes, n usually denotes the size of the graph, however, in the context of A*, we usually write n to denote the current node (as per AI:MA).

I take full responsibility. (Disclaimer: I'm a CS professor teaching BFS and Dijkstra's algorithm every semester and A* every 2nd year.)

[kragen]

I think it is true, although "#edges" needs to be understood as "the number of the edges in the path from the starting point to the node", which was not one of my first three candidate interpretations.