Order of values in dfs and bfs

Question

Let's consider a matrix of integers m:

[[1,2,3]
[4,5,6]
[7,8,9]]

Which represents a graph:

 (1)
 / \
 (4) (2)
 / \ / \
(7) (5) (3)
 \ / \ / 
 (8) (6)
 \ /
 (9) 

There are two implementations of traversals bfs and dfs. BFS uses queue, DFS uses stack, since there is no stack data structure in python both could be implemented using simple listor any other arbitrarily chosen data structure, which behaves like a queue and stack respectively, I opted for deque.

def bfs_iterative(matrix, i, j, visited=None):
 if not matrix:
 return
 values = [matrix[i][j]]
 rows, cols = len(matrix), len(matrix[0])
 visited = visited if visited else set()
 
 queue = deque([(i, j)])
 visited.add((i, j))
 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 while queue:
 row, col = queue.popleft()
 for dr, dc in directions:
 r, c = row + dr, col + dc
 if r not in range(rows):
 continue
 if c not in range(cols):
 continue
 if (r, c) in visited:
 continue
 queue.append((r, c))
 visited.add((r, c))
 values.append(matrix[r][c])
 return values
 
 
 
def dfs_iterative(matrix, i, j, visited=None):
 if not matrix:
 return
 values = []
 rows, cols = len(matrix), len(matrix[0])
 visited = visited if visited else set()
 
 stack = deque()
 stack.append((i, j))
 directions = [
 (0, -1),
 (0, 1),
 (-1, 0),
 (1, 0),
 ]
 while stack:
 row, col = stack.pop()
 if (row, col) not in visited:
 visited.add((row, col))
 values.append(matrix[row][col])
 
 for dr, dc in directions:
 r, c = row + dr, col + dc
 if r not in range(rows):
 continue
 if c not in range(cols):
 continue
 if (r, c) in visited:
 continue
 stack.append((r, c))
 
 return values

Depending on the order of directions in bfs the output of the values will be: [1,4,2,7,5,3,8,6,9] or [1,2,4,3,5,7,6,8,9], which probably doesn't matter since "levels" are diagonals and the levels are in correct order (top to down), the elements are left to right or right to left. But for dfs there are more possible outputs and I wonder whether my implementation is off or each of those outputs is correct. Since for BST there are in-order, post-order, pre-order traversals and each is valid and each is dfs I think the 2nd option, but I cannot find a decent read about that actually. Found A BFS and DFS implementation which sort of tackles this question.

• RootTwo: I think you mixed up "bfs" and "dfs" in the last paragraph. A bfs searches a "level" before it goes to a deeper level. A dfs keeps going deeper until it can't go any deeper, then backs up until it finds a different path to try.
• Gameplay: Right, fixed that

Answer 1

Visited?

What is the point of visited=None in your function signatures? It looks like you're setting up for a recursive call, where the standard caller doesn't provide a visited argument, but the recursive call needs to pass it in.

You could omit the argument, and simply write visited = set() in the bodies of the functions.

Or are you allowing the caller to provide a collection of locations which shouldn't be visited? In which case, do you really want that collection to be modified by your function? Maybe you want:

 visited = set(visited) if visited else set()

to a) make a copy you can freely modified, and b) ensure the collection they've given you is actually an \$O(1)\$ set.

Optional[list[int]]

The if not matrix: return complicates your function. Instead of your functions returning a list[int], they return the more complicated Optional[list[int]].

If the matrix is empty, using return [] keeps your return type consistent.

Ranges

 rows, cols = len(matrix), len(matrix[0])
 ...
 while queue:
 ...
 for dr, dc in directions:
 if r not in range(rows):
 continue
 if c not in range(cols):
 continue

Pop quiz: given a 9x11 matrix, how many range() objects are created? How many unique range() objects did you actually need?

How about:

 rows = range(len(matrix))
 cols = range(len(matrix[0]))
 ...
 while queue:
 ...
 for dr, dc in directions:
 if r not in rows:
 continue
 if c not in cols:
 continue

BFS Loop rerolling

Consider 1 of the initial lines, and 1 of the last lines of your loop:

 values = [matrix[i][j]]
 ...
 ...
 values.append(matrix[r][c])

In addition to creating the values structure, the first statements is adding matrix[r][c] to that structures ... assume i, j = r, c that is. It looks like you've primed your loop wrong, causing you to need to replicate the logic in both places.

In the DFS, you append to values just after you visit (pop) (row, col) off the stack. You can do the same thing here:

 values = []
 visited = {(i, j)}
 queue = deque([(i, j)])
 while queue:
 row, col = queue.popleft()
 values.append(matrix[r][c])
 for dr, dc in directions:
 r, c = row + dr, col + dc
 if r in rows and c in cols and (r, c) not in visited:
 visited.add((r, c))
 queue.append((r, c))

• Gameplay: Visited - not sure I want to allocate memory for that possibly huge set if I don't want to do if for pretty small range objects, do I? Optional - yeah, that's true, didn't type hint, didn't notice, good point. Pop quiz: 0...I need literally 0 range objects, cause I could just if r<0 or r>rows-1 I guess values.append(matrix[r][c]) should be values.append(matrix[row][col]), cause r and c are not defined in this scope, right? It is redundant, I agree, however not sure what do you mean by "wrong" tbh and what logic is replicated, I'll give it a 2nd look though. Thanks :)