Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



Consider the graph shown below : 
Use Kruskal's algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is





Solution

Using Kruskal's algorithm, we select edges in increasing order of weights, without forming a cycle.

From the graph, the selected edge weights are:

$1,1,1,2,2,2,3,4$

Since the graph has $9$ vertices, the minimum spanning tree must have

$9-1=8$ edges.

Now, total weight of MST is

$1+1+1+2+2+2+3+4$

$=16$

Therefore, the weight of the minimum spanning tree is

$16$



Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...