Breadth First Search (BFS):
A graph's Breadth-First Traversal (or Search) is comparable to a tree's Breadth-First Traversal. The one catch is that, unlike trees, graphs can contain cycles, allowing us to return to the same node. To prevent processing a node several times, we separate the vertices into two groups:
- Visited and
- Not visited.
A boolean visited array marks the visited vertices. For the sake of simplicity, all vertices are believed to be reachable from the initial vertex. For traversal, BFS employs a queue data structure.
BFS (Breadth First Search)
1, 2, 5, 4, 7, 6, 3- Level order traversal
Depth First Search (BFS):
Depth First Search (DFS) is an edge-based technique. It employs the Stack data structure and operates in two stages: first, visited vertices are pushed into the stack, and then if no vertices are found, visited vertices are popped.
DFS (Depth First Search)
1, 2, 4, 5, 3, 6, 7- Pre order traversal
BFS: 1, 4, 2, 3, 5, 8, 7, 10, 6
DFS: 1, 4, 3, 10, 9, 2, 8, 7, 5, 6
Difference between BFS and DFS
