Apr 26, 2026
How to find a minimum spanning tree using Kruskal's and Prim's algorithms?
I am studying graph theory and I need to understand minimum spanning trees (MST). A spanning tree of a connected, undirected graph is a subgraph that is a tree and includes all vertices.
I know two algorithms:
- Kruskal's algorithm: Sort edges by weight, add edges one by one if they don't form a cycle
- Prim's algorithm: Start from a vertex, repeatedly add the smallest edge connecting the tree to a vertex outside
My questions:
- Why do these algorithms work (correctness proof)?
- What are the time complexities of each?
- When should I use Kruskal vs Prim?
- How do I detect cycles efficiently in Kruskal's algorithm?
- Can I apply MST to a real-world problem like designing a fiber optic network connecting cities?
For example, find the MST of the graph with vertices A-F and edges:
AB:4, AC:2, BC:1, BD:5, CD:8, CE:10, DE:2, DZ:6, EZ:3.
1 answers338 views
Loading comments...
1 Answer
DP
Dr. Priya SharmaApr 27, 2026 Accepted**Kruskal's Algorithm (edge-centric):**
1. Sort edges by weight: BC(1), AC(2), DE(2), AB(4), BD(5), DZ(6), CD(8), CE(10), EZ(3) — wait EZ(3) should be before AB.
2. Add BC(1), AC(2), DE(2), EZ(3), AB(4) — but AB would create cycle A-B-C-A, so skip. Add DZ(6).
3. MST edges: BC(1), AC(2), DE(2), EZ(3), DZ(6). Total weight: 14.
**Prim's Algorithm (vertex-centric, starting from A):**
- A: pick AC(2) → {A, C}
- {A, C}: pick CB(1) → {A, B, C}
- {A, B, C}: pick BD(5) → {A, B, C, D}
- {A, B, C, D}: pick DE(2) → {A, B, C, D, E}
- {A, B, C, D, E}: pick EZ(3) → {A, B, C, D, E, Z}
Total: 2 + 1 + 5 + 2 + 3 = 13. (Different from Kruskal because Prim picked BD(5) instead of DZ(6). Both are valid MSTs — there can be multiple.)
**Why they work (Cut property):** For any cut partitioning vertices into two sets, the minimum-weight edge crossing the cut belongs to some MST. Both algorithms repeatedly apply this property.
**Cycle detection in Kruskal:** Use Union-Find (Disjoint Set Union). Each vertex starts in its own set. When adding edge (u, v), check if find(u) = find(v). If so, adding the edge creates a cycle. Otherwise, union the sets.
**Time Complexity:**
- Kruskal: $O(E \log V)$ (sorting dominates)
- Prim (binary heap): $O(E \log V)$
- Prim (Fibonacci heap): $O(V \log V + E)$
**When to use:**
- Kruskal: sparse graphs, easy to implement
- Prim: dense graphs, especially when adjacency matrix is available
Loading comments...