Why does Kruskal's algorithm find the minimum spanning tree if it's greedy?

Question

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?

Answer 1

Okay, let's assume that you're right, so Kruskal's algorithm doesn't find the optimal solution. Let the solution find by Kruskal's algorithm S, and the optimal solution T.

There must be an edge e = (u, v) that appears on S but not on T. As T is an spanning tree, there must be a path between node u and node v.

Now, we should notice that at least one edge on the path u-v has weight not smaller than e. Otherwise, Kruskal's algorithm would have chosen all the edges on the path u-v instead of edge e.

That means, if we remove that edge and add e on the solution T, the solution doesn't get worse. And as we assumed that T is optimal, after this change, the tree is still optimal. If we apply this logic repeatedly, we can always make S.

Answer 2

I could comprehend the askings as the following question- Greedy is not always optimal then why Kruskal's algorithm gets the optimal solution? So this question can be answered in two parts-

1. Does Kruskal algorithm gives optimal solution? This is already answered by @miheyan.

2. If greedy always gives optimal solution? In general NO, Greedy doesn't give optimal solution always but there is a set of problems for which Greedy approach gives optimal solution and Kruskal's algorithm lies in that set.

Let's take a problem statement - There are two players(player A and Player B) who are given a pile of money with different denomination. Let's say there are 4 currency notes with values as- 100, 50, 20, 10. Players will choose one currency note at a time and they will pick alternatively. Player A starts the game. Winner will be the person who gets more money.Both players play optimally. Who will win the game? Now try to solve this problem with greedy approach and see if greedy approach gives the optimal solution or not? Take different values, different examples and do your home work.

So the bottom line is - for a set of problems Greedy solution is always optimal but not for all problems. Hope it helps!