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?

Moses

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

Whipple

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.

Biofeedback

This should be the accepted answer. So intuitive! – Esmerolda

Never thought about this! If I forget, I usually try to imagine the iteration and see if it is making sense. This is so cool! – Biretta

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

Triparted

Good observation :) – Obrian

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

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 – Simons

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

Araroba

Answer 5

Take it in Alphabetical order...

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

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

Sarge

Answer 6

BFS --> B --> Barbecue --> Queue

DFS --> S --> Stack

Virology

:D :D :D :D :D :D :D – Avron

Answer 7

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.

Aer

Answer 8

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.

Simons

Answer 9

Bfs;Breadth=>queue

Dfs;Depth=>stack

Refer to their structure

Benjy

Answer 10

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

DFSS

Olivia

Answer 11

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.

Rihana

Answer 12

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

Asleyaslope

Answer 13

if you visually rotate 'q' symbol (as in queue) 180 degrees you will get a 'b' (as in bfs).

Otherwise this is stack and dfs.

Autochthon

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Gesticulation

Answer 14

I would like to share this answer: https://mcmap.net/q/354411/-why-is-depth-first-search-claimed-to-be-space-efficient

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.

Plaided

Answer 15

You can remember by making an acronym

BQDS

Beautiful Queen has Done Sins.

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

Fragmentary

LOL Sorry but this is not a very useful suggestion. I think the word you're looking for is a nmenonic. The acronym has to be itself memorable. – Fission

@Fission , Added nmenonic as per you suggestion. – Fragmentary

Answer 16

Here is a simple analogy to remember. In a BFS, you are going one level at a time but in DFS you are going as deep as possible to the left before visiting others. Basically stacking up a big pile of stuff, then analyze them one by one, so if this is STACK, then the other one is queue.

Remember as "piling up", "stacking up", big as possible. (DFS).

Talkfest

Answer 17

Stack = Stack of Pancakes. A stack of pancakes goes down. It's deep. Depth First.

Queue = A Queue is a Line (of people). Lines go wide. Wide is Breadth First.

Holmium