How fast is dfs

Can someone please explain what, and how are the speed and memory requirements different? Memory requirements : The stack size is bound by the depth whereas the queue size is bound by the width. For a balanced binary tree with n nodes, that means the stack size would be log n but the queue size would b O n. Note that an explicit queue might not be needed for a BFS in all cases -- for instance, in an array embedded binary tree, it should be possible to compute the next index instead.

Speed : I don't think that's true. For a full search, both cases visit all the nodes without significant extra overhead. If the search can be aborted when a matching element is found, BFS should typically be faster if the searched element is typically higher up in the search tree because it goes level by level.

DFS might be faster if the searched element is typically relatively deep and finding one of many is sufficient. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Collectives on Stack Overflow. Learn more. Ask Question. Asked 4 years ago. Active 10 months ago.

Viewed 7k times. Improve this question. Dominique Fortin 2, 13 13 silver badges 20 20 bronze badges. Shreyas Pimpalgaonkar Shreyas Pimpalgaonkar 2 2 silver badges 16 16 bronze badges.

Please provide a reference. The truth, as with many things in computer science, is "it depends on the graph. Add a comment. Active Oldest Votes. Improve this answer. Stefan Haustein Stefan Haustein 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. 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. 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:. 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. 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. Python Javascript Linux Cheat sheet Contact. If solutions are frequent but located deep in the tree, BFS could be impractical. But these are just rules of thumb; you'll probably need to experiment.

Depth-first Search Depth-first searches are often used in simulations of games and game-like situations in the real world. 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. 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.