Od 2010 · Ponad 2 mln uruchomień narzędzi miesięcznie
Od 2010
Dodaj do Chrome

Moje Narzędzia

Tryb Automatyczny

Nie zapisano jeszcze żadnych narzędzi.

Uaktualnij do Wersji Premium
Powiązane narzędzia
Kalkulator Najkrótszej Ścieżki DijkstryWalidator ciągu stopni grafuKalkulator Sortowania TopologicznegoKalkulator Kolorowania Grafów
Strona główna > Matematyka > Zaawansowane działania matematyczne
 

Kalkulator Minimalnego Drzewa Rozpinającego

Oblicz Minimalne Drzewo Rozpinające (MST) grafu ważonego za pomocą algorytmu Kruskala lub Prima. Funkcje obejmują interaktywną wizualizację grafu, śledzenie algorytmu krok po kroku oraz animację wyboru krawędzi.

BezpłatneBez rejestracjiAktualizacja lut 2026
Kalkulator Minimalnego Drzewa RozpinającegoWypróbuj teraz — za darmo ▼

Wypróbuj te przykładowe grafy:

Prosty (5 węzłów) Sieć (7 węzłów) Algorytm Prima (6 węzłów) Duży (12 węzłów)
Format: węzeł1, węzeł2, waga — jedna krawędź na linię. MST działa na grafach nieskierowanych. Wszystkie wagi muszą być nieujemne.

Embed Kalkulator Minimalnego Drzewa Rozpinającego Widget

O Kalkulator Minimalnego Drzewa Rozpinającego

Witamy w kalkulatorze minimalnego drzewa rozpinającego, interaktywnym narzędziu do obliczania MST dla grafu ważonego przy użyciu algorytmu Kruskala lub Prima. Niezależnie od tego, czy studiujesz teorię grafów, projektujesz infrastrukturę sieciową, czy optymalizujesz alokację zasobów, ten kalkulator zapewnia wizualną eksplorację krok po kroku dwóch fundamentalnych algorytmów optymalizacji kombinatorycznej.

Co to jest Minimalne Drzewo Rozpinające (MST)?

Minimalne Drzewo Rozpinające spójnego, nieskierowanego, ważonego grafu to podzbiór krawędzi, który:

  • Łączy wszystkie wierzchołki (rozpinające)
  • Nie zawiera cykli (drzewo)
  • Ma minimalną możliwą całkowitą wagę krawędzi

Dla grafu o V wierzchołkach, MST zawsze posiada dokładnie V - 1 krawędzi. Jeśli graf jest niespójny, wynikiem jest Minimalny Las Rozpinający — zbiór MST dla każdej spójnej składowej.

Właściwość MST
$$|E_{MST}| = |V| - 1 \quad \text{oraz} \quad W_{MST} = \sum_{e \in E_{MST}} w(e) \text{ jest zminimalizowane}$$

Algorytm Kruskala

Algorytm Kruskala to zachłanny algorytm oparty na krawędziach, który buduje MST poprzez przetwarzanie krawędzi w kolejności rosnących wag. Wykorzystuje strukturę danych Union-Find (zbiory rozłączne) do wydajnego wykrywania cykli.

Pseudokod Kruskala

function Kruskal(Graph):
  MST ← pusty zbiór
  Posortuj wszystkie krawędzie według wag (rosnąco)
  Zainicjuj Union-Find dla wszystkich wierzchołków

  for each krawędź (u, v, w) w posortowanych krawędziach:
    if Find(u) ≠ Find(v):  // różne składowe
      MST ← MST ∪ {(u, v, w)}
      Union(u, v)  // połącz składowe

  return MST
Złożoność czasowa Kruskala
$$O(E \log E) = O(E \log V)$$

Algorytm Prima

Algorytm Prima to zachłanny algorytm oparty na wierzchołkach, który rozwija MST z wierzchołka początkowego. W każdym kroku dodaje najtańszą krawędź łączącą wierzchołek w drzewie z wierzchołkiem poza drzewem.

Pseudokod Prima

function Prim(Graph, start):
  MST ← pusty zbiór
  inMST ← {start}
  PQ ← kolejka priorytetowa z krawędziami od start

  while PQ nie jest pusta and |inMST| < |V|:
    (w, u, v) ← wyciągnij minimum z PQ
    if v ∉ inMST:
      MST ← MST ∪ {(u, v, w)}
      inMST ← inMST ∪ {v}
      Dodaj wszystkie krawędzie z v do PQ

  return MST
