Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 or BFS. Can someone please provide some intuition about how to remember which algorithm uses which data structure?

like image 410
captcadaver Avatar asked Oct 14 '10 00:10

captcadaver


People also ask

Which data structures are used in BFS and DFS algorithm?

BFS(Breadth First Search) uses Queue data structure for finding the shortest path. DFS(Depth First Search) uses Stack data structure.

Which data structure is used for DFS how it works?

The depth-first search (DFS) algorithm starts with the initial node of graph G and goes deeper until we find the goal node or the node with no children. Because of the recursive nature, stack data structure can be used to implement the DFS algorithm.

Which data structure is used for implementing DFS?

Depth First Search (DFS) uses Stack data structure.


1 Answers

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.

like image 188
Sai Kumar Battinoju Avatar answered Oct 23 '22 07:10

Sai Kumar Battinoju