Intermediate LevelData Structures & Algorithms
How do Kruskal's and Prim's algorithms find the Minimum Spanning Tree?
ā Interview Prompt: Compare Kruskal's (edge-based, Union-Find) and Prim's (vertex-based, min-heap) MST algorithms ā their complexities and use cases.
A Minimum Spanning Tree (MST) connects all $V$ vertices with $Vā1$ edges of minimum total weight, with no cycles.
Kruskal's Algorithm ā $O(E \log E)$:
ā¢
Sort all edges by weight.
ā¢
Add edge to MST if it doesn't form a cycle (Union-Find check).
ā¢
Best for sparse graphs.
Prim's Algorithm ā $O(E \log V)$ with min-heap:
ā¢
Start from any vertex; greedily add the minimum-weight edge connecting the MST to a new vertex.
ā¢
Best for dense graphs.
Both produce the same MST (weight), though the tree structure may differ.
Code Implementation Example
typescript
// Kruskal's MST using Union-Find
function kruskalMST(n: number, edges: [number, number, number][]): number {
edges.sort((a, b) => a[2] - b[2]); // sort by weight
const uf = new UnionFind(n);
let totalWeight = 0, edgesUsed = 0;
for (const [u, v, w] of edges) {
if (uf.union(u, v)) { // no cycle ā add to MST
totalWeight += w;
edgesUsed++;
if (edgesUsed === n - 1) break; // MST complete
}
}
return edgesUsed === n - 1 ? totalWeight : -1; // -1 if not connected
}š”Kruskal's MST with Union-Find cycle detection ā O(E log E).
šÆ Interview Key Takeaway
Kruskal's is edge-based (sort + Union-Find) ā great for sparse graphs. Prim's is vertex-based (greedy + min-heap) ā better for dense graphs.
#DSA#MST#Kruskal#Prim#Intermediate
Back to all Data Structures & Algorithms Questionsā