We assume that we have the same graph G.

In introduction to Algorithms by Cormen it's said that it`s possible depending on how it breaks ties when the edges are sorted into order.

I have trouble visualizing the answer given:

Suppose that A is an empty set of edges. Then, make any cut that has (u, v) crossing it. Then, since that edge is of minimal weight, we have that (u, v) is a light edge of that cut, and so it is safe to add. Since we add it, then, once we finish constructing the tree, we have that (u, v) is contained in a minimum spanning tree.

What does it mean to make a cut? I`m familiar with Kruskal's algorithm but nowhere in the process do I see cuts being made. It's either we unite two trees and add the edge to A or we reject the edge and continue on.

  • $\begingroup$ That depends on the ordering of the elements. If you choose a different order, than you may select a different edge from the same lengths. $\endgroup$ – kelalaka Feb 24 '20 at 18:01

Cuts aren't made as part of Kruskal's algorithm; they are used in a proof that it always returns a minimum spanning tree. See e.g. here.

But you don't need them to answer the question in the title; instead, take as your graph a triangle with all 3 edges the same weight. Then any order on these edges is allowed and Kruskal's algorithm will return the tree consisting of the first 2 edges, whichever they are.

  • $\begingroup$ But how do you make the algorithm return different trees...wait does this involve changing the sorting method? It seems that it is quite vague how sorting is done in this algo. $\endgroup$ – BreezeWind Feb 24 '20 at 17:33
  • $\begingroup$ Yes, it only requires that if weight of edge $e_i$ is lower than weight of $e_j$, it's considered earlier, but edges with equal weights can be considered in any order. $\endgroup$ – Alexey Romanov Feb 24 '20 at 17:37
  • $\begingroup$ ok this is what I thought it would be. Thanks! $\endgroup$ – BreezeWind Feb 24 '20 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.