PadhaikoAll subjects

Past exam question: 2078 Baishakh (Back), Q11

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Graphs

Question

Define minimum spanning tree with suitable example. Show step by step solution to find the minimum spanning tree of the graph below using Prim's algorithm.

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

Solution

Definition and Example of Minimum Spanning Tree (MST): Given a connected, undirected, weighted graph , a Minimum Spanning Tree (MST) is an acyclic connected subgraph containing all vertices with edges such that the sum of edge weights is minimized.

Prim's Algorithm Trace (Starting from Vertex A): Maintain visited set and grow the tree by repeatedly picking the minimum-weight edge crossing :

  1. Initial: . Candidate edges: A-D(1), A-C(6), A-B(7).
    • Pick A-D(1). .
  2. From : Candidates: D-E(4), C-D(5), D-F(5), A-C(6), A-B(7).
    • Pick D-E(4). .
  3. From : Candidates: E-F(2), C-E(3), C-D(5), D-F(5), A-C(6), A-B(7).
    • Pick E-F(2). .
  4. From : Candidates: C-E(3), C-D(5), A-C(6), A-B(7).
    • Pick C-E(3). .
  5. From : Candidates crossing to B: A-B(7), B-C(8).
    • Pick A-B(7). (all 6 vertices covered!).

MST Verification: Selected edges (): A-D(1), D-E(4), E-F(2), C-E(3), A-B(7). Total MST weight = .

Answer:

All past exam questions for Data Structure and Algorithms