It is said that Kruskal's algorithm for MST construction is greedy, but the algorithm chooses global minimum and instead of local minimum unlike Prim's algorithm. Can someone explain how Kruskal's algorithm is considered a greedy approach ?
What we do in Kruskal ? Firstly sort the edges according to their weight. Then we choose that edge which has minimal weight. We add that edge if it makes no cycle. Thus we go forward greedily. So it is greedy approach. :)
The greedy approach is called greedy because, it takes optimal choice in each stage expecting, that will give a total optimal solution.