CODEWITHSUNDEEP
algorithmgreedyminimum-spanning-treekruskals-algorithm
Jeremy
Jeremy

Reputation: 45

How is Kruskal's Algorithm Greedy?

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 ?

Upvotes: 2

Views: 4484

Answers (3)

AmyC
AmyC

Reputation: 77

First of all, what does it mean to be greedy?

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.
----Wikipedia https://en.wikipedia.org/wiki/Greedy_algorithm

Thus "greedy algorithm" is about making choices in sequence such that each individual choice is best according to some limited "short-term" criterion that is not too expensive to evaluate.

Here in Kruskal's algorithm, the "choice" is "picking the edge with the next lowest weight and do not form a cycle with already picked edges" and it is not too expensive to evaluate given the sorting algorithm and the union-find data structure.

The local minimum you mentioned in the question should be understood more as current knowledge of graph instead of adjacent vertices or edges.

Upvotes: 1

Mukit09
Mukit09

Reputation: 3399

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.

Upvotes: 1

amit
amit

Reputation: 178451

It is a greedy algorithm because you chose to union two sets of vertices each step according tot he minimal weight available, you chose the edge that looks optimal at the moment. This is a greedy step, and thus the algorithm is said to be greedy.

in the pseudo code from wikipedia (attached), the greedy step is at the choice of (u,v), which is the lowest weighted edge that connects two unconnected components.

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A

Upvotes: 0

Related Questions