Algorytmy i struktury danych - Grafy i ich reprezentacje Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Grafy i ich reprezentacje
MENUGA
ÓWNE
Grafy i ich reprezentacje
Start
Struktury danych - Klasyczne
Napisał Michał Knasiecki
Algorytmy
czwartek, 28 lipiec 2005
Kryptografia
Na początek kilka definicji:
W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów
Struktury danych
(wierzchołków, oznaczanych przez V) wzajemnie połącznonych za pomocą krawędzi
(oznacznych przez E).
Kursalgorytmiki
Grafy dzielimy na grafy skierowane i nieskierowane:
Praktyka
Mapaserwisu
Historia strony
Współautorzy/ CV
Rys.1. Graf nieskierowany Rys.2. Graf skierowany
Forum
Jeśli krawędz
łączy dwa wierzchołki to jest z nimi incydentna
.
Zgłoś błąd
Pętla własna to krawędz
łączące wierzchołek z samymsobą.
Stopień wierzchołka w grafie nieskierowanymto liczba incydentnych z nimkrawędzi.
Szukaj
Istnieje kilka algorytmówdo przechowania grafu w pamięci.
Omówmy najpierw macierz sąsiedztwa.
Budujemy tablicę o rozmiarach V*V, gdzie V-liczba wierzchołków. Następnie wypełniamy ją
Tani Internet MULTIMO -
zerami- jeśli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki
już za 10 zł netto. Zobacz
są połączone. Oto macierz sąsiedztwa dla grafu z rysunku 1:
www.multimo.pl
1 2 3 4 5
1 0 1 1 0 1
2 1 0 1 1 1
3 1 1 0 1 0
4 0 1 1 0 1
5 1 1 0 1 0
Złożoność pamięciowa
O(V2)
Widać, że macierz jest symetryczna. Stosując tablicę dynamiczną można więc zmniejszyć
rozmiar macierzy do połowy zapisując ją jako macierz dolno-(górno)-trójkątną.
Lista incydencji.
Należy utworzyć listę dla każdego wierzchołka v, w której przechowujemy zbiór
wierzchołkówpołączonych krawędzią z v. Lista dla grafu z rysunku 1 wygląda następująco:
: 2, 3, 5
1
: 1, 3, 4
2
: 1, 2, 4
3
: 2, 3, 5
4
: 4, 1
5
http://www.algorytm.org/index.php?option=com_content&task=view&id=44&Itemid... 2007-10-06 18:44:33
Algorytmy i struktury danych - Grafy i ich reprezentacje Strona 2
Złożoność pamięciowa O(V+E)
Lista krawędzi jest to lista, na której przechowujemy wszystkie krawędzie występujące w
grafie.
Przykład dla grafu skierowanego z rys.2:
1 - 2
2 - 4
2 - 5
3 - 1
3 - 2
4 - 3
5 - 1
5 - 4
Zapisując przy pomocy tej reprezentacji graf, w którym występują krawędzie skierowane i
nieskierowane należy w przypadku krawędzi nieskierowanej z u do v zapisać krawędz

