MST (Kruskal's & prim's algorithm)

(MST) Kruskal’s & Prim's Algorithm

Kruskal’s and Prim’s algorithms are two fundamental greedy approaches used to find a Minimum Spanning Tree (MST) of a connected, weighted graph, ensuring all vertices are connected with the minimum possible total edge weight. Kruskal’s algorithm works by selecting the smallest edges first and adding them to the tree while avoiding cycles, typically using a disjoint set (Union-Find) structure, whereas Prim’s algorithm starts from a node and grows the tree by repeatedly adding the smallest edge that connects a visited node to an unvisited node. Both methods guarantee an optimal MST but differ in their approach and implementation strategies.

1. Objective

Kruskal’s Algorithm finds a Minimum Spanning Tree (MST) of a connected, weighted graph by selecting the smallest edges first while avoiding cycles.

2. Key Points

• Uses Greedy Strategy.

• Works well for sparse and large graphs.

• Operates on edges, not adjacency lists.

• Requires a Disjoint Set / Union-Find data structure to detect cycles efficiently.

3. Inputs

• V → Number of vertices

• E → Number of edges

• Spanning tree always contains V − 1 edges

4. Steps of the Algorithm

1. Sort all edges in non-decreasing order of weight:
   

   $$\mathbf{w}({\mathbf{e}}_1)\le \mathbf{w}({\mathbf{e}}_2)\le \dots \le \mathbf{w}({\mathbf{e}}_{|\mathbf{E}|})$$

   $

2. Initialize MST = Ø (empty set)

3. For each edge (u, v) in sorted order:

   • If adding the edge does NOT form a cycle → add it to MST

   • Otherwise → skip the edge

   • Use Union-Find to check cycle

4. Stop when MST contains V − 1 edges

5. Output

• Set of edges ${\mathbf{E}}_{\mathbf{t}}$ forming the Minimum Spanning Tree

• MST total weight is minimum possible

6. Time Complexity

Dominant step → Sorting edges

World of defense on sorting algorithm which we use to sort the edge set E

• Sorting edges: $\mathbf{O}(|E|lo{\mathbf{g}}_2|E|)$

• Union-Find operations: O(E α(V)) ≈ O(E)
  (α = inverse Ackermann, extremely slow-growing)

✔ Final complexity:

7. Example Use-Cases

• Network design (cables, LAN)

• Road/rail route optimization

• Clustering in ML

• Minimum-cost spanning infrastructure

8. Pseudocode

Kruskal(G):
  sort edges by weight
  initialize MST = empty set
  make-set(v) for each vertex v

  for each edge (u, v) in sorted order:
    if find(u) != find(v):
       add (u, v) to MST
       union(u, v)

  return MST