algorytm.org

Minimalne drzewo rozpinające

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Minimalne drzewo rozpinające
Ocena użytkowników:***** / 27
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 10 sierpnia 2005 19:09

Niech będzie dany spójny graf nieskierowany o wierzchołkach V i krawędziach E. Ponadto z każdą krawędzią będzie związana tzw. waga, określna przez funkcję w, która oznaczają długość danej krawędzi. Jeżeli znajdziemy taki podzbiór T zawarty w zbiorze krawędzi E, który łączy wszystkie wierzchołki i taki, że suma wszystkich wag krawędzi wchodzących w skład T jest możliwie najmniejszy, to znajdziemy tzw. minimalne drzewo rozpinające. Oto minimalne drzewo rozpinające dla przykładowego grafu:
Minimalne drzewo rozpinające
Suma wag dla tego drzewa wynosi 10

Jest znanych kilka algorytmów tworzące takie drzewo. Wszystkie one wykorzystują tzw. metodę "zachłanną". Do rozrastającego się drzewa dodawane są "najlepsze" krawędzie, w tym przypadku o najmniejszej wadze.

Opis algorytmu Kruskala.
Opis algorytmu Prima
Poprawiony: 30 sierpnia 2012 14:41
Komentarze
photo
-66 # p 2009-11-18 12:41
Gtraf na rysunku nie jest drzewem.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+56 # TheVirus 2009-11-26 12:05
Patrz tylko na zielone krawędzie
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz