Question

. What is minimum spanning tree (MST)? Apply Kruskal’s algorithm to find the MST for the following graph.

 

Image ignouacademy-com--p-apply-41120

12 Sep 2025
Answer :
Word Count : 1108
A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted, undirected graph that connects all the vertices together without forming any cycles and with the minimum possible total edge weight. The main purpose of an MST is to ensure that every vertex is reachable from any other vertex while minimizing the cost associated with the edges. In practical applications, MSTs are used in designing efficient network layouts such as computer networks, telecommunication networks, road networks, and electrical grids, where minimizing the total wiring or distance is important. There are several algorithms to find an MST, among which Kruskal’s algorithm and Prim’s algorithm are most widely used. Kruskal’s algorithm focuses on adding edges in increasing order of their weights while avoiding cycles, whereas Prim’s algorithm grows the MST from a starting vertex by repeatedly adding the smallest edge connecting the tree to a vertex outside it. Kruskal’s algorithm is a greedy approach to find the MST. The algorithm works as follows: first, all the edges of the graph are sorted in ascending order based on their weights. Then, edges are picked one by one from the sorted list and added to the MST if they do not form a cycle with the edges already included. To detect cycles efficiently, a Disjoint Set Union (DSU) or Union-Find data structure is commonly used. This data structure keeps track of connected components and helps in determining whether adding a particular edge will create a cycle. The process continues until all vertices are included in the MST, which means exactly $V-1$ edges are chosen for a graph with $V$ vertices. To apply Kruskal’s algorithm, let us consider the following graph with vertices labeled $A, B, C, D, E, F$ and edges with their respective weights: * Edge AB = 4 * Edge AC = 2 * Edge BC = 1 * Edge BD = 5 * Edge CD = 8 * Edge CE = 10 * Edge DE = 2 * Edge DF = 6 * Edge EF = 3 Step 1: Sort all edges in increasing order of their weights: BC(1), AC(2), DE(2), AB(4), EF(3), BD(5), DF(6), CD(8), CE(10) Step 2: Initialize an empty MST and consider each edge in the sorted order. We will also keep track of connected components to avoid cycles. * First, pick edge BC(1). Since B and C are not connected yet, add BC to MST. MST = {BC} * Next, pick AC(2). A and C are not yet connected in MST, add AC. MST
_____ _____ __________ __________ ______.
_______ ________ _________ ____ ____ _____ ________ __________ ______ _________ _____ _____.
_____ ___ ___ _________ _________ _______ ____ _______.
_________ ______ ______ _____ _____ __________.
_____ _________ ________ ______ _____ ________.
________ _____ __________ _________ _______.
_______ ___ ________ __________ _____ ____ _________ __________.
_______ ________ ____ _______ _____ _________ _________ __________ _________.
_______ _____ ______ ___ _______ _____ ___ _______.
_____ _________ _________ ___ ___ ______ _____ __________ _______ _____ _____.
____ _______ __________ __________ ____ _________ ______ ___ _____ ____ __________.
_______ _________ ________ _____ _____ _______ _________ _________ ______.
_____ ______ ____ __________ _________ _____ ________ _________.
________ __________ __________ ______ _______ _______ ___.
_______ __________ ____ ___ _______ _______ _______ ______ ___ ______ _____.
___ ___ _________ ____ ____ _______ ____.
___ ___ ______ __________ ________ __________ ____ ______ ____ ___ ____.
_____ ___ ___ __________ _____ ____.
_______ ______ _______ ___ ______ ______ _________ ___ _________ ________ ____ ___.
____ ___ ____ _______ ______ _________ __________ _______.
_______ ___ ______ ______ _______.
________ __________ _______ __________ ________ _______.
___ ____ __________ _______ ______ ________ _____ ____ ________ _________.
________ _________ _____ ___ _______ __________ ___ _____ _________ ___.
____ ___ ___ _________ ____ _____ ______ ______.
_______ ___ ______ _______ ________ ____.
____ _________ _______ ____ __________ ______ _____ ______ __________ _______ ______.
________ _____ _______ _____ _________.
________ _______ ____ ____ ______ __________.
_________ ___ ______ _____ ______ _________ _________ ____ _________ _________ ______ _______.
_________ __________ ________ ___ _____ ___ _____ ________ ___ _____ ___ ___.
__________ __________ _____ _______ ____ ____ _____ _____ ____.
____ ________ __________ __________ _______ _________ _________ ________ ___ _________ __________.
__________ __________ _______ _________ ______ ____ ___ _____.
_____ ________ __________ _______ _________ ___ ________ ____.
_____ _______ ____ ____ ______ ________ ___ _________ __________ __________ ____ ___.
_____ _____ ______ ________ __________ ______ __________ _________ _________.
______ ____ _________ __________ __________ _________ _____.
________ ___ _________ ____ ____ ____ ____ _________ ________ ___.
________ ___ ______ _________ ______ _________ ____ ________.
________ _______ ______ ________ _______.
___ __________ ____ ____ ______ ______.
_________ _____ __________ ________ __________ ___ ___ ______ _________ ____ ____.
____ ___ _____ _____ _____ ________ _______ ______ _____.
_______ __________ _______ _____ _______ ________ ____ ________ _____ _________ ________ _______.
__________ ________ __________ __________ _____.
________ ___ ____ __________ _________ ___.
_________ ___ ____ _______ __________ _______ _________ ________ ______ _________ ___ ________.
_________ _________ _________ _______ __________ __________ __________ _____.
_________ _________ ___ __________ _________ ____ _________.
_______ ___ _____ _______ _________ _________.
__________ ______ __________ ______ _________ ___ _______ _____ _______ _____ _____.
____ ____ _____ ___ ____ _______ _______ ________.
________ ___ ___ __________ __________ ____ _____ _____ __________ ___ _____ ______.
____ ______ _______ __________ _________ __________ _________ ___ _____ ___ ___.
____ ________ ____ ________ ______ ____ _______ ________.
______ _________ _____ __________ __________ __________ _____ _________.
___ ____ ___ ________ _______ ___.
__________ _______ _________ ___ __________ __________ _________ ___ ____ _________ ____.
______ _______ _____ _________ _____ ____ ___ ___ _____ _____ _____.
______ _____ ________ __________ _________ _________ ________ ____ ________ __________ ________.
_______ __________ ___ ______ ____ ______ ___ __________ ______ ______ _____ ______.
____ ___ __________ __________ ____ ______.
___ ____ ___ _____ _________.
______ ___ ________ _____ _______ _______ _______ _________ __________ __________ ___.
___ _____ ______ ___ ______ ______.
____ _________ __________ _________ ________ __________ ______ ________ _________.
___ _____ ___ ___ ________ __________ _____ _______ ______ ____ _________ _________.
_________ ________ ______ ___ ___ __________ _______ ______ __________.
_____ ____ ____ _________ ______ ___.
_____ _____ ______ _____ _______ ________.
_______ ________ __________ ______ ___ _____ ___ ______ ____ ___ _____ __________.
________ ___ ______ ______ _____ ________.
____ ____ ________ ___ ___ ___ __________ ____.
______ _________ __________ ________ _____ _________ ________ _____ ____ ___ __________ _________.
______ ____ ___ ___ __________.
___ __________ _____ _______ ___ ______ ____ _______.
______ ________ _______ _______ ____ _________ _____ ________.
______ _________ _______ _______ _________ ___ __________ __________ _________ __________ ___.
____ ___ _______ _____ _________ _________ __________ ___ _________ ______.
IGNOU ACADEMY
Your IGNOU journey, made easier.
  • Solved Assignments
  • Study Notes
  • Guess Papers
  • Question Papers
Skip in 10
Top
📞
Call Support Instant phone assistance IGNOU MCS 21 2025 2026 - . What is minimum spanning tree (MST)? Apply Kruskal’s algorithm | IGNOU Academy
→
🟢
WhatsApp Chat Fast live messaging
→
Email Us Business enquiries & support
→