(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.

Kruskal’s algorithm illustration showing a weighted graph and comparison of possible spanning trees, selecting the minimum spanning tree with the lowest total edge weight.

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

Sort all edges in non-decreasing order of weight:

\bm{w(e_1)\le w(e_2)\le}\dots\bm{\le w(e_{|E|}})

$
Initialize MST = Ø (empty set)
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
Stop when MST contains V − 1 edges

5. Output

Set of edges 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:
Union-Find operations: O(E α(V)) ≈ O(E)
(α = inverse Ackermann, extremely slow-growing)

✔ Final complexity:

O(E\log_2E)

O(n\log_2n)

O(E\log_2V)\quad(\text{since}\;E\le V-1)

7. Example Use-Cases

Network design (cables, LAN)
Road/rail route optimization
Clustering in ML
Minimum-cost spanning infrastructure

8. Pseudocode

powershell

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