#🔒 Kruskal's Algorithm - which way to go if two edges have the same weight?

18 messages · Page 1 of 1 (latest)

abstract lynx
#

Hey there! I'm currently looking into graphs and stumbled upon Kruskal's Algorithm. I have a question regarding the implementation on https://www.programiz.com/dsa/kruskal-algorithm.

In the example, I get the first image which is the weighted graph. Afterwards one of the graphs with the least weight is chosen. Fine by me. Then we chose the next edge with the least weight. We iterate like this over the connections to the respective edge. However, prior to the last image we have two choices to draw the edge with the weight 4. The authors have made a decision and the question I have is if it matters or not (in theory it shouldn't) which one I take.

hexed brookBOT
#

@abstract lynx

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.
abstract lynx
#

I'm talking specifically about this case:

image.png
#

And whether or not I could've done this:

image.png
#

The same question applies to Christofides algo: in step 5 of the example, could I not connect the nodes vertically instead?
https://en.wikipedia.org/wiki/Christofides_algorithm

Christofides algorithm

The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality).
It is an approximation algorithm that guarantees that its solutions will be within a facto...

barren musk
#

Would have to see all the edges and weights to tell

abstract lynx
#

It's the same weight

barren musk
#

Ah then yes.

#

It doesn't matter.

#

In both cases, you get a MST

abstract lynx
#

Do you know whether or not it is the same for Christofides example? Mathematically the end result should be the same?

image.png
barren musk
#

Haven't heard of that algo. Will have to read it up later!

cosmic mortar
abstract lynx
#

Thank you

#

!close

hexed brookBOT
#
Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.