Minimum Spanning Tree (MST)

In graph theory, a Minimum Spanning Tree (MST) for a weighted graph is a spanning tree with the minimum weight among all the spanning trees. It connects all the vertices together without any cycles and with the minimum possible total edge weight.

Key Concepts

• Spanning Tree: A subset of Graph G, which has all the vertices covered with the minimum number of edges.
• Weighted Graph: A graph where each edge has a numerical weight.

Greedy Algorithms for MST

1. Kruskal's Algorithm
   • Strategy: Add edges in order of increasing weight until all vertices are connected without forming a cycle.
   • Steps:
     1. Sort all the graph edges in non-decreasing order of their weight.
     2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far using a Disjoint Set (Union-Find). If cycle is not formed, include this edge.
     3. Repeat step 2 until there are $V-1$ edges in the spanning tree, where $V$ is the number of vertices.
2. Prim's Algorithm
   • Strategy: Start from an arbitrary vertex and grow the MST by adding the cheapest possible connection from the tree to another vertex.
   • Steps:
     1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
     2. Grow the tree by adding the cheapest edge from the tree to a vertex not yet in the tree.
     3. Repeat step 2 until all vertices are in the tree.

Efficiency

• Kruskal's Algorithm is more efficient for sparse graphs.
• Prim's Algorithm can be more efficient for dense graphs, especially with the use of priority queues.

Use Cases

MSTs are useful in scenarios that require:

• Designing a minimal cost network, such as electrical wiring, computer networks, or road networks.
• Cluster analysis in data science.

Complexity

• Kruskal’s Algorithm: $O (E \log E)$ or $O (E \log V)$ for sorting edges and making sets.
• Prim’s Algorithm: $O (E + V \log V)$ with a binary heap (or Fibonacci heap for better performance).