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

I always mix up whether I use a stack or a queue for DFS开发者_如何学C or BFS. Can someone please provide some intuition about how to remember which algorithm uses which data structure?

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.

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

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.

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)

Take it in Alphabetical order...

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

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

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.

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

DFS --> S --> Stack

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.

Bfs;Breadth=>queue

Dfs;Depth=>stack

Refer to their structure

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

DFSS

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.

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

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.

You can remember by making an acronym

BQDS

Beautiful Queen has Done Sins.

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

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

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.