When is it practical to use Depth-First Search DFS vs Breadth-First Search BFS

Question

I understand the differences between DFS and BFS  but I m interested to know when it s more practical to use one over the other    Could anyone give any examples of how DFS would trump BFS and vice versa

User · Answer

This is a good example to demonstrate that BFS is better than DFS in certain case. https://leetcode.com/problems/01-matrix/

When correctly implemented, both solutions should visit cells that have farther distance than the current cell +1. But DFS is inefficient and repeatedly visited the same cell resulting O(n*n) complexity.

For example,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,

User · Answer

Nice Explanation from  http   www programmerinterview com index php data-structures dfs-vs-bfs      An example of BFS   Here   s an example of what a BFS would look like  This is something like Level Order Tree Traversal where we will use QUEUE with ITERATIVE approach  Mostly RECURSION will end up with DFS   The numbers represent the order in which the nodes are accessed in a BFS     In a depth first search  you start at the root  and follow one of the branches of the tree as far as possible until either the node you are looking for is found or you hit a leaf node   a node with no children   If you hit a leaf node  then you continue the search at the nearest ancestor with unexplored children      An example of DFS   Here   s an example of what a DFS would look like  I think post order traversal in binary tree will start work from the Leaf level first  The numbers represent the order in which the nodes are accessed in a DFS        Differences between DFS and BFS   Comparing BFS and DFS  the big advantage of DFS is that it has much lower memory requirements than BFS  because it   s not necessary to store all of the child pointers at each level  Depending on the data and what you are looking for  either DFS or BFS could be advantageous   For example  given a family tree if one were looking for someone on the tree who   s still alive  then it would be safe to assume that person would be on the bottom of the tree  This means that a BFS would take a very long time to reach that last level  A DFS  however  would find the goal faster  But  if one were looking for a family member who died a very long time ago  then that person would be closer to the top of the tree  Then  a BFS would usually be faster than a DFS  So  the advantages of either vary depending on the data and what you   re looking for   One more example is Facebook  Suggestion on Friends of Friends  We need immediate friends for suggestion where we can use BFS  May be finding the shortest path or detecting the cycle  using recursion  we can use DFS

User · Answer

I think it depends on what problems you are facing     shortest path on simple graph -  bfs all possible results -  dfs search on graph treat tree  martix as a graph too  -  dfs

User · Answer

Some algorithms depend on particular properties of DFS  or BFS  to work  For example the Hopcroft and Tarjan algorithm for finding 2-connected components takes advantage of the fact that each already visited node encountered by DFS is on the path from root to the currently explored node

User · Answer

One important advantage of BFS would be that it can be used to find the shortest path between any two nodes in an unweighted graph  Whereas  we cannot use DFS for the same

User · Answer

When tree width is very large and depth is low use DFS as recursion stack will not overflow Use BFS when width is low and depth is very large to traverse the tree

User · Answer

DFS is more space-efficient than BFS  but may go to unnecessary depths   Their names are revealing  if there s a big breadth  i e  big branching factor   but very limited depth  e g  limited number of  moves    then DFS can be more preferrable to BFS     On IDDFS  It should be mentioned that there s a less-known variant that combines the space efficiency of DFS  but  cummulatively  the level-order visitation of BFS  is the iterative deepening depth-first search  This algorithm revisits some nodes  but it only contributes a constant factor of asymptotic difference

User · Answer

When you approach this question as a programmer  one factor stands out  if you re using recursion  then depth-first search is simpler to implement  because you don t need to maintain an additional data structure containing the nodes yet to explore  Here s depth-first search for a non-oriented graph if you re storing    already visited    information in the nodes  def dfs origin                                   DFS from origin      origin visited   True                        Mark the origin as visited     for neighbor in origin neighbors             Loop over the neighbors         if not neighbor visited  dfs neighbor    Visit each neighbor if not already visited  If storing    already visited    information in a separate data structure  def dfs node  visited                            DFS from origin  with already-visited set      visited add node                             Mark the origin as visited     for neighbor in node neighbors               Loop over the neighbors         if not neighbor in visited               If the neighbor hasn t been visited yet              dfs neighbor  visited                then visit the neighbor dfs origin  set     Contrast this with breadth-first search where you need to maintain a separate data structure for the list of nodes yet to visit  no matter what

User · Answer

Depth-first Search  Depth-first searches are often used in simulations of games  and game-like situations in the real world   In a typical game you can choose one of several possible actions  Each choice leads to further choices  each of which leads to further choices  and so on into an ever-expanding tree-shaped graph of possibilities     For example in games like Chess  tic-tac-toe when you are deciding what move to make  you can mentally imagine a move  then your opponent   s possible responses  then your responses  and so on  You can decide what to do by seeing which move leads to the best outcome   Only some paths in a game tree lead to your win  Some lead to a win by your opponent  when you reach such an ending  you must back up  or backtrack  to a previous node and try a different path  In this way you explore the tree until you find a path with a successful conclusion  Then you make the first move along this path     Breadth-first search  The breadth-first search has an interesting property  It first finds all the vertices that are one edge away from the starting point  then all the vertices that are two edges away  and so on  This is useful if you   re trying to find the shortest path from the starting vertex to a given vertex  You start a BFS  and when you find the specified vertex  you know the path you   ve traced so far is the shortest path to the node  If there were a shorter path  the BFS would have found it already   Breadth-first search can be used for finding the neighbour nodes in peer to peer networks like BitTorrent  GPS systems to find nearby locations  social networking sites to find people in the specified distance and things like that

