PadhaikoAll subjects

Past exam question: 2063 Baishakh (Regular / Back), Q10

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Graphs

Question

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):

Both run in time using an adjacency list.

Example on Graph (0-1, 0-2, 1-3, 1-4, 2-5) Starting at 0:

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.

All past exam questions for Data Structure and Algorithms