MST algorytmu Prima ze stosem kopcowym
Rozwijanie drzewa od jednego wierzchołka
MST algorytmu Prima ze stosem kopcowym to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 4 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.
Inna droga do MST
Algorytm Prima również znajduje minimalne drzewo rozpinające, ale rozbudowuje jeden spójny obszar na zewnątrz, zamiast najpierw sortować wszystkie krawędzie. 🌱
Rozpoczęcie od jednego wierzchołka
Proszę wybrać dowolny wierzchołek początkowy i oznaczyć go jako visited. Drzewo zaczyna się od pojedynczego węzła i rozszerza się po jednej krawędzi naraz.
visited = [False] * nIdea granicy
W każdym kroku należy rozważyć wszystkie krawędzie prowadzące z drzewa na zewnątrz. Algorytm Prima zawsze wybiera najtańszą z tych krawędzi granicznych.
Kopiec minimum wybiera minimum
Kopiec minimalny szybko znajduje najtańszą krawędź graniczną. W każdej iteracji należy dodawać do niego krawędzie kandydujące i usuwać wpis o najmniejszej wadze.
import heapq
heap = [(0, start)]Usunięcie najtańszej krawędzi
Proszę usunąć z kopca wpis o najmniejszej wartości. Zawiera on wagę oraz kolejny wierzchołek, który najtaniej można dołączyć do rozbudowywanego drzewa.
w, u = heapq.heappop(heap)Pomijanie nieaktualnych wpisów
Wierzchołek może znajdować się w kopcu więcej niż raz. Jeśli usunięty wpis dotyczy wierzchołka, który jest już oznaczony jako visited, należy go zignorować i usunąć kolejny wpis.
if visited[u]:
continueDodawanie i rozszerzanie
Należy oznaczyć usunięty wierzchołek jako visited i dodać jego wagę do sumy. Następnie proszę dodać do kopca wszystkie wychodzące z niego krawędzie, aby można było wykorzystać je w kolejnych krokach.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Powtarzanie do ukończenia
Proszę kontynuować usuwanie wpisów i rozszerzanie drzewa, aż każdy wierzchołek zostanie oznaczony jako visited. Wtedy zgromadzona suma jest wagą minimalnego drzewa rozpinającego.
Czas działania
Każdą krawędź można dodać do kopca i usunąć z niego, dlatego algorytm Prima oparty na kopcu działa w czasie O(E log V), porównywalnym z algorytmem Kruskala.
Prim a Kruskal
Algorytm Prima warto stosować dla gęstych grafów z listą sąsiedztwa, a algorytm Kruskala — gdy dostępna jest już zwykła lista krawędzi. Oba algorytmy zwracają tę samą wagę MST.
Przypomina algorytm Dijkstry
Pętla z kopcem przypomina algorytm Dijkstry, ale porównywane są surowe wagi krawędzi, a nie odległości ścieżek. Rozpoznanie tego schematu pozwala szybciej pisać kod. ⚡
Szybki test
Proszę przypomnieć sobie, jak algorytm Prima wybiera kolejną krawędź w każdej iteracji.
Podsumowanie
Zbudował(a) Pan/Pani MST za pomocą algorytmu Prima: rozpoczął(ęła) Pan/Pani w dowolnym miejscu, użył(a) kopca minimalnego do dodawania najtańszej krawędzi granicznej i pomijał(a) nieaktualne wpisy. Świetna praca! 🎉
Ucz się Python dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 30
- Lekcje
- 120
Często zadawane pytania
Czy lekcja „MST algorytmu Prima ze stosem kopcowym” jest bezpłatna?
Tak — pełny tekst „MST algorytmu Prima ze stosem kopcowym” 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 „MST algorytmu Prima ze stosem kopcowym”?
Rozwijanie drzewa od jednego wierzchołka Ć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 4 z 4.
Ile czasu zajmuje lekcja „MST algorytmu Prima ze stosem kopcowym”?
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
- DSU z kompresją ścieżki
- Scalanie według rangi i składowe
- Minimalne drzewo rozpinające algorytmu Kruskala
- MST algorytmu Prima ze stosem kopcowym