Algorytm Drzewo - dowolny jezyk programowania

[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?

[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.

[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

[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.

[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ć?

[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”.

[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ć.

[Ister]

Polecam lekturę.

[fender666]

Polecam lekturę.

Może zamiast się sam wymigiwać jakąś lekturą sam raczysz pomóc, czy nie potrafisz? A może potrafisz tylko innych poprawiać?

[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.