PadhaikoAll subjects

Past exam question: 2072 Ashwin (Regular), Q13

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Graphs

Question

Explain a breadth first traversal in graph with suitable example. Explain Kruskal's algorithm to find minimum spanning tree with suitable example.

Solution

Breadth-First Traversal (BFS) with Example: BFS explores a graph level by level from a start vertex using a Queue:

  1. Mark visited and enqueue .
  2. While the queue is non-empty, dequeue , visit it, and enqueue all unvisited neighbors of (marking them visited).

Example: On undirected graph A-B, A-C, B-D, C-D starting from A:

Kruskal's Algorithm for MST with Example: Sort all edges by non-decreasing weight; iterate through sorted edges and add if and lie in different components (checked via Union-Find) until edges are chosen. Example: On 4-vertex graph A-B(1), B-C(2), A-C(3), C-D(4), B-D(5):

Answer:

All past exam questions for Data Structure and Algorithms