Login

Welcome, Guest. Please login or register.

March 29, 2024, 08:07:27 am

Author Topic: Networks - Kruskal's Algorithm  (Read 3508 times)  Share 

0 Members and 1 Guest are viewing this topic.

thaifriedrice

  • Adventurer
  • *
  • Posts: 13
  • Respect: +2
Networks - Kruskal's Algorithm
« on: May 22, 2019, 03:52:56 pm »
0
What happens in kruskals if there are two shortest edges? like if there were two edges that had the weight of 2? which one would you use to start at?
୧[ ˵ ͡ᵔ ͜ʟ ͡ᵔ ˵ ]୨ ~uwu

RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8814
  • "All models are wrong, but some are useful."
  • Respect: +2575
Re: Networks - Kruskal's Algorithm
« Reply #1 on: May 22, 2019, 05:12:35 pm »
+4
You can basically pick either of the two. Kruskal's algorithm is designed so that even when there's edges of the same weight, you'll get a correct answer.

(Remember that a network can have multiple different MSTs. Sometimes, depending on which edge you pick, you just end up getting two different MSTs. But they're still minimum spanning trees regardless.)

LoneWolf

  • MOTM: March 20
  • Trendsetter
  • **
  • Posts: 174
  • 2020!
  • Respect: +8
Re: Networks - Kruskal's Algorithm
« Reply #2 on: July 22, 2020, 09:11:46 pm »
0
RUI. can u please explain Kruskals please... dont get it
Business Studies
Economics
Modern History
English
Maths