Breadth First Vs Depth First

Question

When Traversing a Tree Graph what is the difference between Breadth First and Depth first  Any coding or pseudocode examples would be great

User · Answer

I think it would be interesting to write both of them in a way that only by switching some lines of code would give you one algorithm or the other, so that you will see that your dillema is not so strong as it seems to be at first.

I personally like the interpretation of BFS as flooding a landscape: the low altitude areas will be flooded first, and only then the high altitude areas would follow. If you imagine the landscape altitudes as isolines as we see in geography books, its easy to see that BFS fills all area under the same isoline at the same time, just as this would be with physics. Thus, interpreting altitudes as distance or scaled cost gives a pretty intuitive idea of the algorithm.

With this in mind, you can easily adapt the idea behind breadth first search to find the minimum spanning tree easily, shortest path, and also many other minimization algorithms.

I didnt see any intuitive interpretation of DFS yet (only the standard one about the maze, but it isnt as powerful as the BFS one and flooding), so for me it seems that BFS seems to correlate better with physical phenomena as described above, while DFS correlates better with choices dillema on rational systems (ie people or computers deciding which move to make on a chess game or going out of a maze).

So, for me the difference between lies on which natural phenomenon best matches their propagation model (transversing) in real life.

User · Answer

These two terms differentiate between two different ways of walking a tree   It is probably easiest just to exhibit the difference  Consider the tree       A          B   C          D   E   F   A depth first traversal would visit the nodes in this order  A  B  D  C  E  F   Notice that you go all the way down one leg before moving on   A breadth first traversal would visit the node in this order  A  B  C  D  E  F   Here we work all the way across each level before going down    Note that there is some ambiguity in the traversal orders  and I ve cheated to maintain the  reading  order at each level of the tree  In either case I could get to B before or after C  and likewise I could get to E before or after F  This may or may not matter  depends on you application        Both kinds of traversal can be achieved with the pseudocode   Store the root node in Container While  there are nodes in Container     N   Get the  next  node from Container    Store all the children of N in Container    Do some work on N   The difference between the two traversal orders lies in the choice of Container     For depth first use a stack   The recursive implementation uses the call-stack     For breadth-first use a queue      The recursive implementation looks like  ProcessNode Node     Work on the payload Node    Foreach child of Node       ProcessNode child        Alternate time to work on the payload Node  see below       The recursion ends when you reach a node that has no children  so it is guaranteed to end for finite  acyclic graphs     At this point  I ve still cheated a little  With a little cleverness you can also work-on the nodes in this order   D  B  E  F  C  A   which is a variation of depth-first  where I don t do the work at each node until I m walking back up the tree  I have however visited the higher nodes on the way down to find their children   This traversal is fairly natural in the recursive implementation  use the  Alternate time  line above instead of the first  Work  line   and not too hard if you use a explicit stack  but I ll leave it as an exercise

User · Answer

Given this binary tree      Breadth First Traversal  Traverse across each level from left to right      I m G  my kids are D and I  my grandkids are B  E  H and K  their grandkids are A  C  F   - Level 1  G  - Level 2  D  I  - Level 3  B  E  H  K  - Level 4  A  C  F  Order Searched  G  D  I  B  E  H  K  A  C  F   Depth First Traversal  Traversal is not done ACROSS entire levels at a time  Instead  traversal dives into the DEPTH  from root to leaf  of the tree first  However  it s a bit more complex than simply up and down   There are three methods    1  PREORDER  ROOT  LEFT  RIGHT  You need to think of this as a recursive process    Grab the Root   G    Then Check the Left   It s a tree    Grab the Root of the Left   D    Then Check the Left of D   It s a tree    Grab the Root of the Left  B    Then Check the Left of B   A    Check the Right of B   C  and it s a leaf node  Finish B tree  Continue D tree    Check the Right of D   It s a tree    Grab the Root   E    Check the Left of E   Nothing    Check the Right of E   F  Finish D Tree  Move back to G Tree    Check the Right of G   It s a tree    Grab the Root of I Tree   I    Check the Left   H  it s a leaf     Check the Right   K  it s a leaf  Finish G tree    DONE  G  D  B  A  C  E  F  I  H  K    2  INORDER  LEFT  ROOT  RIGHT Where the root is  in  or between the left and right child node    Check the Left of the G Tree   It s a D Tree    Check the Left of the D Tree   It s a B Tree    Check the Left of the B Tree   A    Check the Root of the B Tree  B    Check the Right of the B Tree  C  finished B Tree     Check the Right of the D Tree  It s a E Tree    Check the Left of the E Tree   Nothing    Check the Right of the E Tree   F  it s a leaf  Finish E Tree  Finish D Tree       Onwards until       DONE  A  B  C  D  E  F  G  H  I  K    3  POSTORDER   LEFT  RIGHT  ROOT   DONE  A  C  B  F  E  D  H  K  I  G   Usage  aka  why do we care   I really enjoyed this simple Quora explanation of the Depth First Traversal methods and how they are commonly used   In-Order Traversal will print values  in order for the BST  binary search tree     Pre-order traversal is used to create a copy of the  binary search tree     Postorder traversal is used to delete the  binary search tree    https   www quora com What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

User · Answer

Understanding the terms   This picture should give you the idea about the context in which the words breadth and depth are used       Depth-First Search      Depth-first search algorithm acts as if it wants to get as far away from the starting point as quickly as possible  It generally uses a Stack to remember where it should go when it reaches a dead end  Rules to follow  Push first vertex A on to the Stack   If possible  visit an adjacent unvisited vertex  mark it as visited  and push it on the stack  If you can   t follow Rule 1  then  if possible  pop a vertex off the stack  If you can   t follow Rule 1 or Rule 2  you   re done   Java code   public void searchDepthFirst            Begin at vertex 0  A      vertexList 0  wasVisited   true      displayVertex 0       stack push 0       while   stack isEmpty              int adjacentVertex   getAdjacentUnvisitedVertex stack peek                If no such vertex         if  adjacentVertex    -1                stack pop              else               vertexList adjacentVertex  wasVisited   true                 Do something             stack push adjacentVertex                          Stack is empty  so we re done  reset flags     for  int j   0  j  lt  nVerts  j            vertexList j  wasVisited   false     Applications  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      Breadth-First Search      The breadth-first search algorithm likes to stay as close as possible to the starting point  This kind of search is generally implemented using a Queue  Rules to follow  Make starting Vertex A the current vertex   Visit the next unvisited vertex  if there is one  that   s adjacent to the current vertex  mark it  and insert it into the queue  If you can   t carry out Rule 1 because there are no more unvisited vertices  remove a vertex from the queue  if possible  and make it the current vertex  If you can   t carry out Rule 2 because the queue is empty  you   re done   Java code   public void searchBreadthFirst         vertexList 0  wasVisited   true      displayVertex 0       queue insert 0       int v2      while   queue isEmpty              int v1   queue remove               Until it has no unvisited neighbors  get one         while   v2   getAdjUnvisitedVertex v1      -1                vertexList v2  wasVisited   true                 Do something             queue insert v2                          Queue is empty  so we re done  reset flags     for  int j   0  j  lt  nVerts  j             vertexList j  wasVisited   false     Applications  Breadth-first search 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    Hopefully that should be enough for understanding the Breadth-First and Depth-First searches  For further reading I would recommend the Graphs chapter from an excellent data structures book by Robert Lafore

[algorithm] Breadth First Vs Depth First

Examples related to algorithm

Examples related to depth-first-search

Examples related to breadth-first-search

Examples related to tree-traversal