CODEWITHSUNDEEP
javaalgorithmdepth-first-searchbreadth-first-search
user3871
user3871

Reputation: 12718

Depth First Search and Breadth First Search Understanding

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?

enter image description here

enter image description here

Thanks!

Upvotes: 26

Views: 16707

Answers (2)

Vitor De Mario
Vitor De Mario

Reputation: 1179

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.

Upvotes: 4

wazy
wazy

Reputation: 1065

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/

Upvotes: 1

Related Questions