Past exam question: 2072 Ashwin (Regular), Q13
Open in the Padhaiko appQuestion
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:
- Mark visited and enqueue .
- 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:
- Enqueue
AvisitA, enqueueB, CvisitB, enqueueDvisitCvisitD. Order:A, B, C, D.
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):
- Sorted edges:
A-B(1), B-C(2), A-C(3), C-D(4), B-D(5). - Select
A-B(1),B-C(2), skipA-C(3)(cycle), selectC-D(4)3 edges chosen, MST total weight .
Answer:
- BFS: Uses a FIFO queue for level-order exploration (
A, B, C, Din the example). - Kruskal's Algorithm: Greedily adds lightest non-cycle edges up to edges (weight in the example).