algorithm for DFS

Question

Can anybody tell me the algorithm for depth first search (DFS)? I need to write the code for DFS in python.

Answer 1

See my answer on searching at http://stackoverflow.com/questions/3225878/how-can-i-reduce-this-problem-to-the-tower-of-hanoi-or-solve-it-in-the-least-num/3225916#3225916

The only difference between a BFS and a DFS is where in your to-check list you insert your next state.

At that link, I was talking about a game. So when I say "board", I really mean "state" or "node", and when I say "move", I mean "link" or "transition". It's just terminology.

Answer 2

The basic difference between DFS and BFS is whether you are checking the area directly around you first, or scouting out at a distance first. Imagine you are on a chessboard at the upper-left corner (0,0). In BFS, you would check the three squares next to you first: (1,0),(1,1),(0,1). Then, you'd check the squares next to (1,0) - making sure that you don't check one that you already checked! (This is important in BFS and DFS.) Then the ones next to (1,1) and the ones next to (0,1). Then you would start checking the next "layer" outwards, until you ran out of things that you haven't checked yet. DFS is similar, but instead of doing things one "layer at a time" outwards from the starting point, you "scout out" as far as possible first.

Another metaphor is imagine that you are paper-wrapping a whole oak tree in a park. If you wrapped things the BFS way, you would wrap the trunk, then all the really thick branches until they were done, then all the thinner branches until they were done, and finally all the leaves. If you did it in the DFS way, you would wrap the trunk, then pick a big branch and wrap that, then wrap the first small branch off that, then the first leaf off that... and then you'd "back off" just a little and wrap the nearby leaves... and then "back off" to the next small branch, and do all its leaves. Et ceteras.

Answer 3

There isn't really an algorithm for depth first search - it is an algorithm. It's also a common building block for other algorithms.

In depth first search, you keep pushing forward as far as you can before backtracking as little as possible to try alternatives. This is in contrast to breadth first search, where you examine every alternative from your current state before exploring any of the possible next-states you discover.

That is, in depth first search, as you find new places/states/intermediate solutions, you place them on a last-in-first-out stack. In a breadth-first search, you place them in a first-in-first-out queue.

Very often (but not always), the stack for a depth-first search is implicit (the processor stack). What this means is that the search is implemented by making recursive calls.

The following is a pseudo-C++ depth-first search of a binary tree (not a binary search tree - there is no ordering assumption)...

bool Find (position_t p_Start, position_t &p_Result)
{
  if (p_Start.Contains_Goal ())
  {
    p_Result = p_Start;
    return true;
  }

  return (Find (p_Start.Left_Child ()) || Find (p_Start.Right_Child ()));
    //  Note - second Find call only occurs if the first fails, due to the
    //         shortcut behaviour of ||
}

There's a fun DFS-based algorithm for generating random mazes - the description below seems pretty good.

http://www.mazeworks.com/mazegen/mazetut/index.htm