How can I remember which data structures are used by DFS and BFS?

Question

I always mix up whether I use a stack or a queue for DFS or BFS. Can someone please provide some intuition about how to remember which algorithm uses which data structure?

Solution 1

Draw a small graph on a piece of paper and think about the order in which nodes are processed in each implementation. How does the order in which you encounter the nodes and the order in which you process the nodes differ between the searches?

One of them uses a stack (depth-first) and the other uses a queue (breadth-first) (for non-recursive implementations, at least).

Solution 2

Queue can be generally thought as horizontal in structure i.e, breadth/width can be attributed to it - BFS, whereas

Stack is visualized as a vertical structure and hence has depth - DFS.

Solution 3

I remember it by keeping Barbecue in my mind. Barbecue starts with a 'B' and ends with a sound like 'q' hence BFS -> Queue and the remaining ones DFS -> stack.

Solution 4

BFS explores/processes the closest vertices first and then moves outwards away from the source. Given this, you want to use a data structure that when queried gives you the oldest element, based on the order they were inserted. A queue is what you need in this case since it is first-in-first-out(FIFO). Whereas a DFS explores as far as possible along each branch first and then bracktracks. For this, a stack works better since it is LIFO(last-in-first-out)

Solution 5

Take it in Alphabetical order...

.... B(BFS).....C......D (DFS)....

.... Q(Queue)...R......S (Stack)...

View more solutions

Comments

[RBT]

Good observation :)

[tryurbest]

Google likes this answer it seems. If you search for this question google extracts this answer out. So here is an upvote for that.

[M-J]

Hahaha OMG I didn't have the problem of OP when I stumbled upon this question, but after reading this answer, no way I forget that :D

[disklosr]

This should be the accepted answer. So intuitive!

[Yaman]

:D :D :D :D :D :D :D