Past exam question: 2073 Bhadra (Regular), Q11
Open in the Padhaiko appQuestion
Write an algorithm for warshall's algorithm with suitable example. Define Breadth first traversal and depth first traversal with an example. Define Kruskal's Algorithm with suitable example.
Solution
Warshall's Algorithm with Example:
Algorithm WARSHALL(A, n):
1. R = A
2. For k = 0 to n - 1:
For i = 0 to n - 1:
For j = 0 to n - 1:
R[i][j] = R[i][j] OR (R[i][k] AND R[k][j])
3. Return R
Example: On directed edges 0->1, 1->2, initial has . At , updates to , showing 2 is reachable from 0.
Breadth-First Traversal (BFT) and Depth-First Traversal (DFT):
- BFT (Queue-based): Visits a start vertex, then all neighbors at distance 1, then distance 2, etc.
- DFT (Stack/Recursion-based): Follows one path as deep as possible before backtracking.
Example: On graph A-B, A-C, B-D, starting at A (alphabetical neighbors):
- BFT visits:
A, B, C, D. - DFT visits:
A, B, D, C.
Kruskal's Algorithm with Example: Sorts all edges by ascending weight and repeatedly adds the lightest edge that does not create a cycle until edges are selected. Example: On triangle A-B(1), B-C(2), A-C(5): pick A-B(1) and B-C(2), reject A-C(5) (cycle) MST weight .
Answer:
- Warshall's Algorithm: Computes all-pairs reachability in via intermediate vertices .
- BFT vs. DFT: BFT uses a Queue (
A, B, C, D); DFT uses a Stack (A, B, D, C). - Kruskal's Algorithm: Greedily selects minimum-weight acyclic edges using Union-Find.