0Pricing
Coding Interview Prep · 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 Coding Interview Prep 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep 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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

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

Dodawanie najtańszych krawędzi bez tworzenia cykli Ćwiczysz Coding Interview Prep 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ąć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep 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 Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep 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 Coding Interview Prep