# What is the difference between Breadth-First Search and Depth-First Search?

 0 I know that Breadth-first search & Depth-first search both of them are Uniformed Search, but what are the differences between them? asked 11 Oct '11, 15:46 AUnshur 180●1●1●8 Merlin 4.2k●5●14●29 Make sure you don't forget your second 'n'! UniNformed search...not to be confused with uniform cost search. (17 Oct '11, 08:44) laconic

 5 In a Breadth-first search you explore each node at a given depth before moving on the the next level. So if you have a tree:  A B C D E F G  The search path would be A-B-C-D-E-F-G. Depth first search explores all the way to the bottom of a path before moving backtracking up to another higher level child. so for the same tree the search path would be A-B-D-E-C-F-G. answered 11 Oct '11, 16:15 EdK ♦ 3.3k●5●11●34 This assumes that ties are broken by choosing the left most node. The search path would be different with alternate tie-breaking choices. The logic is right, though. (17 Oct '11, 08:47) laconic
 3 Breath first is a careful search where you equally progress in all possible directions. If the goal is out there somewhere you will find it. Depth first is a more aggressive and risk taking search where you choose one path and ignore all the other paths until you reach the end of your chosen path. If there is no end to that path you will continue forever which is why this approach is incomplete. answered 11 Oct '11, 16:41 kindtb 420●3●13
 0 take a look at videos 2.18-2.21. peter compares BFS and DFS (and UCS) with respect to optimality, completeness, and storage/memory costs; he also shows the traversal orders for each. BFS is optimal and complete, but the frontier can get very large (O(2^n) nodes stored at level n in the search tree). DFS is neither optimal nor complete but you can store fewer nodes. Basically you end up storing your current path from the start state to the current node that you are expanding. So if you're at level n in the search tree, you're storing O(n) nodes. Note that DFS could be complete if you store enough nodes in the explored list to avoid all repeated states, but that increases your storage costs. answered 11 Oct '11, 16:18 nierman 341●3●8
 0 here is a nice animation in wikipedia explaining the idea of Breadth-first search: http://en.wikipedia.org/wiki/File:Animated_BFS.gif answered 11 Oct '11, 17:28 hamda 1●1
 0 Hello, if we follow http://en.wikipedia.org/wiki/Depth-first_search then your A-B-C-D-E-F-G is correct. If we follow pages 86-86 from Artificial Intelligence - A modern approach - Russel-Norving 3rd edition, then it would be (from Left->Right) A-B-F-G-D-E, as the remove_choice is based on a FIFO queue. answered 17 Oct '11, 08:43 Comment on the answer you are referring to. This is not a stand-alone answer. (17 Oct '11, 08:58) laconic
 0 Although the implementation may be different (data structures, recursion vs. iteration, etc.) you can think of the way things working in this way. In BFS, children get added to a queue (FIFO) to be expanded. In DFS, children get added to a stack (LIFO). Notice how this causes deeper and deeper children to be explored first in DFS because those last nodes in are the ones you are going to expand first. Alternatively, BFS will expand children at the same depth-level first (they will be older in the queue than the next depth-level's children) before moving on to deeper children. answered 17 Oct '11, 09:08 laconic 492●9
 toggle preview community wiki