A minimalne drzewo rozpinające (MST) jest zdefiniowany jako drzewo rozpinające który ma minimalną wagę spośród wszystkich możliwych drzew rozpinających
A drzewo rozpinające definiuje się jako drzewiasty podgraf połączonego, nieskierowanego grafu, który zawiera wszystkie wierzchołki grafu. Lub, mówiąc słowami Laymana, jest to podzbiór krawędzi grafu, który tworzy drzewo ( acykliczny ), gdzie każdy węzeł grafu jest częścią drzewa.
Minimalne drzewo rozpinające ma wszystkie właściwości drzewa rozpinającego z dodatkowym ograniczeniem posiadania minimalnych możliwych wag spośród wszystkich możliwych drzew rozpinających. Podobnie jak drzewo opinające, również graf może mieć wiele możliwych MST.
Właściwości drzewa opinającego:
Drzewo opinające zawiera niżej wymienione zasady :
- Liczba wierzchołków ( W ) na wykresie, a drzewo opinające jest takie samo.
- W drzewie rozpinającym istnieje stała liczba krawędzi, która jest o jeden mniejsza niż całkowita liczba wierzchołków ( I = V-1 ).
- Drzewo opinające nie powinno być bezładny , ponieważ powinno istnieć tylko jedno źródło komponentu, nie więcej.
- Drzewo opinające powinno być acykliczny, Który oznacza, że w drzewie nie byłoby żadnego cyklu.
- Całkowity koszt (lub wagę) drzewa opinającego definiuje się jako sumę wag krawędzi wszystkich krawędzi drzewa opinającego.
- Graf może mieć wiele możliwych drzew rozpinających.
Minimalne drzewo rozpinające:
A minimalne drzewo rozpinające (MST) jest zdefiniowany jako drzewo rozpinające który ma minimalną wagę spośród wszystkich możliwych drzew rozpinających.
kolekcje Java
Minimalne drzewo rozpinające ma wszystkie właściwości drzewa rozpinającego z dodatkowym ograniczeniem posiadania minimalnych możliwych wag spośród wszystkich możliwych drzew rozpinających. Podobnie jak drzewo opinające, również graf może mieć wiele możliwych MST.
- Spójrzmy na MST powyższego przykładowego wykresu,
Minimalne drzewo rozpinające
Algorytmy znajdowania minimalnego drzewa rozpinającego:
Istnieje kilka algorytmów znajdowania minimalnego drzewa rozpinającego z danego wykresu, niektóre z nich są wymienione poniżej:
apurva padgaonkar
Algorytm minimalnego drzewa opinającego Kruskala:
Jest to jeden z popularnych algorytmów znajdowania minimalnego drzewa rozpinającego na podstawie połączonego, nieskierowanego wykresu. To jest Najpierw sortuje wszystkie krawędzie wykresu według ich wag,
Algorytm ten można efektywnie zaimplementować przy użyciu struktury danych DSU (Disjoint-Set) w celu śledzenia połączonych elementów wykresu. Jest to wykorzystywane w różnych praktycznych zastosowaniach, takich jak projektowanie sieci, klastrowanie i analiza danych.
Postępuj zgodnie z artykułem na Algorytm minimalnego drzewa rozpinającego Kruskala dla lepszego zrozumienia i implementacji algorytmu.
Algorytm minimalnego drzewa rozpinającego Prima:
Jest to również algorytm zachłanny. Algorytm ten ma następujący przepływ pracy:
- Rozpoczyna się od wybrania dowolnego wierzchołka, a następnie dodania go do MST.
- Następnie wielokrotnie sprawdza minimalną wagę krawędzi łączącą jeden wierzchołek MST z innym wierzchołkiem, który nie znajduje się jeszcze w MST.
- Proces ten jest kontynuowany, aż wszystkie wierzchołki zostaną uwzględnione w MST.
Aby efektywnie wybrać minimalną wagę krawędzi dla każdej iteracji, algorytm ten używa kolejki priorytetowej do przechowywania wierzchołków posortowanych aktualnie według ich minimalnej wagi krawędzi. Jednocześnie śledzi MST przy użyciu tablicy lub innej struktury danych odpowiedniej do typu danych, które przechowuje.
Algorytmu tego można używać w różnych scenariuszach, takich jak segmentacja obrazu na podstawie koloru, tekstury lub innych cech. W przypadku wyznaczania trasy, na przykład znajdowania najkrótszej ścieżki między dwoma punktami, którą może podążać ciężarówka dostawcza.
Postępuj zgodnie z artykułem na Algorytm minimalnego drzewa rozpinającego Prima dla lepszego zrozumienia i implementacji tego algorytmu.
Algorytm minimalnego drzewa rozpinającego Boruvki:
Jest to również algorytm przechodzenia po grafie używany do znalezienia minimalnego drzewa rozpinającego połączonego, nieskierowanego wykresu. Jest to jeden z najstarszych algorytmów. Algorytm działa poprzez iteracyjne budowanie minimalnego drzewa rozpinającego, zaczynając od każdego wierzchołka grafu jako osobnego drzewa. W każdej iteracji algorytm znajduje najtańszą krawędź łączącą drzewo z innym drzewem i dodaje tę krawędź do minimalnego drzewa rozpinającego. Jest to prawie podobne do algorytmu Prima służącego do znajdowania minimalnego drzewa rozpinającego. Algorytm ma następujący przepływ pracy:
- Zainicjuj las drzew, w którym każdy wierzchołek grafu będzie osobnym drzewem.
- Dla każdego drzewa w lesie:
- Znajdź najtańszą krawędź łączącą go z innym drzewem. Dodaj te krawędzie do minimalnego drzewa rozpinającego.
- Zaktualizuj las, łącząc drzewa połączone dodanymi krawędziami.
- Powtarzaj powyższe kroki, aż las będzie zawierał tylko jedno drzewo, czyli minimalne drzewo rozpinające.
Algorytm można zaimplementować przy użyciu struktury danych, takiej jak kolejka priorytetowa, aby skutecznie znaleźć najtańszą krawędź między drzewami. Algorytm Boruvki jest prostym i łatwym do wdrożenia algorytmem znajdowania minimalnych drzew rozpinających, ale może nie być tak skuteczny jak inne algorytmy w przypadku dużych grafów z wieloma krawędziami.
Postępuj zgodnie z artykułem na Algorytm minimalnego drzewa rozpinającego Boruvki dla lepszego zrozumienia i implementacji tego algorytmu.
Aby dowiedzieć się więcej o właściwościach i charakterystyce Minimalnego Drzewa Rozpinającego, kliknij Tutaj.
Zastosowania minimalnych drzew rozpinających:
- Projekt sieci : W projektowaniu sieci można zastosować drzewa opinające, aby znaleźć minimalną liczbę połączeń wymaganych do połączenia wszystkich węzłów. W szczególności minimalne drzewa rozpinające mogą pomóc zminimalizować koszty połączeń poprzez wybór najtańszych krawędzi.
- Przetwarzanie obrazu : Drzewa opinające można wykorzystać w przetwarzaniu obrazu w celu zidentyfikowania regionów o podobnej intensywności lub kolorze, co może być przydatne w zadaniach segmentacji i klasyfikacji.
- Biologia : Drzewa rozpinające i minimalne drzewa rozpinające można wykorzystać w biologii do konstruowania drzew filogenetycznych reprezentujących ewolucyjne relacje między gatunkami lub genami.
- Analiza sieci społecznościowych : Drzewa opinające i minimalne drzewa opinające można wykorzystać w analizie sieci społecznościowych w celu zidentyfikowania ważnych powiązań i relacji między jednostkami lub grupami.
Niektóre popularne problemy z rozmowami kwalifikacyjnymi na MST
| 1. | Znajdź minimalny koszt połączenia wszystkich miast | Ćwiczyć |
Niektóre często zadawane pytania dotyczące minimalnych drzew rozpinających:
1. Czy dla danego grafu może istnieć wiele drzew o minimalnym rozpinaniu?
Tak, graf może mieć wiele minimalnych drzew rozpinających, jeśli istnieje wiele zestawów krawędzi o tej samej minimalnej wadze całkowitej.
2. Czy algorytm Kruskala i algorytm Prima można zastosować do grafów skierowanych?
Nie, algorytmy Kruskala i Prima są przeznaczone wyłącznie do grafów nieskierowanych.
3. Czy graf rozłączony może mieć minimalne drzewo rozpinające?
Nie, rozłączony graf nie może mieć drzewa rozpinającego, ponieważ nie obejmuje wszystkich wierzchołków. Dlatego też nie może mieć minimalnego drzewa rozpinającego.
25 c do k
4. Czy przy pomocy algorytmu Dijkstry można znaleźć minimalne drzewo rozpinające?
Nie, algorytm Dijkstry służy do znajdowania najkrótszej ścieżki między dwoma wierzchołkami w grafie ważonym. Nie jest przeznaczony do wyszukiwania minimalnego drzewa rozpinającego.
5. Jaka jest złożoność czasowa algorytmów Kruskala i Prima?
Zarówno algorytmy Kruskala, jak i Prima mają złożoność czasową wynoszącą O(ElogE) , gdzie E jest liczbą krawędzi grafu.