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?

Nadianadine

Answer 1

Okay, let's assume that you're right, so Kruskal's algorithm doesn't find the optimal solution. Let the solution found 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 a 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 a 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.

Alfonzoalford

"Otherwise, Kruskal's algorithm would have chosen all the edges on the path u-v instead of edge e". It's not clear to me why this must be true. For instance, there could be an alternative path. I think the proof of correctness in wikipedia is easier to follow. – Gesticulation

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!

Endoenzyme

Answer 3

There are some greedy algorithms that produce globally optimal solutions. There are some greedy algorithms that do not. Kruskal's algorithm happens to be in the first category (which requires a standard proof as shown in other answers).

Thermolabile

This doesn't answer the question. – Orianna

Given that the OP asked 4 questions, this answer addresses the conceptually critical 3rd. – Thermolabile

From what I understand, the OP already assumes that Kruskal's algorithm is correct, and given the title of the question, I assume the essense was questioning why the algorithm works if it's greedy. – Orianna

Answer 4

I am not sure what you mean.

However, wikipedia says:

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.[1] This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

Meanwhile, about minimum spanning tree, wikipedia says:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

So combining these two: Kruskal basically finds the minimum spanning tree or forest using a greedy search approach.

Deathless