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?

Answer 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).

Answer 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.

Answer 3

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)

Answer 4

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.

Answer 5

Take it in Alphabetical order...

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

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

Answer 6

BFS uses always queue, Dfs uses Stack data structure. As the earlier explanation tell about DFS is using backtracking. Remember backtracking can proceed only by Stack.

Answer 7

Bfs;Breadth=>queue

Dfs;Depth=>stack

Refer to their structure

Answer 8

The depth-first search uses a Stack to remember where it should go when it reaches a dead end.

DFSS

Answer 9

1. Stack (Last In First Out, LIFO). For DFS, we retrieve it from root to the farthest node as much as possible, this is the same idea as LIFO.

2. Queue (First In First Out, FIFO). For BFS, we retrieve it one level by one leve, after we visit upper level of the node, we visit bottom level of node, this is the same idea as FIFO.

Answer 10

An easier way to remember, especially for young students, is to use similar acronym:

BFS => Boy FriendS in queue (for popular ladies apparently).

DFS is otherwise (stack).

Answer 11

Don't remember anything.

Assuming the data structure used for the search is X:

Breadth First = Nodes entered X earlier, have to be generated on the tree first: X is a queue.

Depth First = Nodes entered X later, must be generated on the tree first: X is a stack.

In brief: Stack is Last-In-First-Out, which is DFS. Queue is First-In-First-Out, which is BFS.

Answer 12

I would like to share this answer: https://stackoverflow.com/a/20429574/3221630

Taking BFS and replacing a the queue with a stack, reproduces the same visiting order of DFS, it uses more space than the actual DFS algorithm.

Answer 13

You can remember by making an acronym

BQDS

Beautiful Queen has Done Sins.

In Hindi, बहुरानी क्यु दर्द सहा