What is the difference between DFS and BFS?

What is BFS?

BFS is generally known as the low level traversal. As we already know that it stands for breadth first search and is mainly used in the queue data structure. In this, we generally take up any node as the root node. It is generally a graph traversal algorithm that begins negotiating the graph from the initial node and inspects all the other nodes as well. After this, it chooses a node which is the closest and then traverses all the other unvisited nodes. When we use Breadth first search algorithm, we can easily use any node and consider them as the root node. There appears to be a lot of other methods as well to approach the graph for the traversal but BFS is known to be the most commonly used. It is generally categorized as a recursive algorithm which implies that it repeats itself. This algorithm is used to find all the vertices and nodes of a tree or graph data structure. This algorithm mainly categorizes a graph into two sub categories that are visited and non-visited. It chooses a single node from anywhere in the graph and then explores all the other adjacent nodes beside the chosen node. The BFS algorithm for a graph is nearly similar to that of a tree with the only difference that a graph might contain cycles in them. In this kind of algorithm, all the adjacent nodes are inquired before moving to the next level. It is based on the mechanism of adding adjacent nodes to the traversal line beginning from the initial node.

What is DFS?

DFS stands for Depth First Search. Generally, it is a repetitive or decidable type of algorithm which is basically used in identifying all the vertices or nodes of a graph or tree data structure. It begins its hunt from the initial node in the graph G and hunts deeper and deeper until it reaches its goal which is also known as the goal node or the node that has no children. Due to its repetitive or to be more precise recursive behavior, the stack data structure is used in order to implement the DFS algorithm.

The stack data structure is generally used for this kind of traversal. The stack data structure works on the LIFO principle. LIFO stands for ‘Last In First Out’. In this type of algorithm, we can generally begin from any given node or anywhere unless and until the root node is mentioned in the problem. We can consider any node as the root node.

The major differences between DFS and BFS

	BFS	DFS
Full Form	It stands for Breadth First Search.	It stands for Depth First Search.
Technique	BFS is considered to be a technique that is based on vertex as it has to find the quickest path.	DFS is considered to be a technique that is based on edge because as we know that the edges are inspected more than the rest of the nodes present.
Definition	It is type of traversal method in which we first inspect all the nodes of a given level and then we move on to the next node or level.	It is also a type of traversal technique where it begins with the root node and then begin investigating every other node till the time we find a particular node that is not visited.
Data Structure	In this, queue data structure is usually used for the traversal technique.	In this, stack data structure is usually used for the traversal technique.
Bachtracking	Backtracking is not possible in this type of traversal.	Backtracking is possible in this type of traversal. It generally uses this method to check all the unexplored nodes.
Number of edges	As we know, BFS is known for searching the quickest path and so it contains a minimum number of edges from the beginning itself.	Whereas in DFS, there are a lot of edges needed to commute from the first node to the final node.
Optimality	This kind of traversal is great for the kind of vertex that is closer to the origin vertex.	This kind of traversal is great for the kind of graphs that are at a certain distance to the origin vertex.
Speed	It is known that BFS is much slower than DFS.	It is known that DFS is much quicker and efficient than BFS.
Decision tree	BFS traversal is known to be not valid for the decision tree as it requires individual visit to all the adjacent nodes initially.	DFS traversal is known to be valid for the decision tree as it visits every path individually which helps in finding the goal.
Memory	This type of traversal technique is known to be less efficient in terms of memory as it has more memory requirement as compared to DFS.	This type of traversal technique is known to be more efficient in terms of memory as it has less memory requirement as compared to BFS.