Traversal is a process of visiting all the edges and vertices in a graph.

There are two main Traversal Algorithms:

1. Breadth First Search [BFS]
2. Depth First Search [DFS]

Breadth First Search

Breadth-first search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving to the next level. It starts at a given source vertex and systematically explores all the vertices reachable from the source.

Depth-First Search

Depth-first search (DFS) is a graph traversal algorithm that explores all the vertices of a graph by going as deep as possible before backtracking. It starts at a given source vertex and systematically explores all the vertices reachable from the source.

COMPARISON BETWEEN BFS & DFS:

**** | Breadth-first search | Depth- first search
-------------------------|---------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------- Goal | Visit all nodes in breadth-first order | Visit all nodes in depth-first order
Order of traversal | Explore vertices in the order of their distance from the source | Explore vertices as deeply as possible before backtracking
Data Structure Used | Queue | Stack
Memory Efficiency | Requires more memory as it needs to store all the vertices at the current level | Requires less memory as it only needs to store the path from the source to the current vertex Shortest Path | Guarantees finding the shortest path in an unweighted graph | Does not guarantee finding the shortest path
Application | Shortest path algorithms, connectivity analysis, finding all reachable vertices | Topological sorting, cycle detection, maze solving