PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q8

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Graphs

Question

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

AspectBreadth-First Search (BFS)Depth-First Search (DFS)
StrategyLevel-by-level exploration from sourceExplores as deep as possible before backtracking
Data StructureQueue (FIFO)Stack (LIFO) or recursion
Shortest PathFinds shortest path in unweighted graphsDoes not guarantee shortest path
ApplicationsShortest hop path, level-order traversal, broadcastingCycle 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.

EdgeWeightActionReason
C-C1RejectSelf-loop
B-D2AcceptConnects {B, D}
D-T2AcceptConnects T ({B, D, T})
A-C3AcceptConnects {A, C}
C-D3AcceptMerges {A, C} and {B, D, T}
B-C4RejectForms cycle B-D-C-B
B-T5RejectForms cycle B-D-T-B
A-B6RejectForms cycle A-C-D-B-A
S-A7AcceptConnects S (5 edges reached — MST complete)

MST Cost Verification:

Answer:

All past exam questions for Data Structure and Algorithms