announcements‎ > ‎

2016-04-06 BFS vs DFS

posted Apr 6, 2016, 8:26 AM by Samuel Konstantinovich   [ updated Apr 6, 2016, 8:26 AM ]


Breadth First Search vs. Depth First Search

Depth-First Search

-Tests all possibilities in one path until it needs to backtrack. This is the recursively backtrack you have written for your previous assignments (until now!)

-Does not guarantee shortest path / closest value.

(Visually DFS goes to bottom of a tree, then backtracks, etc.)


Breadth-First Search

BFS checks the first node, then its direct children, then the children of those. Tests all possibilities in order from the closest possibility to the furthest.

This will find the closest matching value or shortest path to a goal.

(Visually BFS will check the next level of the tree, then the next level... etc)

687474703a2f2f7777772e6373652e756e73772e6564752e61752f7e62696c6c772f4a757374736561726368312e676966.gif






Maze example:


# 0 1 2 3 4

0 S _ _ _ _

1 _ # # # _

2 _ _ _ # _

3 _ # _ # _

4 _ _ _ # E

Lets label the spaces we want to go to make our lives easier!

# 0 1 2 3 4

0 S a b c d

1 e # # # f

2 g h i # j

3 k # l # m

4 n o p # q


BFS:
check
a,e on the 1st pass
b,g on the 2nd pass
c,h,k on the 3rd pass
d,i,n on the 4th pass
f,l,o on the 5th
p,j on the 6th
m on the 7th
q on the 8th.


or:

0 1 2 3 4

1 # # # 5

2 3 4 # 6

3 # 5 # 7

4 5 6 # 8


Comments