User · Answer

Breadth First Search is generally the best approach when the depth of the tree can vary  and you only need to search part of the tree for a solution  For example  finding the shortest path from a starting value to a final value is a good place to use BFS   Depth First Search is commonly used when you need to search the entire tree  It s easier to implement  using recursion  than BFS  and requires less state  While BFS requires you store the entire  frontier   DFS only requires you store the list of parent nodes of the current element

User · Answer

For BFS  we can consider Facebook example  We receive suggestion to add friends from the FB profile from other other friends profile  Suppose A- B  while B- E and B- F  so A will get suggestion for E And F  They must be using BFS to read till second level  DFS is more based on scenarios where we want to forecast something based on data we have from source to destination  As mentioned already about chess or sudoku  Once thing I have different here is  I believe DFS should be used for shortest path because DFS will cover the whole path first then we can decide the best  But as BFS will use greedy s approach so might be it looks like its the shortest path  but the final result might differ   Let me know whether my understanding is wrong

User · Answer

That heavily depends on the structure of the search tree and the number and location of solutions  aka searched-for items    If you know a solution is not far from the root of the tree  a breadth first search  BFS  might be better   If the tree is very deep and solutions are rare  depth first search  DFS  might take an extremely long time  but BFS could be faster   If the tree is very wide  a BFS might need too much memory  so it might be completely impractical   If solutions are frequent but located deep in the tree  BFS could be impractical   If the search tree is very deep you will need to restrict the search depth for depth first search  DFS   anyway  for example with iterative deepening     But these are just rules of thumb  you ll probably need to experiment  Another issue is parallelism  if you want to parallelize BFS you would need a shared datastructure between threads  which is a bad thing  DFS might be easier to distribute even between connected machines if you don t insist on the exact order of visiting the nodes

User · Answer

The following is a comprehensive answer to what you are asking   In simple terms   Breadth First Search  BFS  algorithm  from its name  Breadth   discovers all the neighbours of a node through the out edges of the node then it discovers the unvisited neighbours of the previously mentioned neighbours through their out edges and so forth  till all the nodes reachable from the origional source are visited  we can continue and take another origional source if there are remaining unvisited nodes and so forth   That s why it can be used to find the shortest path  if there is any  from a node  origional source  to another node if the weights of the edges are uniform   Depth First Search  DFS  algorithm  from its name  Depth   discovers the unvisited neighbours of the most recently discovered node x through its out edges  If there is no unvisited  neighbour from the node x  the algorithm backtracks to discover the unvisited neighbours of the node  through its out edges  from which node x was discovered  and so forth  till all the nodes reachable from the origional source are visited  we can continue and take another origional source if there are remaining unvisited nodes and so forth    Both BFS and DFS can be incomplete  For example if the branching factor of a node is infinite  or very big for the resources  memory  to support  e g  when storing the nodes to be discovered next   then BFS is not complete even though the searched key can be at a distance of few edges from the origional source  This infinite branching factor can be because of infinite choices  neighbouring nodes  from a given node to discover   If the depth is infinite  or very big for the resources  memory  to support  e g  when storing the nodes to be discovered next   then DFS is not complete even though the searched key can be the third neighbor of the origional source  This infinite depth can be because of a situation where there is  for every node the algorithm discovers  at least a new choice  neighbouring node  that is unvisited before   Therefore  we can conclude when to use the BFS and DFS  Suppose we are dealing with a manageable limited branching factor and a manageable limited depth  If the searched node is shallow i e  reachable after some edges from the origional source  then it is better to use BFS  On the other hand  if the searched node is deep i e  reachable after a lot of edges from the origional source  then it is better to use DFS   For example  in a social network if we want to search for people who have similar interests of a specific person  we can apply BFS from this person as an origional source  because mostly these people will be his direct friends or friends of friends i e  one or two edges far  On the other hand  if we want to search for people who have completely different interests of a specific person  we can apply DFS from this person as an origional source  because mostly these people will be very far from him i e  friend of friend of friend     i e  too many edges far   Applications of BFS and DFS can vary also because of the mechanism of searching in each one  For example  we can use either BFS  assuming the branching factor is manageable  or DFS  assuming the depth is manageable  when we just want to check the reachability from one node to another having no information where that node can be  Also both of them can solve same tasks like topological sorting of a graph  if it has   BFS can be used to find the shortest path  with unit weight edges  from a node  origional source  to another  Whereas  DFS can be used to exhaust all the choices because of its nature of going in depth  like discovering the longest path between two nodes in an acyclic graph  Also DFS  can be used for cycle detection in a graph   In the end if we have infinite depth and infinite branching factor  we can use Iterative Deepening Search  IDS

User · Answer

According to the properties of DFS and BFS  For example when we want to find the shortest path  we usually use bfs it can guarantee the  shortest   but dfs only can guarantee that we can come from this point can achieve that point  can not guarantee the  shortest

User · Answer

Because Depth-First Searches use a stack as the nodes are processed  backtracking is provided with DFS   Because Breadth-First Searches use a queue  not a stack  to keep track of what nodes are processed  backtracking is not provided with BFS

[algorithm] When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

Examples related to algorithm

Examples related to graph-algorithm

Examples related to graph-theory

Examples related to depth-first-search

Examples related to breadth-first-search