PadhaikoAll subjects

Past exam question: 2064 Jestha, Q10(b)

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Graphs

Question

Write short notes on: b) Minimum cost spanning trees

Solution

Minimum Cost Spanning Trees (MST): For a connected, undirected, weighted graph , a spanning tree is an acyclic connected subgraph spanning all vertices with edges. A minimum cost spanning tree (MST) is a spanning tree whose sum of edge weights is as small as possible.

Answer:

A minimum cost spanning tree (MST) connects all vertices of a weighted undirected graph using acyclic edges with minimum total weight, computed via Kruskal's or Prim's algorithm.

All past exam questions for Data Structure and Algorithms