Edit page

BFS & DFS

BFS (level order traversal) is a vertex based technique for finding a shortest path in tree. It uses a Queue data structure which follows first in first out. In BFS, one node is selected at a time when it is visited and marked then its adjacent are visited and stored in the queue. It is slower than DFS. [Source: Geeksforgeeks]

It starts traversing from a selected node (source or starting node) and traverse the tree layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.

DFS is a edge based technique. It uses the Stack data structure, performs two stages, first visited nodes are pushed into stack and second if there is no node then visited nodes are popped.

The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking.

References

  • Geeksforgeeks
  • YouTube

BFS

DFS