dwukrotnie: u - v oraz v - u.
Złożoność pamięciowa O(E)
Macierz incydencji to tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy,
jeśli krawędz
wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie (-1), jeśli
do niego wchodzi piszemy (+1), jeśli wierzchołek nie należy do krawędzi piszemy 0, jeśli jest
to pętla własna piszemy 2.
Oto przykład dla grafu z rys. 2.
1 2 3 4 5
1 - 2 -1 1 0 0 0
1 - 3 1 0 -1 0 0
1 - 5 1 0 0 0 -1
0
2 - 4 -1 0 1 0
0
2 - 5 -1 0 0 1
2 - 3 0 1 -1 0 0
3 - 4 0 0 1 -1 0
5 - 1 1 0 0 0 -1
5 - 4 0 0 0 1 -1
Złożoność pamięciowa O(E*V)
Macierz grafu została opracowana w Instytucie Informatyki PP przez dr M. Sternę. Jest to
trochę bardziej skomplikowana reprezentacja grafu niż poprzednie.
Należy utworzyć tablicę o rozmiarach (V+2)2. Wiersze i kolumny numerujemy od 0 do V+1.
Najpierw zajmiemy się częścią macierzy ograniczoną przez indeksy od 1 do V.Zał. że w
wierszach mamy i-te wierzchołki a wkolumnach j-te wierzchołki. Liczby, które mogą znalez
ć
się na skrzyżowaniu wierzchołka i oraz j można podzielić na 3 grupy:
od 1 do V - istnieje krawędz
skierowana: i <- j
od V+1 do 2*V - istnieje krawędz
skierowana: i -> j
od (-V) do (-1) - brak incydentnych krawędzi
Cały sekret macierzy grafu polega jednak na tym, że odczytana wartość nie tylko informuje
nas, czy istnieje krawędz
łącząca wierzchołki i oraz j, ale zawiera też adres następnego
wierzchołka, który jest wtakiej samej relacji z wierzchołkiem i co wierzchołek j.
Podam teraz kilka przykładów dla grafu z rys. 2. Liczba wierzchołków jest równa 5.
http://www.algorytm.org/index.php?option=com_content&task=view&id=44&Itemid... 2007-10-06 18:44:33
Algorytmy i struktury danych - Grafy i ich reprezentacje Strona 3
Prześledzimy sytuację dla wierzchołka 1. w grafie mamy następujące krawędzie zawierające
ten wierzchołek:
1 -> 2
<-
1 3
<-
1 5
Wez
my pierwszą krawędz
: wierzchołek 2 jest jedynym następnikiem wierzchołka 1, więc w
macierzy w komórce [1,2] musimy podać adres wierzchołka 2. Aby obliczyć adres
wierzchołka nr. 2 (mamy do czynienia z następnikiem) wystarczy dodać do niego liczbę
wierzchołkóww grafie: 2+5=7. Taką liczbę zapisujemy w komórce [1,2].
Przejdz
my do krawędzi drugiej: wierzchołek 3 jest poprzednikiem wierzchołka 1, ale (w
przeciwieństwie do następników) nie jedynym: także wierzchołek 5 jest poprzednikiem
wierzchołka 1 (ostatnia krawędz
na naszej liście). W komórce [1,3] musimy więc podać
adres wierzchołka 5. Ponieważ jest to poprzednik, więc adresemwierzchołka 5 jest 5.
Przechodzimy do ostatniej krawędzi: wierzchołek 5 jest poprzednikiem wierzchołka,
ponieważ jest jego ostatnim poprzednikiem (pierwszymbył wierzchołek 3) w komórce [1,5]
podajemy adres wierzchołka 5, czyli znówwpisujemy 5.
W naszej macierzy musimy podać także wierzchołki, które nie są połączone z
wierzchołkiem 1 krawędzią. Punktem wyjściowym listy tych wierzchołków dla każdego
wierzchołka i jest on sam(stąd: macierz grafu nie nadaje się dla grafób z pętlami własnymi)
, lista ta zaczyna się więc w komórce [i,i]. A więc wiemy, że wierzchołek 1 nie jest
połączony krawędzią ze sobą samym oraz wierzchołkiem 4. W komórce [1,1] musimy
podać adres wierzchołka 4, z godnie z tyum co napisałem powyżej, adresy wierzchołków,
które nie są połączone z danym wierzchołiek podaje się poprzedzając numer wierzchołka
znakiem"-". Więc w komórce [1,1] piszemy (-4). Jednocześnie wierzchołek 4 jest ostatnim
wierzchołkiem, z którymnie łączy się wierzchołek 1, więc w komórce [1,4] podajemy znów
adres wierzchołka 4, czyli [1,4]=(-4).
Teraz zajmiemy się pozostałą częścią macierzy: kolumjną nr. 0 i (V+1) oraz wierszemnr. 0
i (V+1). Bez nich możnaby już zapisać graf za pomocą macierzy, lecz dzięki nim będziemy
mieli dostęp do listy poprzedników i następników w czasie O(E). A więc: komórka [i,0]
zawiera pierwszy poprzednik wierzchołka i-tego natomiast komórka [0,i] ostatni poprzednik.
W przykładzie (dotyczącym wierzchołka 1) zapiszemy [1,0]=3, [1,0]=3, ponieważ
pierwszym i ostatnim poprzednikiem wierzchołka 1 jest 3. Podobnie jest z następnikami:
[i,V+1] rozpoczyna listę następników wierzchołka i-tego a [V+1,i] kończy, a więc [1,6]=2,
[6,1]=5, gdyż pierwszym następnikiem wierzchołka 1 jest 2 a ostatnim 5. W ten sposób
wypełniliśmy pierwszy wiersz macierzy grafu.
Dodam jeszcze, że jeżeli jakiś wierzchołek nie ma następników lub poprzedników to na
początku i końcu listy odpowiednio: następników lub poprzedników wpisujemy 0. Poniżej
zamieszczam całą macierz dla grafu z rys. 2 (w kolumnach znajdują się wierzchołki j, w
wierszach wierzchołki i).
0 1 2 3 4 5 6
0 X 3 3 4 5 2 X
3
1 -4 7 5 -4 5 2
2 1 3 -2 3 10 10 4
3 4 7 7 -5 4 -5 1
2
4 -1 5 8 -1 5 3
5 2 9 2 -3 9 -3 1
6 X 2 5 2 3 4 X
Dla lepszego zrozumienia macierzy grafu proponuję narysować graf na podstawie macierzy
i sprawdzić, czy jest to graf z rys. 2.
Dzięki dodatkowymkolumnomi wierszomzyskujemy listy następnikówi poprzedników:
wkolumnie 0: wskaz
nik do pierwszego elementu na liście poprzedników
wwierszu 0: wskaz
nik do ostatniego elementu na liście poprzedników
wkolumnie V+1: wskaz
nik do pierwszego elementu na liście następników
wwierszu V+1: wskaz
nik do ostatniego elementu na liście następników
na głównej przekątnej: wskaz
nik do pierwszego elementu na liście elementów nie
będących ani następnikami ani poprzednikami
http://www.algorytm.org/index.php?option=com_content&task=view&id=44&Itemid... 2007-10-06 18:44:33
Algorytmy i struktury danych - Grafy i ich reprezentacje Strona 4
Złożoność pamięciowa
O((V+2)2)
Ostatnia aktualizacja ( wtorek, 18 wrzesień 2007 )
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=44&Itemid... 2007-10-06 18:44:33
Algorytmy i struktury danych - Grafy i ciąg dalszy Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Reklama FAQ
Kontakt
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Grafy i ciąg dalszy
MENUGA
ÓWNE
Grafy i ciąg dalszy
Start
Struktury danych - Klasyczne
Napisał Michał Knasiecki
Algorytmy
czwartek, 28 lipiec 2005
Kryptografia
Oto dodatkowe informacje na
temat grafów, potrzebne w bardziej skomplikowanych algorytmach.
Struktury danych
Kilka definicji:
Stopień wierzchołka - to liczba krawędzi do niego przyległych
Kursalgorytmiki
Graf regularny - to graf, w którymkażdy wierzchołek ma taki samstopień
Praktyka Graf planarny - to graf, który można przedstawić na płaszczyz
nie tak, by żadne dwie
krawędzie się nie przecinały
f-graf - to graf z ograniczonym stopniem wierzchołka, tzn. jego stopień nie może być
Mapaserwisu
większy niż f
Graf prosty - to graf bez pętli własnych i krawędzi równoległych
Historia strony
Niezmiennik grafu - to liczba lub ciąg liczb, który zależy tylko od struktury grafu a nie od
sposobu jego poetykietowania (np. liczba wierzchołków, liczba krawędzi)
Współautorzy/ CV
Liczba chromatyczna grafu - to najmniejsza liczba kolorów potrzebnych do pokolorowania
wierzchołkówgrafu tak, by żadne dwa przyległe wierzchołki nie były tego samego koloru
Forum
Przykładu do powyższych definicji:
Zgłoś błąd
Szukaj
Taniej nie będzie! AGD,
RTV, Foto, GSM, Car
Audio. stopień wierzchołka 1=2, wierzchołka 2=3, graf planarny, f-graf dla f=3
graf 2-regularny, planarny
graf planarny, f-graf dla f=4
graf planarny, liczba chromatyczna wynosi 3
Teraz przejdz
my do bardzo ważnego problemu: generowania grafówlosowych.
Istnieje kilka modeli grafówlosowych, omówimy najważnejsze
p
http://www.algorytm.org/index.php?option=com_content&task=view&id=43&Itemid... 2007-10-06 18:45:12
Algorytmy i struktury danych - Grafy i ciąg dalszy Strona 2
model G(n,p) - n (liczba wierzchołków) jest dana, p jest tzw. prawdopodobieństwem
krawędziowym (0<=p<=1). Liczba p jest określona dla każdej krawędzi, określa ono
prawdzopodobieństwo, że dana krawędz
znajdzie się w grafie
model G(n,k) - n jest dana, ze zbioru wszystkich możliwych krawędzi są losowane
kolejne krawędzie, lecz tu, w odróżnieniu do poprzedniego modelu, z jednakowym
prawdopodobieństwem
model G(n,f) - n jest dana, f oznacza maksymalny stopień wierzchołka, którego nie
można przekroczyć.
Przy losowaniu grafówstosuje się często tzw. metodę przesiewania (lub sito, wykorzystane
przez Eratostenesa przy wyznaczaniu liczb pierwszych). Dzieli się ona na kilka części:
1. wybór odpowiedniego generatora (zgodnie z powyższymi modelami)
2. każdy wygenerowany graf jest weryfikowany, czy spełnia założenia wybranego
modelu (np. czy jego największy stopień nie jest większy niż f), grafy które ich nie
spełniają są odrzucane, reszta jest zapisywana np. w pliku
3. po zakończeniu generowania w pliku znajdują się grafy spełniające założenia
danego modelu. Należy jeszcze sprawdzić, czy grafy te są różne, tzn. czy nie ma
wśród nich grafówizomorficznych
Testowanie izomorfizmu jest problemem trudnym. Nie ma żadnego szybkiego algorytmu
sprawdzającego, czy dwa grafy są izomorficzne. Powodem tego jest wiele kryteriów
izomorfizmu grafów, jeżeli dane grafy nie spełniają jekiegoś kryterium, należy przejść do
kolejnego (co zwiększa koszt obliczeń).
Kryteriumizomorfizmu grafów:
1. jednakowa liczba wierzchołków
2. jednakowa liczba krawędzi
3. jednakowy ciąg stopni wierzchołków
4. jendakowe ciągi stopni wierzchołkówdla sąsiadów
5. jednakowa liczba trójkątów(cykli o długości 3)
6. tworzenie macierzy odległości
Pierwsze dwa kroki można wykonać wprawdzie w czasie Ś(n), lecz w punkcie 5 czas
zaczyna gwałtownie wzrastać.
Ostatnia aktualizacja ( czwartek, 28 lipiec 2005 )
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=43&Itemid... 2007-10-06 18:45:12
Algorytmy i struktury danych - Drzewa BSP Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Drzewa BSP
MENUGA
ÓWNE
Drzewa BSP
Start
Struktury danych - Klasyczne
Napisał Tomasz Nędza
Algorytmy
czwartek, 28 lipiec 2005
Kryptografia
Ciekawym rodzajem drzewa
jest drzewo BSP. Jest to rozwinięcie pomysłu wykorzystanego w drzewie BST - całość
Struktury danych
działa na prawie identycznych zasadach. Pomimo, że wymaga na początku bardzo
czasochłonnego budowania, jest to wydajna metoda obliczania zależności widoczności
Kursalgorytmiki
wśród grupy wielokątów 3Doglądanych z dowolnego punktu na scenie. Za każdym razem,
Praktyka gdy zmienia się położenie obserwatora, wykonywany jest liniowy algorytm wyświetlania.
A
atwo zauważyć po złożoności poszczególnych części algorytmu, że metoda ta dobrze
nadaje się do zastosowań, wktórych zmienia się punkt obserwacji, natomiast same obiekty
Mapaserwisu
pozostają niezmienne. Pierwsza część algorytmu polega na zbudowaniu drzewa binarnego
ścian składających się na scenę. W korzeniu tego drzewa umieszczany jest dowolny
Historia strony
wielokąt ze sceny. Dla prawidłowości algorytmu nie ma znaczenia, który wielokąt
wybierzemy. Za pomocą tego wielokąta (a raczej za pomocą płaszczyzny, na której ten
Współautorzy/ CV
wielokąt się znajduje) następuje podział pozostałych ścian na dwie grupy, w zależności od
tego, w której półprzestrzeni się znajdują. Do pierwszej półprzestrzeni należą wszystkie
Forum
pozostałe wielokąty znajdujące się przed wielokątem z korzenia, a druga zawiera wielokąty
leżące za wielokątem korzenia. Niektóre wielokąty (znajdujące się jednocześnie w obu
Zgłoś błąd
półprzestrzeniach) muszą być podzielone przez wspomnianą płaszczyznę, a następnie ich
części są przypisywane do odpowiednich grup. Dla każdej grupy powtarzamy
Szukaj
dotychczasowe kroki algorytmu, to znaczy wybieramy wielokąt do korzenia (staje się on
przednim albo tylnym potomkiem) i dzielimy pozostałe ściany. Algorytm budowy drzewa
Taniej nie będzie! AGD, BSP kończy się, gdy każdy węzeł zawiera tylko jeden wielokąt. Myślę, że najłatwiej będzie
RTV, Foto, GSM, Car to zrozumieć na przykładzie. Przypuśćmy, że dany mamy następujący zestaw ścian (rzut z
Audio. góry):
Strzałki przy ścianach oznaczają ich normalne, czyli
kierunek, z którego płaszczyzna może być oglądana.
A
atwo spostrzec, że rzut przedstawia pomieszczenie z
dużym filarem. Liczby oznaczają numery danych ścian
(za ich pomocą będziemy przedstawiać je w drzewie
BSP). Na rysunku tym widać sytuację, o której już
wspomniałem - nie zawsze można odpowiedzieć na
pytanie, po której stronie danej ściany leży inna ściana.
Gdy wybierzemy na przykład ścianę numer 5, nie
będziemy mogli powiedzieć, czy ściana 2 leży z przodu
czy też z tyłu. W zasadzie leży po obu stronach. W tym
przypadku należy podzielić problematyczną ścianę na dwie części. Aby budowę drzewa
BSP bardziej upodobnić do tworzenia drzewa BST, trochę zmienię sposób postępowania.
Będę brał po jednej ścianie i wstawiał w odpowiednie miejsce drzewa BSP. Wsumie jednak
otrzymamy równoważne drzewo. Zacznijmy więc budowanie. Pierwszą ścianą do
wstawienia niech będzie na przykład ściana 5. Jako że drzewo jest puste, wstawiamy tę
ścianę do korzenia.
Dla ułatwienia przy "wskaz
nikach" umieszczę początkowo nazwę
półprzestrzeni, jaka jest wskazywana.
Kolejną wstawianą ścianą będzie ściana nr 1. Z rysunku widać, że
cała jest w "przedniej" półprzestrzeni względem ściany 5, więc
umieścimy ją jako jej lewego potomka. Teraz chcę wstawić ścianę
nr 3. Ścianę tą będę musiał podzielić, gdyż znajduje się i z przodu,
i z tyłu względem ściany 5. Podobnie zrobię od razu ze ścianą nr
2.
Czerwonymi kreskami oznaczę
http://www.algorytm.org/index.php?option=com_content&task=view&id=42&Itemid... 2007-10-06 18:46:15
Algorytmy i struktury danych - Drzewa BSP Strona 2
miejsca podziału ścian. W wyniku tego działania otrzymałem nowe ściany: 3, 10, 9 oraz 2.
Wstawię je teraz do drzewa. Ściana nr 3 jest z przodu ściany nr 5 oraz z przodu ściany nr
1, więc znajdzie się wlewym poddrzewie węzła 1. To samo robię ze ścianą nr 2. Schemat
otrzymanego drzewa znajduje się po lewej.
Do zbadania pozostały namjeszcze ściany 10, 4, 9, 8,
7 i 6. Wstawmy ścianę nr 7. Znajduje się ona z tyłu
ściany nr 5. Trafi więc do prawego poddrzewa. Ściana
nr 6 także trafi do prawego poddrzewa względem
głównego korzenia, ale po porównaniu ze ścianą nr 7
(pamiętajmy, że ona tam się już znajduje) okaże się,
że nr 6 będzie jej prawympotomkiem. Wstawmy teraz
ścianę numer 8, a następnie ścianę nr 4.
Problem pojawi
się przy
ścianach nr 9 i
10, ale
wystarczy je
podzielić w
pokazany
sposób i wstawienie ich do drzewa nie powinno
sprawić trudności. Końcowa postać drzewa
prezentuje się następująco (schemat poniżej):
Drzewo to jest kluczem do prawidłowego posortowania naszych ścian podczas rysowania.
Jeżeli obserwator znajduje się przed ścianą znajdującą się w korzeniu (w półprzestrzeni
wskazywanej przez jej wektor normalny), to wyświetlanie należy rozpocząć od ścian z tylnej
półprzestrzeni. Znajdują się w niej przecież ściany, które mogą być zasłonięte na ekranie
przez wielokąt z korzenia. Następnie należy oczywiście wyświetlić ścianę znajdującą się w
korzeniu, a na końcu wszystkie wielokąty leżące przed tą ścianą. W przypadku gdy
obserwator jest w tylnej półprzestrzeni, najpierw trzeba wyświetlić wszystkie wielokąty z
przedniej półprzestrzeni korzenia, potem wielokąt znajdujący się w korzeniu i wreszcie
wszystkie wielokąty w jego tylnej półprzestrzeni. Załóżmy, że obserwator znajduje się w
punkcie A. Jego pozycję testujemy względem położenia ścian według poniższego
algorytmu:
Korzeń zawiera ścianę nr 5. Ponieważ punkt A znajduje się z przodu tej ściany,
przechodzimy wdrzewie do poddrzewa po prawej.
Napotykamy na kolejny test. Tym razem względem ściany nr 7. Punkt A znajduje się z
tyłu tej ściany, więc wchodzimy wpoddrzewo po stronie lewej.
Znalez
liśmy się w węz
le, który posiada jedynie jednego potomka, więc przechodzimy
tambez żadnych testów. Wwęz
le ze ścianą nr 11 powtarzamy tą czynność.
Znajdujemy się w węz
le ze ścianą nr 9. Oba jej wskaz
niki mają wartość nil, więc
wracamy do pierwszego "rozgałęzienia" w górę, zapamiętując kolejne "mijane" ściany (a
więc kolejno: 9, 11, 4, 7).
Wchodzimy teraz w prawe poddrzewo.
Znównapotykamy na test. Tymrazem chodzi o określenie położenia punktu A względem
ściany nr 6. Znajduje się on z przodu tej ściany, a więc wchodzimy w prawe poddrzewo.
Węzeł ze ścianą nr 8 ma tylko jednego potomka, a więc przechodzimy do ściany nr 10.
Powracając w górę zapamiętujemy "odwiedzone" ściany (aktualna tablica ścian: 9, 11, 4,
7, 10, 8, 6).
Z węzła ze ścianą nr 6 przechodzimy w lewe poddrzewo. Jest to pojedyncza ściana, a
więc powracamy wgórę - do węzła nr 5.
Przechodzimy do lewej gałęzi. Dochodzimy aż do węzła ze ścianą nr 2, po czym
następuje powrót do korzenia.
http://www.algorytm.org/index.php?option=com_content&task=view&id=42&Itemid... 2007-10-06 18:46:15
Algorytmy i struktury danych - Drzewa BSP Strona 3
Po całymprzejściu drzewa otrzymaliśmy następującą kolejność ścian: 9, 11, 4, 7, 10, 8,
6, 12, 5, 2, 3, 1
Wcelu wyświetlenia poprawnie wyglądającej sceny, należy teraz wszystkie ściany rysować
w takiej kolejności, jaką uzyskaliśmy podczas przeglądania drzewa.
Ostatnia aktualizacja ( czwartek, 28 lipiec 2005 )
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=42&Itemid... 2007-10-06 18:46:15
Algorytmy i struktury danych - Minimalne drzewo rozpinające Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
Start Struktury danych Klasyczne Minimalne drzewo
template designedby peekmambo.com
rozpinające
MENUGA
ÓWNE
Minimalne drzewo rozpinające
Start
Napisał Michał Knasiecki
środa, 10 sierpień 2005
Algorytmy
Niech będzie dany spójny
Kryptografia graf nieskierowany o wierzchołkach V i krawędziach E. Ponad to z każdą krawędzią będzie
związana tzw. , określna przez funkcję w, która oznaczają długość danej krawędzi.
waga
Struktury danych
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
Kursalgorytmiki
najmniejszy, to znajdziemy tzw. minimalne drzewo rozpinające
. Oto minimalne drzewo
rozpinające dla przykładowego grafu:
Praktyka
Mapaserwisu
Historia strony
Współautorzy/ CV
Forum
Zgłoś błąd
Szukaj
Suma wag dla tego drzewa wynosi 10
Taniej nie będzie! AGD,
Jest znanych kilka algorytmów tworzące takie drzewo. Wszystkie one wykorzystują tzw.
RTV, Foto, GSM, Car
. Do rozrastającego się drzewa dodawane są "najlepsze" krawędzie, w
metodę "zachłanną"
Audio.
tymprzypadku o najmniejszej wadze.
Opis algorytmu Kruskala
.
Opis algorytmu Prima
Ostatnia aktualizacja ( środa, 10 sierpień 2005 )
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=101&Itemid... 2007-10-06 18:46:28
Algorytmy i struktury danych - Cykl Hamiltona Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Cykl Hamiltona
MENUGA
ÓWNE
Cykl Hamiltona
Start
Napisał Michał Knasiecki
wtorek, 16 sierpień 2005
Algorytmy
Graf posiada cykl Hamiltona,
Kryptografia jeśli istnieje w nimcykl (droga, która zaczyna się i kończy wtymsamymwierzchołku), który
zawiera każdy wierzchołek dokładnie raz. Algorytm znajdujący cykl Hamiltona w grafie jest
Struktury danych
znacznie bardziej skomplikowany, niż w przypadku cyklu . Nie istnieje żaden
Eulera
algorytmrozwiązujący ten problemw czasie wielomianowym, algorytmnależy więc do klasy
Kursalgorytmiki
NP-zupełnych.
Praktyka
Mapaserwisu
Historia strony
Współautorzy/ CV
Przykładowy cykl: 1,2,6,5,3,4,1 lub 1,5,6,2,4,3,1
Forum
Ostatnia aktualizacja ( wtorek, 16 sierpień 2005 )
Zgłoś błąd
Szukaj
Tani Internet MULTIMO -
już za 10 zł netto. Zobacz
www.multimo.pl
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=115&Itemid... 2007-10-06 18:46:47
Algorytmy i struktury danych - Cykl Eulera Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Cykl Eulera
MENUGA
ÓWNE
Cykl Eulera
Start
Napisał Michał Knasiecki
wtorek, 16 sierpień 2005
Algorytmy
Kryptografia
Struktury danych
Kursalgorytmiki
Do powstania cyklu Eulera przyczynił się tzw. problem
mostów królewieckich. Przez Królewiec (dziś Kaliningrad) przepływała rzeka, w rozwidleniu
Praktyka
której znajdowały się 2 wyspy. Na rzece znajdowało się 7 mostów (patrz rys.). Miejscowa
ludność co rok urządzała zabawę, która polegała na próbowaniu przebycia wszysktkich
Mapaserwisu mostów dokładnie raz. Problemem tym zajął się Leonhard Euler, szwajcarski matematyk,
fizyk i astronom. Udowodnił on, że nie jest to możliwe, powodem tego jest nieparzysta
Historia strony
liczba wejść na mosty na wyspach oraz po obu stronach rzeki.
CyklemEulera w grafie nazywamy cykl (drogę, która zaczyna się i kończy w tym samym
Współautorzy/ CV
wierzchołku), który zawiera każdą krawędz
dokładnie raz.
Forum
Zgłoś błąd
Szukaj
Taniej nie będzie! AGD,
RTV, Foto, GSM, Car
Audio.
Graf z cyklemEulera Graf bez cyklu Eulera
A
ańcuchemEulera wgrafie nazywamy drogę, który zawiera każdą krawędz
dokładnie raz.
: po pierwsze graf musi być spójny (musi istnieć droga
Warunek istnienia cyklu Eulera
łącząca każdą parę wierzchołków). Jeżeli graf jest spójny i skierowany to do każdego
wierzchołka musi wchodzić i wychodzić tyle samo krawędzi. Jeżeli graf jest spójny i
nieskierowany to liczba wychodzących krawędzi z każdego wierzchołka musi być parzysta.
Opis algorytmu
Ostatnia aktualizacja ( środa, 05 paz
dziernik 2005 )
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=114&Itemid... 2007-10-06 18:46:58
Algorytmy i struktury danych - Tablice z hashowaniem Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Tablice z hashowaniem
MENUGA
ÓWNE
Tablice z hashowaniem
Start
Napisał Michał Knasiecki
wtorek, 16 sierpień 2005
Algorytmy
Tablice z hashowaniem są
Kryptografia stosowane, gdy z pewnego dużego zbioru danych w danej chwili musimy znać stosunkowo
jego niewielki podzbiór. Elementy z tego podzbioru są zapisywane w tablicy, której indeksy
Struktury danych
dla danego elementu oblicza specjalna funkcja hashująca. Takie rozwiązanie zmniejsza
złożoność pamięciową algorytmy, np. wyobraz
my sobie, że ze zbioru 10.000 liczb
Kursalgorytmiki
całkowitych w danej chwili potrzebujemy jedynie 10. Po zastosowaniu tablicy z
hashowaniem zmniejszamy wymaganą pamięć 1000-krotnie. Ponieważ adres danego
Praktyka
elementu jest obliczany na podstawie jego wartości, funkcja hashująca jest bardzo szybka.
Jednak z tego samego powodu może dojść do konfliktu. Może się bowiem zdarzyć tak, że
Mapaserwisu
funkcja wyznaczy kilku danym tą samą komórkę w pamięci. Jest to niedopuszczalne,
należy więc w takim przypadku do komórki wyznaczonej przez funkcję doczepić statyczną
Historia strony
tablicę o ilości elementów równej ilości przydzielonych komórce elementów. Ponieważ
tablice są statyczne, algorytmnie traci na szybkości, a ponieważ każdy element ma osobne
Współautorzy/ CV
w niej miejsce nie dochodzi do konfliktu.
Forum
Jeśli funkcja hashująca wyznaczy wszystkim elementom tą samą komórkę, elementy te
zostaną zapisane w jednej tablicy. W najgorszym przypadku więc tablica z hashowaniem
Zgłoś błąd
sprowadza się do zwykłej tablicy statycznej (stąd złożoność pesymistyczna przeszukiwania
jest O(n)). Jeśli jednak funkcja hashująca wyznaczy każdemu elementowi inny adres
Szukaj
złożoność przeszukiwania jest stała: O(1), (wynika to z faktu, że wartość szukanego
elementu jest jednoznaczna z jego adresem w pamięci). Jednym z najczęściej
przytaczanych przykładów zastosowania tablicy z hashowaniem są kompilatory. Podczas
Taniej nie będzie! AGD,
analizowania programu muszą one zapamiętywać, czy dana zmienna już wystąpiła, a jeśli
RTV, Foto, GSM, Car
tak, to co znaczy.
Audio.
Podstawą tablic z hashowaniem jest dobra funkcja hashująca. Miarą tej "dobroci" jest
stopień, w jakim spełnia ona zasadę prostego równomiernego hashowania, tzn: losowo
wybrany klucz jest z takim samym prawdopodobieństwem odwzorowywany na każdą z
pozycji. Oznacza to poprosty, by klucze były wmiarę równomiernie rozpraszane w tablicy.
Jedną z najprostszych funkcji hashujących jest funkcja modularna, która dla klucza k
zwraca wartość reszty z dzielenia k przez m (m-długość tablicy), czyli h(k)=k modulo m.
Funkcja hashująca dla hasowania modularnego może wyglądać następująco:
#include
...
int h(int x){
return fmod(x, m);
}
Aby funkcja modularna dawała zadowalające efekty należy dobrać odpowiednią wartość m:
nie powinna być ona potęgądwójki. Dlatego należy wybierać liczby pierwsze dalego
położóne od potęg dwójki, np. dobrą wartością jest m=701.
Ostatnia aktualizacja ( wtorek, 16 sierpień 2005 )
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=113&Itemid... 2007-10-06 18:47:17
Algorytmy i struktury danych - Kopiec (Stóg) Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Kopiec (Stóg)
MENUGA
ÓWNE
Kopiec (Stóg)
Start
Napisał Michał Knasiecki
wtorek, 16 sierpień 2005
Algorytmy
Kopiec inaczej zwany
, które spełnia tzw.warunek
Kryptografia stogiem jest szczególnym przypadkiem drzewa binarnego
kopca tzn. każdy następnik jest niewiększy od swego poprzednika. Z warunku tego wynikają
Struktury danych
szczególne własności kopca:
w korzeniu kopca znajduje się największy element
Kursalgorytmiki
na ścieżkach (połączeniach między węzłami), od korzenia do liścia, elementy są
Praktyka posorotwane nierosnąco
Oto przykładowy kopiec:
Mapaserwisu
Historia strony
Współautorzy/ CV
Forum
Zgłoś błąd
Szukaj
Szczególne własności kopcówzostały wykorzystane do stworzenia algorytmy do sortowania
Taniej nie będzie! AGD,
zwanego HeapSort
RTV, Foto, GSM, Car
Audio.
Ostatnia aktualizacja ( wtorek, 16 sierpień 2005 )
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=111&Itemid... 2007-10-06 18:47:34
Algorytmy i struktury danych - Drzewo Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Drzewo
MENUGA
ÓWNE
Drzewo
Start
Napisał Michał Knasiecki
wtorek, 16 sierpień 2005
Algorytmy
Drzewo jest bardziej
Kryptografia skomplikowaną strukturą niż poprzednie. Dla każdego drzewa wyróżniony jest jeden,
charakterystyczny element- korzeń. Korzeń jest jedynym elementem drzewa, który nie
Struktury danych
posiada elementów poprzednich. Dla każdego innego elementu określony jest dokładnie
jeden element poprzedni. Dla każdego elementu oprócz ostatnich, tzw. liści istnieja co
Kursalgorytmiki
najmniej 2 elementy następne. Jeżeli liczba następnych elementów wynosi dokładnie 2 to
drzewo nazywamy binarnym. Drzewo można zdefiniować, jako acykliczny .
graf
Praktyka
Mapaserwisu
Historia strony
Współautorzy/ CV
Forum
Zgłoś błąd
Szukaj
Dla każdego drzewa można określić:
Mobilny internet szybki jak
długość drogi u (głębokość) - liczba wierzchołków, przez które należy przejść od korzenia
stacjonarny.Przy zakupie
do wierzchołka u
programantywirusowy
wysokość u - maksymalna liczba wierzchołkówna drodze od u do pewnego liścia
Gratis
wysokość drzewa = głębokość = wysokość korzenia +1
ścieżka z u do v - zbiór wierzchołków, przez które należy przejść z wierzchołka u do v
droga - ścieżka skierowana
stopień wierzchołka - liczba jego bezpośrednich następników
stopień drzewa - maksymalny stopień wierzchołka
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=110&Itemid... 2007-10-06 18:48:11
Algorytmy i struktury danych - Lista Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Lista
MENUGA
ÓWNE
Lista
Start
Napisał Michał Knasiecki
wtorek, 16 sierpień 2005
Algorytmy
Lista jest to liniowo
Kryptografia uporządkowany zbiór elementów, z których dowolny element można usunąć oraz dodać w
dowolnym miejscu. Pierwszy i ostatni element listy nazywamy końcami listy. Szczególnym
Struktury danych
przypadkiemlisty może być (gdy pobrać, odczytać i wstawić element można tylko na
stos
końcu listy) lub kolejka (pobrać i odczytać element można tylko na początku listy, a dodać
Kursalgorytmiki
na końcu).
Listy mogą być posortowane (najmniejszy element jest w korzeniu). Rozważmy przypadek
Praktyka
jednokierunkowej listy posortowanej.
Aby dodać element do listy posortowanej należy sprawdzić, w którymmiejscu powienien się
Mapaserwisu
on znajdować. Sprawdzamy od korzenia, schodząc w dół, jeśli element, który chcemy
dodać jest większy od badanego węzła i mniejszy od jego następnika, to należy umieścić go
Historia strony
między nimi. Musimy więc ustawić wskaz
nik aktualnego węzła na dodawany element, a
wskaz
nik tego elementu na następnik. Ponieważ jest to lista jednokierunkowa,
Współautorzy/ CV
przeszukiwanie jej należy zawsze zaczynać od korzenia. Dodając więc pierwszy element do
pustej listy należy zapamiętać jego wskaz
nik, by póz
niej móc się do niego przenieść.
Forum
W przeciwieństwie do stosu i kolejki listy mogą zawierać dwa wskaz
niki. Takie listy
nazywamy dwukierunkowymi, poruszać się możemy w niej w obydwu kierunkach, co
Zgłoś błąd
przyspiesza wszystkie operacje. Oto schemat listy dwukierunkowej:
Szukaj
Mobilny internet szybki jak
stacjonarny.Przy zakupie
programantywirusowy
Gratis
Ostatnia aktualizacja ( wtorek, 16 sierpień 2005 )
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=109&Itemid... 2007-10-06 18:48:22
Algorytmy i struktury danych - Kolejka Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Kolejka
MENUGA
ÓWNE
Kolejka
Start
Napisał Michał Knasiecki
poniedziałek, 01 sierpień 2005
Algorytmy
Kolejka jest strukturą liniowo
Kryptografia uporządkowanych danych w której dołączać nowe dane można jedynie na koniec kolejki a
usuwać z początku. Procedura usunięcia danych z końca kolejki jest taka sama, jak w
Struktury danych
przypadku , z tą różnicą, że usuwamy dane od początku a nie od końca.
stosu
Pierwszy element (a dokładniej wskaz
nik do jego miejsca w pamięci) musi zostać
Kursalgorytmiki
zapamiętany, by możliwe było usuwanie pierwszego elementu w czasie stałym O(1).
Gdybyśmy tego nie zrobili, aby dotrzeć do pierwszego elementu należałoby przejść
Praktyka
wszystkie od elementu aktualnego (czyli ostatniego), co wymaga czasu O(n).
Działanie na kolejce jest intuicyjnie jasne, gdy skojarzymy ją z kolejką ludzi np. w sklepie.
Mapaserwisu
Każdy nowy klient staje na jej końcu, obsługa odbywa się jedynie na początku.
Schemat kolejki wygląda następująco:
Historia strony
Współautorzy/ CV
Forum
Zgłoś błąd
Szukaj
Tani Internet MULTIMO -
już za 10 zł netto. Zobacz
Ostatnia aktualizacja ( wtorek, 16 sierpień 2005 )
www.multimo.pl
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=67&Itemid... 2007-10-06 18:48:33
Algorytmy i struktury danych - Stos Strona 1
sobota, 06 paz
dziernik 2007
szukaj...
Kontakt Reklama FAQ
Strona główna
template designedby peekmambo.com
Start Struktury danych Klasyczne Stos
MENUGA
ÓWNE
Stos
Start
Napisał Michał Knasiecki
piątek, 29 lipiec 2005
Algorytmy
Stos jest strukturą liniowo
Kryptografia uporządkowanych danych, z których jedynie ostatni element, zwany wierzchołkiem, jest w
danym momencie dostępny. W wierzchołku odbywa się dołączanie nowych elementów,
Struktury danych
również jedynie wierzchołek można usunąć.
Stos jest bardzo często wykorzystywaną strukturą danych. Działanie na nim jest częśto
Kursalgorytmiki
porównywane do stosu talerzy: nie można usunąć talerza znajdującego się na dnie stosu
nie usuwając wcześniej wszystkich innych. Nie można także dodać nowego talerza gdzieś
Praktyka
indziej, niż na samą górę.
Przykładowe zastosowanie stosu możesz poznać w algorytmie Inf-2-ONP zmieniający
Mapaserwisu
notację zapisu liczb z infiksowej na Odwrotną Notację Polską.
Oto schamt stosu:
Historia strony
Współautorzy/ CV
Forum
Zgłoś błąd
Szukaj
Szybki dostęp do
Ostatnia aktualizacja ( wtorek, 16 sierpień 2005 )
internetu. Kupjeden z
modemówiPlusa już za 1
zł!
Mambo is Free Software released under the GNU/GPL License.
Mobiletec Mobilne Systemy Informatyczne
http://www.algorytm.org/index.php?option=com_content&task=view&id=41&Itemid... 2007-10-06 18:48:52