Past exam question: 2063 Baishakh (Regular / Back), Q10
Open in the Padhaiko appQuestion
How the depth first search algorithm and breadth first search algorithm are implemented? Explain with suitable example.
Solution
Implementation of Depth-First Search (DFS) & Breadth-First Search (BFS):
- DFS (Stack / Recursion): Maintains a
visited[]array; pushes start vertexsonto a stack (or callsDFS(s)recursively), marks it visited, and repeatedly visits an unvisited neighbor before backtracking. - BFS (FIFO Queue): Maintains
visited[]and a queueQ; markssvisited, enqueuess, and in awhile (!isEmpty(Q))loop dequeuesuand enqueues all unvisited neighbors ofu(marking them visited upon enqueue).
Both run in time using an adjacency list.
Example on Graph (0-1, 0-2, 1-3, 1-4, 2-5) Starting at 0:
- DFS Order:
0 -> 1 -> 3 -> 4 -> 2 -> 5(deepest branch first via stack/recursion). - BFS Order:
0 -> 1 -> 2 -> 3 -> 4 -> 5(level 0:{0}, level 1:{1, 2}, level 2:{3, 4, 5}via queue).
Answer:
DFS uses recursion or a Stack (0, 1, 3, 4, 2, 5), while BFS uses a FIFO Queue (0, 1, 2, 3, 4, 5), both visiting every reachable vertex and edge in time.