180 views
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?

### 1 comment

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

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.

1
2,792 views