MST (Kruskal's & prim's algorithm)

(MST) Kruskal’s & Prim's Algorithm

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