Minimum Spanning Trees (MST)

A Spanning Tree is a subset of edges that connects all vertices in a graph without any cycles. A Minimum Spanning Tree is the one with the smallest total edge weight. It is the core of network design optimization.

1. Kruskal's Algorithm (Edge-Based)

Sort all edges by weight. Start adding the smallest edges one by one. Use Union-Find to ensure you never create a cycle. This is perfect for disconnected graphs (Forests).

2. Prim's Algorithm (Vertex-Based)

Start from a single node and expand "greedily" to the nearest unvisited node. This is very similar to Dijkstra and works best for dense graphs.

3. Real-world Usecase

Building a **Fiber Optic Network** connecting 50 cities. You want every city to be connected (directly or indirectly) using the minimum amount of expensive cable. MST gives you the optimal layout.

4. Interview Mastery

Q: "What is the Time Complexity of Kruskal's?"

Architect Answer: "It is **O(E Log E)** or **O(E Log V)** because the dominant part of the algorithm is sorting the edges. The actual cycle detection part using Union-Find is extremely fast—nearly O(1) per operation."