FOLLOW ON GOOGLE NEWS
bfs and dfs in ai

DFS and BFS in AI and their Control Strategies

What is BFS?

BFS stands for Breadth First Searchlevel order traversal). Breadth First Traversal uses Queue data structure. While DFS is exactly opposite. When we use the BFS algorithm for the traversal in a graph, we can consider any node as a root node.

BFS vs. DFS
image source: javatpoint.com

What is DFS?

DFS stands for Depth First Search. Depth First Search uses Stack data structure and it works on LIFO(Last in First Out) principle. In DFS, traversing can be started from any node, or we can say that any node can be considered as a root node until the root node is not mentioned in the problem.

BFS vs. DFS
Image source: javatpoint.com

BFS Vs DFS

The difference between Breadth First Search and Depth First Search is given below:-

Full form BFS stands for Breadth First Search. DFS stands for Depth First Search.
Technique It a vertex-based technique to find the shortest path in a graph. It is an edge-based technique because the vertices along the edge are explored first from the starting to the end node.
Definition

In BFS it explores all the nodes of the same level and then move to the next level.

DFS is also a traversal technique in which traversal is started from the root node and explore the nodes as far as possible until we reach the node that has no unvisited adjacent nodes.
Data Structure It uses Queue data structure to traverse the vertex. It uses Stack data structure to traverse the graph.
Backtracking BFS does not use the backtracking concept. DFS uses backtracking to traverse all the unvisited nodes.
Number of edges BFS finds the shortest path having a minimum number of edges to traverse. In DFS, a greater number of edges are required to traverse from the source vertex to the destination vertex. 
Optimality BFS traversal is optimal for those vertices which are to be searched closer to the source vertex.  DFS traversal is optimal for those graphs in which solutions are away from the source vertex.
Speed BFS is slower than DFS. DFS is faster than BFS.
Suitability for decision tree It is not suitable for the decision tree because it requires exploring all the neighbouring nodes first. It is suitable for the decision tree. Based on the decision, it explores all the paths.
Memory efficient It is not memory efficient as it requires more memory than DFS. It is memory efficient as it requires less memory than BFS.

Control Strategies of BFS and DFS

In an artificial intelligence situation, a control strategy is a technique or approach that instructs us on which rule needs to be implemented next while looking for a solution within the problem space. It aids us in choosing the subsequent rule that must be applied so that we never get stuck. These guidelines determine our method of attack, how soon a problem is resolved, and even whether a problem is ever truly resolved.

When there are multiple rules or fewer rules for finding the answer at each point in the issue space, the control strategy aids in solving the problem. A successful control strategy involves two key elements:

1. Control Strategy should cause Motion

Each rule or strategy applied should cause motion, because if there is no motion, then such a control strategy will never lead to a solution. The motion states the change of state and if a state does not change, then there will be no movement from an initial state and we will never solve the problem.

2. Control Strategy should be Systematic

Though the strategy applied should create the motion, if we do not follow some systematic strategy, we are likely to reach the same state a number of times before reaching the solution, which increases the number of steps.  Taking care of only the first strategy, we may go through particular useless sequences of operators several times.  A control strategy should be systematic, implying a need for global motion (over the course of several steps) as well as for local motion (over the course of a single step).

Examples:

Control_Strategy_ AI
image source: electronicsmedia.info
  • Breadth-First Search: It searches along the breadth and follows a first-in-first-out queue data structure approach.  It will start to scan node A first and then B-C-D-E-F.
  • Depth-First Search:  It searches along the depth and follows the stack approach. The sequence for scanning nodes will be A-B-D-E-C-F, it scans all the sub-nodes of parent nodes and then moves to another node.

Widely used Control Strategies are Breadth-First Search, Depth-First Search, Generate and Test, Hill-Climbing, Best-first search, Problem Reduction and many more.

Watch video for better clarity of concept.

This video has been taken from Abdul Bari’s YouTube channel, we thank them for this, you can subscribe to their channel.