2 votes 2 votes 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? Algorithms kruskals-algorithm prims-algorithm minimum-spanning-tree + – sandip_1999 asked May 11, 2022 edited May 12, 2022 by ankitgupta.1729 sandip_1999 664 views answer comment Share Follow See 1 comment See all 1 1 comment reply ankitgupta.1729 commented May 12, 2022 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.