PadhaikoAll subjects

Past exam question: 2077 Chaitra (Regular), Q11

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Graphs

Question

Define depth first and breadth first traversal. Construct the minimum spanning tree (MST) for the given graph using Krushkal's algorithm.

[figure: undirected weighted graph on 7 vertices 1, 2, 3, 4, 5, 6, 7 with edges 1-2(28), 1-6(10), 2-3(16), 2-7(14), 3-4(12), 4-5(22), 4-7(18), 5-6(25), 5-7(24)]

Solution

Depth-First and Breadth-First Graph Traversal:

Kruskal's Algorithm — Sorted Edges (, Target Edges):

EdgeWeightActionConnected Components
1-610Accept{1, 6}
3-412Accept{3, 4}
2-714Accept{2, 7}
2-316Accept{2, 3, 4, 7}
4-718Reject4 and 7 already connected (4-3-2-7)
4-522Accept{2, 3, 4, 5, 7}
5-724Reject5 and 7 already connected (5-4-3-2-7)
5-625Accept{1, 2, 3, 4, 5, 6, 7} (6 edges — complete!)

Remaining Edge and Total Weight:

Answer:

All past exam questions for Data Structure and Algorithms