What is MST (minimum spanning tree)

Technical details of a Minimum Spanning Tree (MST).

1. Definition:
   • An MST is a fundamental concept in graph theory.
   • It refers to a subset of edges in a connected, weighted graph that connects all the vertices with the minimum possible total edge weight.
   • The MST is a spanning tree, which means it includes all the vertices of the graph and forms a tree structure (acyclic).
2. Properties of a Spanning Tree:
   • The spanning tree adheres to the following principles:
     • The number of vertices (V) in the graph and the spanning tree is the same.
     • The number of edges in the spanning tree is equal to one less than the total number of vertices (E = V – 1).
     • The spanning tree should not be disconnected; there should be only a single connected component.
     • The spanning tree must be acyclic (no cycles).
     • The total cost (or weight) of the spanning tree is the sum of the edge weights of all its edges.
     • There can be many possible spanning trees for a given graph.
3. Minimum Spanning Tree (MST):
   • An MST is a spanning tree that has the minimum weight among all possible spanning trees.
   • It retains all the properties of a spanning tree but adds the constraint of minimizing the total edge weights.
   • Like a spanning tree, there can be multiple possible MSTs for a graph.
4. Algorithms to Find MST:
   • Several algorithms exist to find the minimum spanning tree from a given graph. Here are two popular ones:
     • Kruskal’s Minimum Spanning Tree Algorithm:
       • A greedy algorithm that works for connected, undirected graphs.
       • Workflow:
         1. Sort all edges by their weights.
         2. Iteratively add the next lowest-weight edge to the MST, ensuring no cycles are formed.
         3. Efficiently implemented using a Disjoint-Set Union (DSU) data structure.
       • Practical applications: network design, clustering, and data analysis.
     • Prim’s Minimum Spanning Tree Algorithm:
       • Another greedy algorithm.
       • Workflow:
         1. Start with an arbitrary vertex and grow the MST by adding the nearest vertex.
         2. Select the next vertex with the minimum edge weight.
         3. Repeat until all vertices are included.
       • Also used in network design and resource allocation.
5. Example:
   • Consider the following graph: !Graph
   • The MST for this graph would include edges {A-B, B-C, C-D, D-E, E-F} with a total weight of 16.