Minimum Spanning Tree (MST) algorithms find the cheapest way to connect all points in a network. They're crucial for optimizing connections in various fields, from computer networks to city planning.

Prim's and Kruskal's are two key MST algorithms. Prim's grows a tree from a starting point, while Kruskal's sorts all connections by cost and adds the cheapest ones that don't create loops. Both find the most efficient network layout.

Minimum Spanning Tree Algorithms

Minimum spanning tree properties

• Subset of edges in a weighted, connected, and undirected graph that spans all vertices with minimum total edge weight
• Contains no cycles, forming a tree structure
• Number of edges is always one less than the number of vertices (V-1 edges for V vertices)
• Uniqueness depends on edge weights
  • Distinct edge weights guarantee a unique MST
  • Duplicate edge weights may result in multiple valid MSTs
• Cut property states the minimum weight edge crossing any cut in the graph is part of the MST
• Cycle property states the maximum weight edge in any cycle is not part of the MST

Steps of Prim's algorithm

1. Start with an empty set to store MST vertices

2. Assign key values to all vertices

   • Initial vertex key set to 0
   • All other vertex keys set to infinity

3. While there are vertices not in the MST:

   1. Select the vertex with the minimum key value (not yet in MST)
   2. Add this vertex to the MST set
   3. Update adjacent vertex key values if the edge weight is smaller than the current key

Steps of Kruskal's algorithm

1. Sort all edges in non-decreasing order of weight
2. Initialize an empty set for MST edges and a disjoint set data structure for connected components
3. For each edge in sorted order (lowest to highest weight):
   1. If adding the edge doesn't create a cycle (vertices not already connected)
      • Include it in the MST
      • Update the disjoint set data structure
   2. If adding the edge creates a cycle, discard it
4. Repeat step 3 until the MST has V-1 edges (V = number of vertices)

Prim's vs Kruskal's algorithms

• Time complexity
  • Prim's: $O((V+E) \log V)$ or $O(E \log V)$ with a binary heap (V = vertices, E = edges)
  • Kruskal's: $O(E \log V)$ for sorting edges and $O(V \alpha(V))$ for disjoint set operations (near-constant time)
• Implementation differences
  • Prim's maintains a priority queue of vertices based on key values
    • Suitable for dense graphs or adjacency matrix representation
  • Kruskal's sorts edges by weight and uses a disjoint set data structure for cycle detection
    • Suitable for sparse graphs or adjacency list representation
• Both are greedy algorithms that produce the same MST (with distinct edge weights)
  • Differ in approach and implementation details
  • Kruskal's may perform better in practice for sparse graphs (fewer edges)