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?

score 146 · Answer 1 · answered Sep 24 '15 at 05:23

146

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.

answered Sep 24 '15 at 05:23

Sai Kumar Battinoju

1,569
2
9
4

2

This should be the accepted answer. So intuitive! – disklosr Feb 05 '21 at 10:13

James McNellis · Accepted Answer · 2020-01-27T21:33:16.410

41

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

edited Jan 27 '20 at 21:33

answered Oct 14 '10 at 00:22

James McNellis

338,529
73
897
968

score 39 · Answer 3 · answered Sep 28 '14 at 09:51

39

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.

answered Sep 28 '14 at 09:51

kawadhiya21

2,417
18
33

1

Good observation :) – RBT Apr 19 '17 at 01:17
1

Google likes this answer it seems. If you search for this question google extracts this answer out. So here is an upvote for that. – tryurbest Jul 13 '18 at 15:50
2

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 – M-J Nov 25 '18 at 10:44

score 27 · Answer 4 · answered Oct 20 '11 at 08:56

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)

score 11 · Answer 5 · answered May 17 '16 at 10:59

11

Take it in Alphabetical order...

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

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

answered May 17 '16 at 10:59

Shaik Ameer Basha

119
1
2

score 10 · Answer 6 · answered Mar 04 '13 at 09:30

10

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.

answered Mar 04 '13 at 09:30

ashutosh

385
4
10

score 6 · Answer 7 · answered Dec 04 '20 at 09:42

6

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

DFS --> S --> Stack

answered Dec 04 '20 at 09:42

Yans Ruan

191
2
4

:D :D :D :D :D :D :D – Yaman Sep 20 '21 at 08:03

score 4 · Answer 8 · answered Nov 25 '18 at 10:58

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.

score 3 · Answer 9 · edited Mar 24 '13 at 06:32

3

Bfs;Breadth=>queue

Dfs;Depth=>stack

Refer to their structure

edited Mar 24 '13 at 06:32

DD_

7,401
11
37
61

answered Mar 24 '13 at 06:16

Subrato

31
1

score 2 · Answer 10 · answered May 06 '16 at 08:36

2

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

DFSS

answered May 06 '16 at 08:36

Yogesh Umesh Vaity

28,478
14
117
88

score 1 · Answer 11 · answered Jul 03 '17 at 13:28

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

score 1 · Answer 12 · answered May 27 '18 at 06:42

1

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

answered May 27 '18 at 06:42

HZhang

166
12

score 0 · Answer 13 · edited May 23 '17 at 12:02

0

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.

edited May 23 '17 at 12:02

Community

1
1

answered Apr 30 '17 at 02:05

arboreal84

2,006
17
21

Yogesh Sanchihar · Answer 14 · 2018-12-08T05:30:36.710

0

You can remember by making an acronym

BQDS

Beautiful Queen has Done Sins.

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

edited Dec 08 '18 at 05:30

answered Jul 28 '18 at 15:30

Yogesh Sanchihar

972
16
23

3

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. – pscl Oct 30 '18 at 08:27
@pscl , Added nmenonic as per you suggestion. – Yogesh Sanchihar Jun 13 '19 at 03:01

score 0 · Answer 15 · answered Nov 12 '20 at 20:55

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

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

15 Answers15