Depth First Search and Breadth First Search Understanding

Question

I'm making Tetris as a fun side project (not homework) and would like to implement AI so the computer can play itself. The way I've heard to do it is use BFS to search through for available places, then create an aggregate score of the most sensible drop location...

But I'm having trouble understanding the BFS and DFS algorithms. The way I learn best is by drawing it out... are my drawings correct?

---

Thanks!

Solution 1

The end result of your traversals is correct, you're pretty close. However, you're a little bit off in the details.

In the depth first search, you will pop a node, mark it as visited and stack its unvisited children. In that order. The order may seem irrelevant for a tree, but if you had a graph with cycles, you could fall in an infinite loop, but this is another discussion.

Given the baseline of the algorithm, after you push the root node into the stack, you will start your first iteration, immediately popping A. It will not remain on the stack until the end of the algorithm. You'll pop A, stack D, C and B all at once (or B, C and D, you can do it left to right or right to left, it's your choice) and mark A as visited. Right now, your stack has D in the bottom, C in the middle and B on top.

The next node popped is B. You'll push F and E into the stack (I'll keep the order the same as yours), marking B as visited. The stack has, from top to bottom, E F C D. Next, E is popped, no new nodes are added and E is marked as visited. The loop will continue, doing the same to F, C and D. The final order is A B E F C D.

I'll try to rewrite the algorithm in a similar way to yours:

Push root into stack
Loop until stack is empty
    Pop node N on top of stack
    Mark N as visited
    For each children M of N
        If M has not been visited (M.visited() == false)
            Push M on top of stack

I won't go into details for the breadth first search, the algorithm is exactly the same. The difference is in the data structure and how it behaves. A queue is FIFO (First In First Out) and, because of that, you will visit all the nodes in the same level before you start visiting the nodes in the inferior levels.

Solution 2

First of all I believe your traversals seem okay (from a quick overview). I am going to give you some useful links below.

I've found some decent videos on youtube about this before but here is one (not the best I've seen) that covers it http://www.youtube.com/watch?v=eXaaYoTKBlE. If you are doing it for fun make two versions, one with DFS and one with BFS and benchmark them to observe the difference. Also download the graph searcher and any other tools you find useful from http://www.aispace.org/downloads.shtml if you want to trace some for better understanding. And last but not least a stackoverflow question on DFS and BFS http://www.stackoverflow.com/questions/687731/

Comments

[wazy]

Note: It's not very efficient or realtime to use DFS because of the amount of possibilities becomes very very large, so you use BFS to come up with a reasonable move based upon some calculations. Not quite as relevant here but you may want to look into the Minimax algorithm for AI because it is relatively simple and demonstrates cutting down the amount of possibilities to come up with a move much faster (usually in Tic-tac-toe).

[Luiggi Mendoza]

@wazy it will depend on the data. What if the graph has more nodes per level than per height?

[wazy]

I hate to say it "depends" but it is pretty reliant on are you trying to find a solution "quickly" (or at least attempting to and not necessarily optimal) or are you trying to evaluate every possible solution/combination.

[Luiggi Mendoza]

@wazy again, it depends. If you know something about data, then you can apply the best algorithm for it. If you know nothing about it, probably the BFS would do it. Also, it depends on the real problem to begin with.

[wazy]

@Luiggi Mendoza Yea I can't make any assumptions hence my previous comment.