Understanding Search Algorithms: BFS vs. DFS
Search Algorithm Terminologies
Search
Searching is a step-by-step procedure to solve a search problem in a given search space. A search problem can have three main factors:
- Search Space: Search space represents a set of possible solutions, which a system may have.
- Start State: It is a state from where the agent begins the search.
- Goal Test: It is a function that observes the current state and returns whether the goal state is achieved or not.
Search Tree
A tree representation of a search problem is called a search tree. The root of the search tree is the root node, which corresponds to the initial state.
Actions
These describe all the available actions to the agent.
Transition Model
A description of what each action does can be represented as a transition model.
Path Cost
This function assigns a numeric cost to each path.
Solution
An action sequence that leads from the start node to the goal node.
Optimal Solution
A solution with the lowest cost among all solutions.
Properties of Search Algorithms
Following are the four essential properties of search algorithms to compare their efficiency:
Completeness
A search algorithm is said to be complete if it guarantees to return a solution if at least any solution exists for any random input.
Optimality
If a solution found for an algorithm is guaranteed to be the best solution (lowest path cost) among all other solutions, then such a solution is said to be an optimal solution.
Time Complexity
Time complexity is a measure of time for an algorithm to complete its task.
Space Complexity
It is the maximum storage space required at any point during the search, as the complexity of the problem.
BFS
Breadth-first search is the most common search strategy for traversing a tree or graph. This algorithm searches breadthwise in a tree or graph; hence it is called breadth-first search.
The BFS algorithm starts searching from the root node of the tree and expands all successor nodes at the current level before moving to nodes of the next level.
The breadth-first search algorithm is an example of a general-graph search algorithm.
Breadth-first search is implemented using a FIFO queue data structure.
Advantages
- BFS will provide a solution if any solution exists.
- If there are more than one solutions for a given problem, then BFS will provide the minimal solution, which requires the least number of steps.
Disadvantages
- It requires lots of memory since each level of the tree must be saved into memory to expand the next level.
- BFS needs lots of time if the solution is far away from the root node.
DFS
Depth-first search is a recursive algorithm for traversing a tree or graph data structure.
It is called depth-first search because it starts from the root node and follows each path to its greatest depth node before moving to the next path.
DFS uses a stack data structure for its implementation.
The process of the DFS algorithm is similar to the BFS algorithm.
Advantage
- DFS requires very less memory as it only needs to store a stack of the nodes on the path from the root node to the current node.
- It takes less time to reach the goal node than the BFS algorithm (if it traverses in the right path).
Disadvantage
- There is the possibility that many states keep re-occurring, and there is no guarantee of finding the solution.
- The DFS algorithm goes for deep down searching, and sometimes it may go into an infinite loop.