Złożoność czasowa Prima (kopiec binarny)
$$O((V + E) \log V)$$

Kruskal vs Prim: Kiedy którego użyć?

CechaKruskalPrim
PodejścieOparte na krawędziach (sortowanie globalne)Oparte na wierzchołkach (lokalny wzrost)
Struktura danychUnion-FindKolejka priorytetowa
Złożoność czasowa\( O(E \log E) \)\( O((V + E) \log V) \)
Najlepszy dlaGrafów rzadkichGrafów gęstych
Grafy niespójneTworzy las rozpinającyRozpina tylko składową węzła początkowego
RównoległośćŁatwiejszy do zrównolegleniaZ natury sekwencyjny

Jak korzystać z tego kalkulatora

  1. Zdefiniuj krawędzie grafu: Wprowadź krawędzie w formacie węzeł1, węzeł2, waga, jedna na linię. MST operuje na grafach nieskierowanych, więc każda krawędź działa w obu kierunkach.
  2. Wybierz algorytm: Wybierz Kruskala dla grafów rzadkich lub Prima dla grafów gęstych. Oba dają optymalne MST.
  3. Ustaw węzeł początkowy (tylko Prim): Opcjonalnie określ, gdzie zaczyna się algorytm Prima. Wpływa to na kolejność wyboru krawędzi, ale nie na całkowitą wagę MST.
  4. Oblicz MST: Kliknij "Znajdź MST", aby uruchomić algorytm. Przeglądaj interaktywną wizualizację, tabelę krawędzi i śledzenie krok po kroku.
  5. Przejdź przez kroki: Użyj przycisków Dalej/Wstecz, aby obserwować wykonywanie algorytmu krok po kroku, z podświetleniem na płótnie w czasie rzeczywistym.

Zrozumienie wyników

Tabela krawędzi MST

Pokazuje każdą krawędź wybraną do MST w kolejności ich dodawania, wraz z poszczególnymi wagami i całkowitą wagą MST.

Wizualizacja grafu

Interaktywne płótno wyświetla graf z elementami kodowanymi kolorami:

  • Zielone węzły i krawędzie = Część MST
  • Pomarańczowe podświetlenia = Obecnie badane
  • Szare elementy = Nie są jeszcze częścią MST

Śledzenie krok po kroku

Pokazuje każdą decyzję algorytmu: która krawędź jest badana, czy została zaakceptowana czy odrzucona (i dlaczego) oraz aktualny stan budowy MST.

Rzeczywiste zastosowania MST

Projektowanie sieci

Najbardziej klasyczne zastosowanie. Łącząc węzły (miasta, serwery, urządzenia elektryczne) przy minimalnej całkowitej długości kabla, światłowodu lub rury, MST zapewnia optymalne rozwiązanie. Firmy telekomunikacyjne używają algorytmów opartych na MST, aby zminimalizować koszty infrastruktury.

Analiza skupień

W uczeniu maszynowym i nauce o danych, klasteryzacja oparta na MST (np. single-linkage clustering) grupuje punkty danych poprzez usuwanie najdłuższych krawędzi z MST. Tworzy to naturalne skupiska bez konieczności wcześniejszego określania liczby grup.

Segmentacja obrazu

Algorytmy widzenia komputerowego wykorzystują MST do segmentacji obrazów na znaczące regiony. Piksele są węzłami, wagi krawędzi reprezentują różnice w kolorze/intensywności, a przecinanie krawędzi MST oddziela odrębne obiekty.

Algorytmy aproksymacyjne

MST zapewnia 2-aproksymację dla metrycznego problemu komiwojażera (TSP). Waga MST jest dolną granicą optymalnej trasy TSP, a podwojenie krawędzi MST daje trasę w granicach 2x optymalnej.

Projektowanie obwodów

Projektowanie układów VLSI wykorzystuje MST (poprzez warianty drzewa Steinera) w celu zminimalizowania całkowitej długości przewodów łączących komponenty na płytce drukowanej, co redukuje opóźnienia sygnału i koszty produkcji.

