Why does Kruskal's algorithm find the minimum spanning tree if it's greedy? Isn't a minimum spanning tree a global optimization problem? Isn't the point of being greedy is that there is a chance you won't find the most optimal solution? So how can Kruskal be able to find the minimum spanning tree while also being greedy?

Question

Please can anyone tell me though Prim’s and Kruskal’s algorithms are greedy algorithms. Greedy algorithms always give local optimum solutions but how Prim’s and Kruskal’s algorithms are giving global optimum solutions why?

Comments

Yes, Greedy algorithms give local optimal solution but that local optimal solution may or may not produce globally optimal solution. In Kruskal’s algorithm, it produces.

There are some greedy algorithms which produce globally optimal solution and there are some algorithms which don’t.

Kruskal’s algorithm comes under those greedy algorithms which produce gobally optimal solution.

Why it produces globally optimal solution, for this, you have to go through the proof of correctness of Kruskal’s  algorithm. I am mentioning some sources for it:

1) MITOCW

2) Wikipedia

I would suggest to go through the first link because you can understand it easily from there with the use of Cut and Paste argument for greedy choice property.