Minimalne drzewa rozpinające

W 1926 roku Otakar Borůvka miał jak najtaniej zaplanować sieć elektryczną na południu Moraw. Jego pytanie, jak połączyć każde miejsce najmniejszą łączną długością linii, to problem minimalnego drzewa rozpinającego, a ma on jedne z najprostszych i najbardziej eleganckich rozwiązań w całej informatyce.

Graf, którego krawędzie mają długości, z wyróżnionymi krótkimi krawędziami rosnącego drzewa, pominiętą krawędzią, która zamknęłaby cykl, narysowaną czerwoną przerywaną linią, i listą krawędzi do sprawdzenia poniżej
Graf, którego krawędzie mają długości, z wyróżnionymi krótkimi krawędziami rosnącego drzewa, pominiętą krawędzią, która zamknęłaby cykl, narysowaną czerwoną przerywaną linią, i listą krawędzi do sprawdzenia poniżej

Problem

Weź spójny graf, którego krawędzie mają długości, czyli koszty. Drzewo rozpinające to zbiór krawędzi, który łączy wszystkie wierzchołki i nie zawiera cyklu; przy n wierzchołkach ma zawsze dokładnie n − 1 krawędzi, bo każda krawędź dołącza jeden wierzchołek więcej. Spośród wszystkich drzew rozpinających minimalne drzewo rozpinające ma najmniejszą łączną długość. Graf może mieć ogromną liczbę drzew rozpinających, ale nie trzeba sprawdzać ich wszystkich.

Dlaczego zachłanność działa

Podziel wierzchołki na dwie grupy w dowolny sposób. Najkrótsza krawędź przechodząca między grupami zawsze należy do jakiegoś minimalnego drzewa rozpinającego: gdyby drzewo używało zamiast niej dłuższej krawędzi między grupami, zamiana na krótszą połączyłaby te same wierzchołki taniej. To jest własność cięcia. Drugą stroną medalu jest własność cyklu: najdłuższa krawędź w dowolnym cyklu nigdy nie jest potrzebna. Oba algorytmy poniżej po prostu stosują te reguły raz po raz.

Przykład

Weź krawędzie A–B o długości 1, B–C 2, A–C 3, C–D 4 i B–D 5. Algorytm Kruskala bierze A–B, potem B–C, potem pomija A–C, bo A i C są już połączone i krawędź zamknęłaby cykl, a potem bierze C–D. Drzewo ma trzy krawędzie na cztery wierzchołki, więc jest gotowe, z łączną długością 7, a B–D nie zostaje nawet sprawdzona. Algorytm Prima od A najpierw dodaje B przez A–B; krawędź B–C (2) wygrywa z A–C (3) jako droga do C, więc C dołącza przez B–C; krawędź C–D (4) wygrywa z B–D (5), więc D dołącza przez C–D. To samo drzewo, to samo 7.

Kruskal, Prim i Borůvka

Algorytm Kruskala, opublikowany przez Josepha Kruskala w 1956 roku, sortuje krawędzie i używa struktury union-find, aby pomijać krawędzie wewnątrz jednej części, więc jego praca rośnie jak E log E. Algorytm Prima pierwszy opisał Vojtěch Jarník w 1930 roku, a ponownie odkryli go Robert Prim w 1957 i Edsger Dijkstra w 1959 roku; z kopcem binarnym jego praca rośnie jak E log V, a z prostą tablicą jak V², co jest dobre dla grafów gęstych. Algorytm Borůvki z 1926 roku pozwala każdej części jednocześnie wziąć swoją najkrótszą wychodzącą krawędź, co pasuje do komputerów równoległych.

Otakar Borůvka w 1981 roku. W 1926 poproszono go o jak najtańsze zaplanowanie sieci elektrycznej południowych Moraw i podał pierwszy algorytm drzewa rozpinającego o minimalnej wadze.
Otakar Borůvka w 1981 roku. W 1926 poproszono go o jak najtańsze zaplanowanie sieci elektrycznej południowych Moraw i podał pierwszy algorytm drzewa rozpinającego o minimalnej wadze.

Zastosowania

Minimalne drzewa rozpinające pomagają projektować tanie sieci kabli, rur i dróg. Dzielą dane na klastry: usuń najdłuższe krawędzie drzewa, a części, które zostaną, są klastrami. Dają szybką trasę w problemie komiwojażera, co najwyżej dwa razy dłuższą od najlepszej, gdy odległości spełniają nierówność trójkąta. A algorytm Kruskala lub Prima na siatce z losowymi długościami krawędzi to klasyczny sposób na wygenerowanie labiryntu.

Wypróbuj

Otwórz aplikację, wybierz Kruskala lub Prima i naciśnij Krok. Przy Kruskalu krawędzie, które zostały do sprawdzenia, są wypisane pod grafem od najkrótszej do najdłuższej; krawędzie, które zamknęłyby cykl, są rysowane czerwoną przerywaną linią. Przy Primie są tam wypisane wierzchołki czekające na dołączenie, z długością ich najlepszej krawędzi, rysowanej przerywaną linią. Uruchom oba na tym samym grafie i porównaj: kolejność jest inna, ale łączna długość zawsze ta sama.

Często zadawane pytania

Ile krawędzi ma drzewo rozpinające?

Dokładnie o jedną mniej, niż jest wierzchołków. Mniej krawędzi nie połączyłoby wszystkich wierzchołków, a jedna więcej zawsze tworzyłaby cykl.

Który jest szybszy, Kruskal czy Prim?

Algorytm Kruskala, który sortuje krawędzie, jest zwykle prostszy i szybki na grafach rzadkich z małą liczbą krawędzi. Algorytm Prima z kopcem dobrze radzi sobie na grafach gęstych, a ze zwykłą tablicą potrzebuje około V² kroków bez względu na liczbę krawędzi.

Co to jest union-find?

Struktura danych, która śledzi, które wierzchołki są w tej samej części. Odpowiada na pytanie „czy te dwa są połączone?” i łączy dwie części prawie natychmiast, a tego właśnie algorytm Kruskala potrzebuje przy każdej krawędzi.

Czy minimalne drzewo rozpinające działa dla grafów skierowanych?

Nie wprost. Dla grafów z krawędziami jednokierunkowymi odpowiednikiem jest minimalna arborescencja rozpinająca, którą wyznacza algorytm Chu–Liu/Edmonds.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Zbuduj minimalne drzewo rozpinające