Kluczowe właściwości MST

  • Właściwość przekroju: Dla dowolnego przekroju grafu, krawędź o minimalnej wadze przechodząca przez przekrój znajduje się w MST.
  • Właściwość cyklu: Dla dowolnego cyklu w grafie, krawędź o maksymalnej wadze w cyklu NIE znajduje się w MST (zakładając unikalne wagi).
  • Unikalność: Jeśli wszystkie wagi krawędzi są różne, MST jest unikalne. Przy powtarzających się wagach może istnieć wiele poprawnych MST o tej samej wadze całkowitej.
  • Podgraf: MST jest podgrafem o V-1 krawędziach i braku cykli.

Często zadawane pytania

Co to jest Minimalne Drzewo Rozpinające (MST)?

Minimalne Drzewo Rozpinające to podzbiór krawędzi spójnego, nieskierowanego i ważonego grafu, który łączy wszystkie wierzchołki razem przy minimalnej możliwej całkowitej wadze krawędzi, bez tworzenia żadnych cykli. MST posiada dokładnie V-1 krawędzi dla grafu o V wierzchołkach.

Jaka jest różnica między algorytmem Kruskala a algorytmem Prima?

Algorytmu Kruskala opiera się na krawędziach: sortuje wszystkie krawędzie według wagi i zachłannie dodaje te, które nie tworzą cykli, korzystając ze struktury danych Union-Find. Algorytm Prima opiera się na wierzchołkach: rozwija MST z węzła początkowego, zawsze dodając najtańszą krawędź łączącą drzewo z nowym wierzchołkiem, korzystając z kolejki priorytetowej. Oba algorytmy dają optymalne MST, ale mogą różnić się kolejnością wyboru krawędzi.

Kiedy powinienem użyć algorytmu Kruskala, a kiedy Prima?

Algorytm Kruskala jest ogólnie lepszy dla grafów rzadkich (mało krawędzi w stosunku do węzłów) z o złożoności czasowej O(E log E). Algorytm Prima jest lepszy dla grafów gęstych ze złożonością czasową O(E log V) przy użyciu kopca binarnego. Dla bardzo gęstych grafów, algorytm Prima z kopcem Fibonacciego osiąga O(E + V log V).

Czy graf może mieć wiele poprawnych MST?

Tak, graf może mieć wiele poprawnych MST, jeśli istnieją krawędzie o takich samych wagach. Różne MST będą miały tę samą całkowitą wagę, ale mogą zawierać inne krawędzie. Kruskal i Prim mogą wygenerować różne MST dla tego samego grafu, ale oba będą miały tę samą minimalną wagę całkowitą.

Jakie są rzeczywiste zastosowania MST?

MST są używane w projektowaniu sieci (minimalizacja długości kabli/światłowodów), układaniu płytek drukowanych, analizie skupień, segmentacji obrazu, budowie taksonomii, aproksymacji problemów NP-trudnych, takich jak problem komiwojażera (TSP), oraz budowie sieci drogowych, rurociągowych i elektrycznych przy minimalnych kosztach.

Czy MST działa na grafach niespójnych?

Prawdziwe MST wymaga grafu spójnego. Jeśli graf jest niespójny, algorytmy wygenerują Minimalny Las Rozpinający — zbiór MST, po jednym dla każdej spójnej składowej. Ten kalkulator wskaże, kiedy graf nie jest w pełni spójny.

Dodatkowe zasoby

Cytuj ten materiał, stronę lub narzędzie w następujący sposób:

"Kalkulator Minimalnego Drzewa Rozpinającego" na https://MiniWebtool.com/pl/kalkulator-minimalnego-drzewa-rozpinającego/ z MiniWebtool, https://MiniWebtool.com/

przez zespół miniwebtool. Zaktualizowano: 19 lutego 2026

Możesz także wypróbować nasz AI Rozwiązywacz Matematyczny GPT, aby rozwiązywać swoje problemy matematyczne poprzez pytania i odpowiedzi w języku naturalnym.

Zaawansowane działania matematyczne:

Popularne i zaktualizowane narzędzia:

Znajdź Minimum i MaksimumKalkulator celtyckiego zodiaku drzewaKalkulator choinki świątecznejZobacz wszystkie →
Strona główna > Matematyka > Zaawansowane działania matematyczne > Kalkulator Minimalnego Drzewa Rozpinającego