> I'm pretty sure that's a BFS, not a DFS. A DFS uses a stack, not a queue.

In the gist, queue.push adds element to the tail end, and queue.pop removes from the tail end.

For it to be behave as BFS, you will have to change queue.pop to queue.shift which will remove elements from the front.

An ideal graph search implementation will take queue as a parameter, and will use queue.enqueue and queue.dequeue. And then the injection -> implementation mapping will be:

  LIFOQueue(stacks) -> DFS
  FIFOQueue(regular queues) -> BFS
  PriorityQueue -> Some sort of Best First Search
  PriorityQueue with A* heuristics -> A* search(duh)

But I didn't want to go through all that trouble to demonstrate a simple snippet.

Interesting, I had never seen this formulation where DFS and BFS can be expressed by a single algorithm that differs only in the behavior of the "queue." It's still a bit misleading to call it "queue" since it might be a stack, but I see the intention.

This formulation of DFS (which tracks a stack of nodes to visit) is less efficient than one that tracks a stack of iterators, because the size of your stack is O(vertices) instead of O(graph depth). On the other hand, it's simpler in some ways, so I can see why it would be preferable in some situations.

Many graph search algorithms can be expressed as a generic graph search algorithm where you have a "white set" of unvisited nodes, a "black set" of visited nodes, and a "grey set" of nodes that you've encountered but have yet to visit. The structure of the grey set determines the algorithm:

Queue = BFS

Stack = DFS

Priority queue by distance from start = Dijkstra's algorithm

Priority queue by distance + heuristic = A*

Bounded priority queue by heuristic = Beam search

Priority queue by connecting edge weights = Prim's algorithm

Pointer reversal = Mark & sweep garbage collector

Check on whether it points into from-space = Copying garbage collector.

Norvig's practical ai programming has a great chapter on search which also shows how similarly different algorithms can be expressed if you have the right abstraction

In case someone runs into this comment and is interested in checking out the book, the book is called AIMA(Artificial Intelligence: A modern approach), and here is the relevant code.

http://aima-python.googlecode.com/svn/trunk/search.py

It's a long file though.

Also, justinh meant this other code instead: http://norvig.com/paip/search.lisp (from Norvig's other book).

Oh. I should have guessed "practical ai programming" was actually PAIP(Paradigms...). I haven't read PAIP, but have read AIMA, and the topic under discussion occurs in AIMA; so I assumed OP meant AIMA.

Perfectly reasonable! The treatment is similar but less formal/complete in PAIP.

My bad for getting the name of the book wrong. I thought of it as PAIP for so long I forget what the actual name is :) Great book though, even for those not especially interested in AI or Lisp

I agree, and relevantly to this post it's a deep book on programming where algorithms and algorithm design do appear but aren't really central. They're an essential part of the toolbox but not the focus.

When I overhauled that code for the third edition, I messed up the A* search. I don't remember what the bug was offhand -- just saying, the OP is not the only one who has trouble sometimes.

> DFS and BFS can be expressed by a single algorithm that differs only in the behavior of the "queue."

Correct me if I am wrong, but the naive non-recursive DFS and BFS differ only in the implementation of queue.

https://gist.github.com/1791284

Isn't that what I said?

My bad. Written communication is confusing - your comment sounded incredulous.

EDIT: In retrospect, you did mention you find it interesting - don't know how it jumped out as incredulous.

Despite the name, he is using the array as a stack, not as a queue.

Only uses #push and #pop, so it's actually a stack. I dunno why it's named queue.