Past exam question: 2078 Poush (Back), Q8
Open in the Padhaiko appQuestion
Differentiate between breadth first and depth first search algorithms. Create a minimum spanning tree for the following graph using Kruskal's algorithm.
[figure: undirected weighted multigraph on 6 vertices S, A, B, C, D, T with edges S-A(7), S-C(8), A-C(3), A-B(6), A-B(9), C-C self-loop(1), B-C(4), C-D(3), B-D(2), B-T(5), B-T(7), D-T(2)]
Solution
Breadth-First Search (BFS) vs. Depth-First Search (DFS):
| Aspect | Breadth-First Search (BFS) | Depth-First Search (DFS) |
|---|---|---|
| Strategy | Level-by-level exploration from source | Explores as deep as possible before backtracking |
| Data Structure | Queue (FIFO) | Stack (LIFO) or recursion |
| Shortest Path | Finds shortest path in unweighted graphs | Does not guarantee shortest path |
| Applications | Shortest hop path, level-order traversal, broadcasting | Cycle detection, topological sort, connectivity, maze solving |
| Time Complexity | (adjacency list) | (adjacency list) |
Kruskal's Algorithm — Sorted Edge List: With (S, A, B, C, D, T), an MST requires edges. Self-loops (C-C(1)) always form a cycle and are ignored.
| Edge | Weight | Action | Reason |
|---|---|---|---|
C-C | 1 | Reject | Self-loop |
B-D | 2 | Accept | Connects {B, D} |
D-T | 2 | Accept | Connects T ({B, D, T}) |
A-C | 3 | Accept | Connects {A, C} |
C-D | 3 | Accept | Merges {A, C} and {B, D, T} |
B-C | 4 | Reject | Forms cycle B-D-C-B |
B-T | 5 | Reject | Forms cycle B-D-T-B |
A-B | 6 | Reject | Forms cycle A-C-D-B-A |
S-A | 7 | Accept | Connects S (5 edges reached — MST complete) |
MST Cost Verification:
- Remaining edges
B-T(7),S-C(8),A-B(9)are rejected as all 6 vertices are already spanned. - Total MST Weight:
Answer:
- BFS vs. DFS: BFS uses a Queue for level-wise traversal (unweighted shortest paths), while DFS uses a Stack/recursion for deep backtracking (cycles, topological sort).
- Kruskal's MST Edges:
B-D(2),D-T(2),A-C(3),C-D(3),S-A(7). - Total Minimum Weight: .