PadhaikoAll subjects

Past exam question: 2073 Bhadra (Regular), Q11

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Graphs

Question

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

Example: On graph A-B, A-C, B-D, starting at A (alphabetical neighbors):

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:

All past exam questions for Data Structure and Algorithms