Breadth First Search vs Depth First Search

Depth First Search (DFS) and Breadth First Search (BFS) are search algorithms used for graphs and trees. When you have an ordered tree or graph, like a Binary Search Tree, it’s quite easy to search the data structure to find the node that you want. However, when given an unordered tree or graph, the BFS and DFS search algorithms can come in handy to find what you’re looking for. The decision to choose one over the other should be based on the type of data that one is dealing with.

In a breadth first search, you start at the root node, and then scan each node in the first level starting from the leftmost node, moving towards the right. Then you continue scanning the second level (starting from the left) and the third level, and so on until you’ve scanned all the nodes, or until you find the actual node that you were searching for. In a BFS, when traversing one level, we need some way of knowing which nodes to traverse once we get to the next level. The way this is done is by storing the pointers to a level’s child nodes while searching that level. The pointers are stored in FIFO (First-In-First-Out) queue. This, in turn, means that BFS uses a large amount of memory because we have to store the pointers.

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.

DFS running time

• DFS has a running time of n+e (n=vertices, e=edges) in a directed graph.
• DFS for an undirected graph has a running time of n+2e as each edge is traversed in both directions.
• Time required is theta(V+E) and not just O(V+E) since we’re guaranteed to examine every vertex and edge.
• DFS search requires the use of a stack while a queue is used for BFS

BFS running time

• The operation of enqueuing and dequeuing takes O(1) time, and so the total time devoted to queue operations is O(V)
• Because the procedure scans the adjacency list of each vertex only when the vertex is dequeued, it scans each adjacency list at most once.
• Since the sum of the lengths of all the adjacency lists is theta(E), the total time spent in scanning adjacency lists is O(E).
• The overhead for initialisation is O(V)

The total running time for BFS is O(V+E) Structure of the tree and the number and locations of solutions determines which one to use. If a solution is not far from root of tree, a BFS would be better – if the tree is very deep and solutions are rare then DFS might take an extremely long time. IF the tree is very wide, a BFS might need too much memory, and might become impractical. If solutions are frequent but located deep in the tree, BFS could be impractical.If the search tree is very deep one might need to restrict the search depth for DFS anyway.

Comments: