Two ways to solve a maze. The faster one gives the worse answer.

Same maze, two algorithms. One looked at 40 cells. The other looked at 117.

You'd think the one that did less work is better. It isn't. It found a path that's 10 moves longer.

BFS spreads out

BFS tries everything one step away, then everything two steps away, and so on. It moves out like a ripple in a pond.

The yellow cells are the queue. First in, first out.

It visited 117 cells, so it did a lot of work. But the path is 28 moves, and that's the shortest one there is. Because it goes out in rings, the first time it reaches the goal has to be the shortest way there.

DFS picks a corridor and keeps going

DFS goes as far as it can down one corridor. It only backs up when it hits a dead end.

Same code basically. The only big change is a stack instead of a queue.

It got there after 40 cells. Nice. But the path is 38 moves.

And it just got lucky here. Add a few walls and DFS can wander through almost the whole maze first.

So which one do I use?

Need the shortest path? BFS. Think fewest hops between two people in a social network.

Just need to know if you can get there, or want to visit everything? DFS is usually less code.

You can try it here. Click cells to add walls and see what you can break: https://software-atlas.haiduc0147.dev/t/graphs