Difference Between BFS and DFS

BFS vs DFS

Breadth First Search (also known as BFS) is a search method used to broaden all the nodes of a particular graph. It accomplishes this task by searching every single solution in order to examine and expand these nodes (or a combination of sequences therein). As such, a BFS does not use a heuristic algorithm (or an algorithm that searches for a solution through multiple scenarios). After all the nodes are obtained, they are added to a queue known as the First In, First Out queue. Those nodes that have not been explored are ‘stored’ in a container marked ‘open’; once explored they are transported to a container marked ‘closed’.

Depth First Search (also known as DFS) is a search method that burrows deeper into a child node of a search until a goal is reached (or until there is a node without any other permutations or ‘children’). After one goal is found, the search backtracks to a previous node that has gone with a solution, repeating the process until all the nodes have been successfully searched. As such, nodes continue to be put aside for further exploration – this is called non-recursive implementation.

The features of the BFS are space and time complexity, completeness, proof of completeness, and optimality. Space complexity refers to the proportion of the number of nodes at the deepest level of a search. Time complexity refers to the actual amount of ‘time’ used for considering every path a node will take in a search. Completeness is, essentially, a search that finds a solution in a graph regardless of what kind of graph it is. The proof of the completeness is the shallowest level at which a goal is found in a node at a definite depth. Finally, optimality refers to a BFS that is not weighted – that is a graph used for unit-step cost.

A DFS is the most natural output using a spanning tree – which is a tree made up of all vertices and some edges in an undirected graph. In this formation, the graph is divided into three classes: Forward edges, pointing from a node to a child node; back edges, pointing from a node to an earlier node; and cross edges, which do not do either one of these.

Summary:

1. A BFS searches every single solution in a graph to expand its nodes; a DFS burrows deep within a child node until a goal is reached.

2. The features of a BFS are space and time complexity, completeness, proof of completeness, and optimality; the most natural output for a DFS is a spanning tree with three classes: forward edges, back edges, and cross edges.

Sharing is caring!