Minimalne drzewo rozpinające
Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.
Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.
Wyznaczanie minimalnego drzewa rozpinającego
Minimalne drzewo rozpinające można wyznaczyć stosując algorytm Kruskala wykorzystujący strategię zachłanną. Algorytm ten polega na dołączaniu do rozwiązania kolejno najkrótszych możliwych krawędzi, aż do otrzymania drzewa rozpinającego. Przebieg algorytmu można zapisać następująco:
- Posortuj krawędzie rosnąco według ich wag, umieść je w kolejce.
- Pobierz z kolejki krawędź o najmniejszej wadze, usuń ją z kolejki.
- Jeśli wierzchołki łączone przez tę krawędź należą do różnych drzew (wówczas dołączenie krawędzi nie spowoduje utworzenia cyklu), dołącz krawędź do rozwiązania.
- Jeśli liczba krawędzi dołączonych do rozwiązania wynosi v-1 (v jest liczbą wierzchołków), zakończ działanie algorytmu. W przeciwnym razie przejdź do punktu 2.
Bibliografia
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Liczba głosów: 12.
Dodano: 18 października 2016 18:30, ostatnia edycja: 30 stycznia 2019 14:10.
Zobacz też
Sortowanie – zagadnienie polegające na uporządkowaniu elementów zbioru rosnąco lub malejąco według pewnego klucza. Zagadnienie to, ze względu na częstość występowania, jest bardzo istotne dla informatyki. Istnieje wiele różnych algorytmów realizujących sortowanie.
Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.
Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.
Quicksort, sortowanie szybkie – algorytm sortowania działający w średnim przypadku w czasie liniowo-logarytmicznym. Algorytm jest oparty na metodzie dziel i zwyciężaj. Nie jest to algorytm stabilny ani wykazujący zachowanie naturalne, jednak ze względu na efektywność jest algorytmem bardzo popularnym.