PadhaikoAll subjects

Past exam question: 2074 Bhadra (Regular), Q10

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Graphs

Question

Explain Depth first traversal in graph. Create minimum spanning tree for the following graph using Kruskal's algorithm.

[figure: undirected weighted graph on 7 vertices A, B, C, D, E, F, G with edges A-B(5), A-C(2), A-D(6), B-D(3), B-F(2), B-G(3), C-D(4), C-E(1), D-F(2), D-G(4), E-F(6), F-G(1)]

Solution

Depth-First Traversal (DFS) in a Graph: DFS starts at a source vertex, marks it visited, and recursively (or via a Stack) explores an unvisited adjacent neighbor as deeply as possible before backtracking to explore remaining unvisited neighbors. Time complexity is with an adjacency list.

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

EdgeWeightActionConnected Components
C-E1Accept{C, E}
F-G1Accept{F, G}
A-C2Accept{A, C, E}
B-F2Accept{B, F, G}
D-F2Accept{B, D, F, G}
B-D3RejectForms cycle B-F-D-B
B-G3RejectForms cycle B-F-G-B
C-D4Accept{A, B, C, D, E, F, G} (6 edges — complete!)

Total Minimum Weight:

Answer:

All past exam questions for Data Structure and Algorithms