Strona 1 z 2
Algorytm Drzewo - dowolny jezyk programowania
: 02 grudnia 2009, 16:15
autor: fender666
Czy jest ktoś w stanie mi pomoc jakkolwiek, a dokładniej dając kod czy gotowy program, może już ktoś z was go pisał? Chodzi mi o program, który ukaże jak działa algorytm drzewa (Matematyka Dyskretna - Grafy). Czy jest ktoś w stanie mi pomoc?
: 02 grudnia 2009, 16:43
autor: jasiekmarc
Drzewa co? Jest mnóstwo algorytmów, które mają coś wspólnego z drzewami.
Tutaj masz na przykład dwa na minimalne drzewo rozpinające w grafie z wagami, ale wyobrażam sobie sortowanie z wykorzystaniem drzewa (heap-sort), kompresję tekstu (drzewa Huffmana), czy jakieś ohydne drzewa przedziałowe.
: 02 grudnia 2009, 16:51
autor: fender666
Wiesz co ogolnie z tego co mi prof. mowil to chcial program ktory pokaze dzialanie algorytmu drzewa takie byly jego slowa w domu przepisze jak powinien dzialac algorytm w pseudokodzie i wrzuce mam nadzieje ze mi pomozecie licze na Was
Oto fragment pseudokodu jaki znalazlem w ksiazce
Kod: Zaznacz cały
Algorytm DRZEWO(v)
{Dane: wierzchołek v w nieskonczonym grafie G}
{Wyniki: Zbiór krawędzi E drzewa spinającego składowej grafu G zawierającej v}
{zmienna pomocnicza: ciag V odwiedzanych wierzcholkow, ostatecznie V = V (G)}
Niech V: = {v} oraz E: = {zbior pusty}
Dopoki istnieja krawedzie w grafie G laczace wierzcholki ze zbioru V z wierzcholkami, ktore nie naleza do V, wykonuj wybierz taka krawedz {u,w} laczaca wierzcholek u nalezacy do V z wierzcholkiem w nienalezacym do V,
dolacz wierzcholek w do V i krawedz {u,w} do E
Jak cos bedzie jeszcze potrzebne moge wrzucic
: 02 grudnia 2009, 18:30
autor: jasiekmarc
No kurcze blade, czemu wy nie zadajecie waszym nauczycielom pytań, jak nie rozumiecie? Jeśli graf G jest nieskończony, to jak może dojść do przerwania procedury. Podejrzewam, że albo rąbnąłeś się ty, albo „profesor” i chodzi o znalezienie minimalnego drzewa spinającego algorytmem prima.
: 02 grudnia 2009, 20:02
autor: fender666
Ogólnie profesor powiedział tyle ile ja powiedziałem, podpowiedział mi że można użyć w tym programie np. macierzy nic więcej nie powiedział. Ten algorytm przepisałem z książki więc na pewno nie ma błędu. Jeśli myślisz, że to chodzi o to, to możesz mi jakoś kod udostępnić?
: 02 grudnia 2009, 23:00
autor: jasiekmarc
Mam wrażenie, że już to zrobiłem
http://www.jasiekmarc.cba.pl/prog/prima.cpp. C++ z użyciem STL. Przy czym nie jestem pewien, że to o ten algorytm chodziło „profesorowi”.
: 02 grudnia 2009, 23:05
autor: fender666
A masz może jeszcze coś innego na myśli oprócz tego programu? Jakąś inną opcję, która może pasować do tego mojego lekko niedokładnego opisu? W sensie profesor sam się za bardzo nie wysilił żeby to wyjaśnić.
: 03 grudnia 2009, 09:04
autor: Ister
: 03 grudnia 2009, 13:13
autor: fender666
Może zamiast się sam wymigiwać jakąś lekturą sam raczysz pomóc, czy nie potrafisz? A może potrafisz tylko innych poprawiać?
: 03 grudnia 2009, 23:14
autor: jasiekmarc
@Ister
Trudno, więcej w życiu zrobiłem cudzych prac domowych niż swoich. Krzywda mi się nie dzieje.
@fender666
Ale komuś się może zacząć dziać, jeśli się, człowieku, nie wysilisz. Opis jest na pewno niedokładny i na pewno błędny (Na wejściu nie może być NIESKOÑCZONY graf - takie rzeczy w algorytmice się nie zdarzają). Wszystkie dane mówią mi jednak, że chodzi o algorytm prima. Dlaczego?
1. W „Wynikach” masz zbiór krawędzi drzewa spinającego.
2. W procedurze, do już istniejącego drzewa dołączasz kolejne wierzchołki. Najprawdopodobniej najkrótszymi krawędziami.
Najkrótsze drzewo spinające, to takie, które wyczerpuje wszystkie wierzchołki grafu i ma najmniejszą sumaryczną wagę krawędzi. Robisz to tak:
1. Masz zawsze dwa zbiory. Zbiór wierzchołków, które już są w drzewie i zbiór tych, które są jeszcze poza.
2. Na początku do pierwszego wkładasz jeden (dowolny) wierzchołek, zaś reszta jest w drugim.
3. Za każdym razem wybierasz najkrótszą krawędź między zbiorami i w ten sposób włączasz kolejne wierzchołki.
4. Dopóki zbiór drugi nie będzie pusty.