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!

Answer 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.