0Pricing
Competitive Programming Academy · Lekcja

Minimalne drzewo rozpinające algorytmu Kruskala

Dodawanie najtańszych krawędzi bez tworzenia cykli

Minimalne drzewo rozpinające algorytmu Kruskala to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Czym jest MST

Minimalne drzewo rozpinające łączy wszystkie wierzchołki przy najmniejszej łącznej wadze krawędzi i nie zawiera cykli. Można wyobrazić sobie okablowanie miasta przy najniższym koszcie. 🌲

Główna idea algorytmu Kruskala

Algorytm Kruskala opiera się na czystej strategii zachłannej: dodaje najtańszą krawędź, która nie tworzy cyklu, aż cały graf stanie się spójny.

Krok pierwszy: sortowanie krawędzi

Najpierw proszę posortować wszystkie krawędzie według wagi, od najmniejszej do największej. Zachłanne preferowanie tanich krawędzi sprawia, że końcowa suma jest minimalna.

edges.sort()  # (weight, u, v)

Dlaczego DSU pasuje idealnie

Dodanie krawędzi tworzy cykl tylko wtedy, gdy oba jej końce są już połączone. DSU sprawdza tę spójność w czasie niemal stałym. 🤝

Przejście po posortowanych krawędziach

Proszę przechodzić po krawędziach od najtańszej do najdroższej. Dla każdej z nich należy sprawdzić, czy jej dwa końce mają już wspólny korzeń w strukturze DSU.

for w, u, v in edges:
    ru, rv = find(u), find(v)

Akceptowanie lub odrzucanie

Jeśli korzenie są różne, krawędź łączy dwie oddzielne części, więc należy ją zaakceptować i połączyć te części operacją union. Jeśli korzenie są takie same, należy ją pominąć, aby uniknąć cyklu.

if ru != rv:
    union(u, v)
    total += w

Kiedy zakończyć działanie

Drzewo rozpinające dla n wierzchołków ma dokładnie n − 1 krawędzi. Po zaakceptowaniu tej liczby krawędzi można zakończyć działanie wcześniej.

Wykrywanie niespójności

Jeśli po rozpatrzeniu wszystkich krawędzi zaakceptowano mniej niż n − 1 z nich, graf jest niespójny i nie istnieje dla niego drzewo rozpinające.

Koszt czasowy

Najwięcej czasu zajmuje sortowanie, dlatego algorytm Kruskala działa w czasie O(E log E). Operacje DSU są tak tanie, że niemal nie zwiększają tego kosztu.

Dlaczego strategia zachłanna jest poprawna

Własność przekroju gwarantuje, że najlżejszą krawędź przecinającą dowolny podział można bezpiecznie dodać. Właśnie dlatego wybieranie krawędzi od najtańszej nigdy nie prowadzi do błędu.

Kiedy wybrać algorytm Kruskala

Algorytm Kruskala świetnie sprawdza się w przypadku rzadkich grafów zapisanych jako lista krawędzi — właśnie taki format najczęściej otrzymuje się bezpośrednio w zadaniach konkursowych. ⚡

Szybki test

Proszę wskazać, co powoduje, że algorytm Kruskala odrzuca krawędź.

Podsumowanie

Zbudował(a) Pan/Pani MST algorytmu Kruskala: posortował(a) Pan/Pani krawędzie, dodawał(a) najtańsze z nich, łącząc dwie składowe za pomocą DSU, i zakończył(a) działanie po uzyskaniu n − 1 krawędzi. 🎉

Często zadawane pytania

Czy lekcja „Minimalne drzewo rozpinające algorytmu Kruskala” jest bezpłatna?

Tak — pełny tekst „Minimalne drzewo rozpinające algorytmu Kruskala” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Minimalne drzewo rozpinające algorytmu Kruskala”?

Dodawanie najtańszych krawędzi bez tworzenia cykli Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?

Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Minimalne drzewo rozpinające algorytmu Kruskala”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?

Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. DSU z kompresją ścieżki
  2. Scalanie według rangi i składowe
  3. Minimalne drzewo rozpinające algorytmu Kruskala
  4. MST algorytmu Prima ze stosem kopcowym
← Powrót do Competitive Programming Academy