Breadth-First Search (BFS) and Depth-First Search (DFS) are algorithms for traversing graphs. Traversal is the process of accessing each vertex (node) of a data structure in a systematic well-defined order. Choosing the algorithm depends on the type of data you are dealing with.
There are generally two types of traversal and the main difference between them is in the order they access nodes:
- Breadth-first search
- Depth-first search
Breadth-first search (BFS) is a traversing algorithm which starts from a selected node (source or starting node) and explores all of the
Breadth-first search can be implemented using a queue data structure, which follows the first-in-first-out (FIFO) method – i.e., the node that was inserted first will be visited first, and so on.
We start the process by considering any random node as the starting vertex. We enqueue (insert) it to the queue and mark it as visited. Then we mark and enqueue all of its unvisited neighbours at the current depth or continue to the next depth level if there is any. The visited vertices are removed from the queue. The process ends when the queue becomes empty.
Example of applications:
- Check if a graph is connected
- Generating spanning tree
- Finding the shortest path in a graph
Depth-first search (DFS) is a traversing algorithm that uses the opposite strategy of breadth-first search. It explores the highest-depth nodes first before backtracking and expanding shallower nodes.
Depth-first search can be implemented using a stack data structure, which follows the last-in-first-out (LIFO) method – i.e., the node that was inserted last will be visited first.
First, we select any random node as a starting vertex. We push it onto the stack and mark it as visited. Then we explore it as far as possible in a branch and push its unvisited neighbour nodes onto the stack. If there aren’t any unvisited nodes left, we come back to a fixed point (backtrack). The visited vertices are pushed onto the stack and later when there is no vertex further to visit those are popped-off. The process ends when the stack becomes empty.
Examples of application:
- Testing connectivity
- Finding a path between two nodes
- Solving puzzles
- BFS visits all of the neighbours before visiting children nodes. DFS visits all children nodes before visiting neighbours.
- For implementation, BFS uses a queue data structure, while DFS uses a stack.
- BFS uses a larger amount of memory because it expands all children of a vertex and keeps them in memory. It stores the pointers to a level’s child nodes while searching each level to remember where it should go when it reaches a leaf node. DFS has much lower memory requirements than BFS because it iteratively expands only one child until it cannot proceed anymore and backtracks thereafter. It has to remember a single path with unexplored nodes.
- Both have the same O(n) time complexity, but BFS is “better” at finding the shortest path in a graph, while DFS is “better” at answering connectivity queries (determining if every pair of vertices can be connected by two disjoint paths).
Choosing between both algorithms depends on the structure of the search tree and the number and location of the solutions. If the solution is mostly in the neighbourhood of the current node it is better to choose BFS. If it is most likely the farthest descendant of a node then choosing a DFS is a better option. If the graph is dense and your average number of neighbours is high relative to the number of nodes, a breadth-first search will have long queues while depth-first will have small stacks. In sparse graphs, the situation is reversed. In conclusion, if memory is a limiting factor, the shape of the graph may have to inform your choice of a search strategy.