Imagine doing bfs on a 2D $$$n \times n$$$ grid. Your code may look something like this:
import collections
NOT_VISITED, VISITED = 0, 1
n = int(input())
grid = [[NOT_VISITED] * n for i in range(n)]
queue = collections.deque([(0, 0)])
while len(queue):
x, y = queue.popleft()
for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == NOT_VISITED:
queue.append((nx, ny))
grid[nx][ny] = VISITED
print(grid)
It works in $$$O(n^2)$$$, nothing interesting. But if we write it like this:
import collections
NOT_VISITED, VISITED = 0, 1
n = int(input())
grid = [[NOT_VISITED] * n for i in range(n)]
queue = collections.deque([(0, 0)])
while len(queue):
x, y = queue.popleft()
grid[x][y] = VISITED
for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == NOT_VISITED:
queue.append((nx, ny))
print(grid)
The code now works in $$$O\left(\dfrac{4^n}{\sqrt{n}}\right)$$$ :skull: :skull: :skull:
Can you figure out why?
In the second code, the cell is marked as visited, but its neighbors are not. This allows the same cell to be visited multiple times, leading to an exponential blow-up.
In second version, you mark the current cell as visited before you check the neighbours.
That would mean that you might re visit the same cell multiple times cause the cell is being put back into queue for checking later even though it is marked as visited.
Also, can you explain how you got the time complexity for second code? i am still working on my skills and would be happy to know
The number of operations spent by the algorithm is $$$c \cdot \text{number of things added to the queue}$$$. You can try to convince yourself that the number of times cell $$$(x, y)$$$ gets added to the queue is the number of shortest paths from $$$(0, 0)$$$ to $$$(x, y)$$$, which is $$$\binom{x + y}{x}$$$.
Therefore, the number of things added to the queue is $$$\sum_{x=0}^{n-1} \sum_{y = 0}^{n-1} \binom{x + y}{x}$$$. Applying hockey-stick once yields $$$\sum_{x=1}^n \binom{x + n - 1}{x} = \sum_{x=1}^n \binom{x + n - 1}{n - 1}$$$. Applying hockey-stick again yields $$$\binom{2n}{n} - 1$$$.
One can use Stirling's approximation, $$$n! \sim \sqrt{2\pi n} (\frac{n}{e})^n$$$, to show that $$$O(\binom{2n}{n}) = O(\frac{4^n}{\sqrt{n}})$$$. I learned the last part just now thanks to Google AI lmao.
Interesting, is there a similar issue for DFS using stack?
Yes
tyristik The user is disabled.
fix the second code by checking if the cell is visited before