BFS Fundamentals - Breadth First Search / Introduction

can you add a code thing here so I can practice memorizing the algo here

We have a template here.

the next page has the question with the code thing there :slight_smile:

I was led here from “Evaluator”:
Question 4 out of 20
Which algorithm should you use to find a node in a narrow but deep tree when either algorithm works?

Your Answer:

Depth First Search
Correct Answer:

Breadth First Search

You state here that
"DFS is better at:

narrow but deep trees"

Isn’t that a contradiction?
Is there a bug in the Evaluator?

Dude same

The question, as it is, makes no sense to me. You have the same chances of finding something with the same speed.

The element to search is expected to be closer to the root somehow? Then BFS. If it is in the depths, then DFS might find it quicker.

As an example, imagine yourself searching a book in the 10 boxes split by 5 rows (2 boxes per row). Here is the score table that compares BFS vs DFS:

Bfs vs Dfs

Formula: score[row][col] = number of steps to arrive to that cell using BFS - those of DFS. For example, with BFS at [row 1 col 2] you arrive at second step, while with DFS you run the first column entirely (that’s 5 boxes) + that first box in the second column (total 5+1 = 6).

         col 1    col 2

row 1 0 +4
row 2 -1 +3
row 3 -2 +2
row 4 -3 +1
row 5 -4 0

Here, the score sums to 0. That means that BFS is as good as DFS in terms of speed, unless we get any details regarding possible location of our element to find.

Sorry for the messed up spaces in the table. Since I cannot edit my message nor I know how algomonster manages whitespaces (some of them got removed, some not), I just hope it is clear enough. Or unless somebody can fix it

dfs coolaid

In the template above, the root node is not being checked. Should it be this instead?

from collections import deque

def bfs_by_queue(root):
queue = deque([root]) # at least one element in the queue to kick start bfs
while len(queue) > 0: # as long as there is an element in the queue
node = queue.popleft() # dequeue
if OK(node): # early return if problem condition met
return FOUND(node)
for child in node.children: # enqueue children
return NOT_FOUND