• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytm Kruskala MST z Find And Union

Object Storage Arubacloud
0 głosów
92 wizyt
pytanie zadane 20 czerwca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Algorytm Kruskala do szukania MST jest prosty. Sortujemy krawędzie po wagach, jeżeli są w różnej spójnej, to łączymy, w jakiej spójnej sprawdzamy Union Findem.

Wszystko by było spoko, tylko niezbyt rozumiem dlaczego to zawsze jest optymalne, w sensie dlaczego nie opłaca nam się użyć krawedzi o większej wadze.

Bardzo proszę o wytłumaczenie.

Z góry dzięki!

1 odpowiedź

+2 głosów
odpowiedź 20 czerwca 2023 przez Whistleroosh Maniak (56,980 p.)
wybrane 20 czerwca 2023 przez pasjonat_algorytmiki
 
Najlepsza

Tu jest prosty dowód przez indukcję. Idea jest taka, że gdyby krawędź (powiedzmy e) dodana przez algorytm Kruskala nie należała do MST to stworzyłaby w tym MST cykl. Ale przez to w jaki sposób algorytm Kruskala wybiera te krawędzie (czyli od najmniejszej do największej wagi) możemy dowieść, że na tym cyklu istnieje inna krawędź o tej samej wadze co e. Wystarczy zatem usunąć tamtą krawędź z MST i dodać e i ostatecznie suma wag w MST się nie zmieni.

Podobne pytania

0 głosów
1 odpowiedź 177 wizyt
0 głosów
1 odpowiedź 142 wizyt
pytanie zadane 14 grudnia 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
0 głosów
1 odpowiedź 241 wizyt
pytanie zadane 18 listopada 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)

92,539 zapytań

141,381 odpowiedzi

319,469 komentarzy

61,926 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...