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.
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.)
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.
· 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.