Strona 1

Algorytmy i struktury danych - Grafy i ich reprezentacje

2007-10-06 18:44:33

http://www.algorytm.org/index.php?option=com_content&task=view&id=44&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Grafy i ich reprezentacje

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Tani Internet MULTIMO -
ju

ż za 10 zł netto. Zobacz

www.multimo.pl

Grafy i ich reprezentacje

Struktury danych

-

Klasyczne

Napisa

ł Michał Knasiecki

czwartek, 28 lipiec 2005

Na pocz

ątek kilka definicji:

W

informatyce

grafem

nazywamy

struktur

ę G=(V, E) składającą się z węzłów

(wierzcho

łków, oznaczanych przez V) wzajemnie połącznonych za pomocą krawędzi

(oznacznych przez E).
Grafy dzielimy na grafy skierowane i nieskierowane:

Rys.1. Graf nieskierowany

Rys.2. Graf skierowany

Je

śli krawędź łączy dwa wierzchołki to jest z nimi incydentna.

P

ętla własna to krawędź łączące wierzchołek z samym sobą.

Stopie

ń wierzchołka w grafie nieskierowanym to liczba incydentnych z nim krawędzi.

Istnieje kilka algorytmów do 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ą

zerami- je

śli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki

s

ą połączone. Oto macierz sąsiedztwa dla grafu z rysunku 1:

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(V

2

)

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ów połączonych krawędzią z v. Lista dla grafu z rysunku 1 wygląda następująco:

1: 2, 3, 5
2: 1, 3, 4
3: 1, 2, 4
4: 2, 3, 5
5: 4, 1

Strona 2

Algorytmy i struktury danych - Grafy i ich reprezentacje

2007-10-06 18:44:33

http://www.algorytm.org/index.php?option=com_content&task=view&id=44&Itemid...

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ędź

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ędź 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

2 - 4

0

-1

0

1

0

2 - 5

0

-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 w kolumnach j-te wierzchołki. Liczby, które mogą znaleźć
si

ę na skrzyżowaniu wierzchołka i oraz j można podzielić na 3 grupy:

od 1 do V - istnieje kraw

ędź skierowana: i <- j

od V+1 do 2*V - istnieje kraw

ędź 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

ędź łącząca wierzchołki i oraz j, ale zawiera też adres następnego

wierzcho

łka, który jest w takiej 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.

Strona 3

Algorytmy i struktury danych - Grafy i ich reprezentacje

2007-10-06 18:44:33

http://www.algorytm.org/index.php?option=com_content&task=view&id=44&Itemid...

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

We

źmy pierwszą krawędź: 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ów w grafie: 2+5=7. Taką liczbę zapisujemy w komórce [1,2].

Przejd

ź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ędź na naszej liście). W komórce [1,3] musimy więc podać

adres wierzcho

łka 5. Ponieważ jest to poprzednik, więc adresem wierzchołka 5 jest 5.

Przechodzimy do ostatniej kraw

ędzi: wierzchołek 5 jest poprzednikiem wierzchołka,

poniewa

ż jest jego ostatnim poprzednikiem (pierwszym był wierzchołek 3) w komórce [1,5]

podajemy adres wierzcho

łka 5, czyli znów wpisujemy 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órym nie łą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 wierszem nr. 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

1

3

-4

7

5

-4

5

2

2

1

3

-2

3

10

10

4

3

4

7

7

-5

4

-5

1

4

2

-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 dodatkowym kolumnom i wierszom zyskujemy listy następników i poprzedników:

w kolumnie 0: wska

źnik do pierwszego elementu na liście poprzedników

w wierszu 0: wska

źnik do ostatniego elementu na liście poprzedników

w kolumnie V+1: wska

źnik do pierwszego elementu na liście następników

w wierszu V+1: wska

źnik do ostatniego elementu na liście następników

na g

łównej przekątnej: wskaźnik do pierwszego elementu na liście elementów nie

b

ędących ani następnikami ani poprzednikami

Strona 4

Algorytmy i struktury danych - Grafy i ich reprezentacje

2007-10-06 18:44:33

http://www.algorytm.org/index.php?option=com_content&task=view&id=44&Itemid...

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

Strona 1

Algorytmy i struktury danych - Grafy i ciąg dalszy

2007-10-06 18:45:12

http://www.algorytm.org/index.php?option=com_content&task=view&id=43&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Grafy i ci

ąg dalszy

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Taniej nie b

ędzie! AGD,

RTV, Foto, GSM, Car
Audio.

Grafy i ci

ąg dalszy

Struktury danych

-

Klasyczne

Napisa

ł Michał Knasiecki

czwartek, 28 lipiec 2005

Oto dodatkowe informacje na
temat grafów, potrzebne w bardziej skomplikowanych algorytmach.
Kilka definicji:
Stopie

ń wierzchołka - to liczba krawędzi do niego przyległych

Graf regularny - to graf, w którym każdy wierzchołek ma taki sam stopień
Graf planarny - to graf, który można przedstawić na płaszczyź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ć
wi

ększy niż f

Graf prosty - to graf bez pętli własnych i krawędzi równoległych
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)

Liczba chromatyczna grafu - to najmniejsza liczba kolorów potrzebnych do pokolorowania
wierzcho

łków grafu tak, by żadne dwa przyległe wierzchołki nie były tego samego koloru

Przyk

ładu do powyższych definicji:

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 przejd

źmy do bardzo ważnego problemu: generowania grafów losowych.

Istnieje kilka modeli grafów losowych, omówimy najwa

żnejszep

Strona 2

Algorytmy i struktury danych - Grafy i ciąg dalszy

2007-10-06 18:45:12

http://www.algorytm.org/index.php?option=com_content&task=view&id=43&Itemid...

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ędź 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ów stosuje 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ów izomorficznych

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ń).

Kryterium izomorfizmu 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ów dla 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

Strona 1

Algorytmy i struktury danych - Drzewa BSP

2007-10-06 18:46:15

http://www.algorytm.org/index.php?option=com_content&task=view&id=42&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Drzewa BSP

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Taniej nie b

ędzie! AGD,

RTV, Foto, GSM, Car
Audio.

Drzewa BSP

Struktury danych

-

Klasyczne

Napisa

ł Tomasz Nędza

czwartek, 28 lipiec 2005

Ciekawym rodzajem drzewa
jest drzewo BSP. Jest to rozwini

ęcie pomysłu wykorzystanego w drzewie BST - całość

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

w

śród grupy wielokątów 3D oglądanych z dowolnego punktu na scenie. Za każdym razem,

gdy zmienia si

ę położenie obserwatora, wykonywany jest liniowy algorytm wyświetlania.

Łatwo zauważyć po złożoności poszczególnych części algorytmu, że metoda ta dobrze
nadaje si

ę do zastosowań, w których zmienia się punkt obserwacji, natomiast same obiekty

pozostaj

ą niezmienne. Pierwsza część algorytmu polega na zbudowaniu drzewa binarnego

ścian składających się na scenę. W korzeniu tego drzewa umieszczany jest dowolny
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

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

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

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

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

BSP ko

ńczy się, gdy każdy węzeł zawiera tylko jeden wielokąt. Myślę, że najłatwiej będzie

to zrozumie

ć na przykładzie. Przypuśćmy, że dany mamy następujący zestaw ścian (rzut z

góry):

Strza

łki przy ścianach oznaczają ich normalne, czyli

kierunek, z którego p

łaszczyzna może być oglądana.

Ł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. W sumie 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 "wskaź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

ę

Strona 2

Algorytmy i struktury danych - Drzewa BSP

2007-10-06 18:46:15

http://www.algorytm.org/index.php?option=com_content&task=view&id=42&Itemid...

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ę w lewym poddrzewie węzła 1. To samo robię ze ścianą nr 2. Schemat

otrzymanego drzewa znajduje si

ę po lewej.

Do zbadania pozosta

ły nam jeszcze ś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 prawym potomkiem. 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 w drzewie 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 w poddrzewo po stronie lewej.

Znale

źliśmy się w węźle, który posiada jedynie jednego potomka, więc przechodzimy

tam bez

żadnych testów. W węźle ze ścianą nr 11 powtarzamy tą czynność.

Znajdujemy si

ę w węźle ze ścianą nr 9. Oba jej wskaź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ów napotykamy na test. Tym razem 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 w gó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.

Strona 3

Algorytmy i struktury danych - Drzewa BSP

2007-10-06 18:46:15

http://www.algorytm.org/index.php?option=com_content&task=view&id=42&Itemid...

Po ca

łym przejściu drzewa otrzymaliśmy następującą kolejność ścian: 9, 11, 4, 7, 10, 8,

6, 12, 5, 2, 3, 1

W celu 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

Strona 1

Algorytmy i struktury danych - Minimalne drzewo rozpinające

2007-10-06 18:46:28

http://www.algorytm.org/index.php?option=com_content&task=view&id=101&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Minimalne drzewo

rozpinaj

ące

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Taniej nie b

ędzie! AGD,

RTV, Foto, GSM, Car
Audio.

Minimalne drzewo rozpinaj

ące

Napisa

ł Michał Knasiecki

środa, 10 sierpień 2005

Niech

b

ędzie dany spójny

graf

nieskierowany o wierzcho

łkach V i krawędziach E. Ponad to 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:

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

Ostatnia aktualizacja (

środa, 10 sierpień 2005 )

Mambo

is Free Software released under the GNU/GPL License.

Mobiletec Mobilne Systemy Informatyczne

Strona 1

Algorytmy i struktury danych - Cykl Hamiltona

2007-10-06 18:46:47

http://www.algorytm.org/index.php?option=com_content&task=view&id=115&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Cykl Hamiltona

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Tani Internet MULTIMO -
ju

ż za 10 zł netto. Zobacz

www.multimo.pl

Cykl Hamiltona

Napisa

ł Michał Knasiecki

wtorek, 16 sierpie

ń 2005

Graf posiada cykl Hamiltona,
je

śli istnieje w nim cykl (droga, która zaczyna się i kończy w tym samym wierzchołku), który

zawiera ka

żdy wierzchołek dokładnie raz. Algorytm znajdujący cykl Hamiltona w grafie jest

znacznie bardziej skomplikowany, ni

ż w przypadku cyklu

Eulera

. Nie istnieje

żaden

algorytm rozwi

ązujący ten problem w czasie wielomianowym, algorytm należy więc do klasy

NP-zupe

łnych.

Przyk

ładowy cykl: 1,2,6,5,3,4,1 lub 1,5,6,2,4,3,1

Ostatnia aktualizacja ( wtorek, 16 sierpie

ń 2005 )

Mambo

is Free Software released under the GNU/GPL License.

Mobiletec Mobilne Systemy Informatyczne

Strona 1

Algorytmy i struktury danych - Cykl Eulera

2007-10-06 18:46:58

http://www.algorytm.org/index.php?option=com_content&task=view&id=114&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Cykl Eulera

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Taniej nie b

ędzie! AGD,

RTV, Foto, GSM, Car
Audio.

Cykl Eulera

Napisa

ł Michał Knasiecki

wtorek, 16 sierpie

ń 2005

Do powstania cyklu Eulera przyczyni

ł się tzw. problem

mostów królewieckich. Przez Królewiec (dziś Kaliningrad) przepływała rzeka, w rozwidleniu
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

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

liczba wej

ść na mosty na wyspach oraz po obu stronach rzeki.

Cyklem Eulera w grafie nazywamy cykl (drogę, która zaczyna się i kończy w tym samym
wierzcho

łku), który zawiera każdą krawędź dokładnie raz.

Graf z cyklem Eulera

Graf bez cyklu Eulera

Łańcuchem Eulera w grafie nazywamy drogę, który zawiera każdą krawędź dokładnie raz.
Warunek istnienia cyklu Eulera: po pierwsze graf musi być spójny (musi istnieć droga
łą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 październik 2005 )

Mambo

is Free Software released under the GNU/GPL License.

Mobiletec Mobilne Systemy Informatyczne

Strona 1

Algorytmy i struktury danych - Tablice z hashowaniem

2007-10-06 18:47:17

http://www.algorytm.org/index.php?option=com_content&task=view&id=113&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Tablice z hashowaniem

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Taniej nie b

ędzie! AGD,

RTV, Foto, GSM, Car
Audio.

Tablice z hashowaniem

Napisa

ł Michał Knasiecki

wtorek, 16 sierpie

ń 2005

Tablice z hashowaniem s

ą

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

dla danego elementu oblicza specjalna funkcja hashuj

ąca. Takie rozwiązanie zmniejsza

z

łożoność pamięciową algorytmy, np. wyobraźmy sobie, że ze zbioru 10.000 liczb

ca

łkowitych w danej chwili potrzebujemy jedynie 10. Po zastosowaniu tablicy z

hashowaniem zmniejszamy wymagan

ą pamięć 1000-krotnie. Ponieważ adres danego

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

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ą

tablic

ę o ilości elementów równej ilości przydzielonych komórce elementów. Ponieważ

tablice s

ą statyczne, algorytm nie traci na szybkości, a ponieważ każdy element ma osobne

w niej miejsce nie dochodzi do konfliktu.

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

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

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

analizowania programu musz

ą one zapamiętywać, czy dana zmienna już wystąpiła, a jeśli

tak, to co znaczy.
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 w miarę 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 <math.h>

...

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

Strona 1

Algorytmy i struktury danych - Kopiec (Stóg)

2007-10-06 18:47:34

http://www.algorytm.org/index.php?option=com_content&task=view&id=111&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Kopiec (Stóg)

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Taniej nie b

ędzie! AGD,

RTV, Foto, GSM, Car
Audio.

Kopiec (Stóg)

Napisa

ł Michał Knasiecki

wtorek, 16 sierpie

ń 2005

Kopiec

inaczej

zwany

stogiem jest szczególnym przypadkiem

drzewa binarnego

, które spe

łnia tzw.warunek

kopca tzn. każdy następnik jest niewiększy od swego poprzednika. Z warunku tego wynikają
szczególne w

łasności kopca:

w

korzeniu

kopca znajduje si

ę największy element

na

ścieżkach (połączeniach między węzłami), od korzenia do liścia, elementy są

posorotwane nierosn

ąco

Oto przyk

ładowy kopiec:

Szczególne w

łasności kopców zostały wykorzystane do stworzenia algorytmy do sortowania

zwanego

HeapSort

Ostatnia aktualizacja ( wtorek, 16 sierpie

ń 2005 )

Mambo

is Free Software released under the GNU/GPL License.

Mobiletec Mobilne Systemy Informatyczne

Strona 1

Algorytmy i struktury danych - Drzewo

2007-10-06 18:48:11

http://www.algorytm.org/index.php?option=com_content&task=view&id=110&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Drzewo

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Mobilny internet szybki jak
stacjonarny.Przy zakupie
program antywirusowy
Gratis

Drzewo

Napisa

ł Michał Knasiecki

wtorek, 16 sierpie

ń 2005

Drzewo

jest

bardziej

skomplikowan

ą strukturą niż poprzednie. Dla każdego drzewa wyróżniony jest jeden,

charakterystyczny element- korze

ń. Korzeń jest jedynym elementem drzewa, który nie

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

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

.

Dla ka

żdego drzewa można określić:

d

ługość drogi u (głębokość) - liczba wierzchołków, przez które należy przejść od korzenia

do wierzcho

łka u

wysoko

ść u - maksymalna liczba wierzchołków na drodze od u do pewnego liścia

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

Strona 1

Algorytmy i struktury danych - Lista

2007-10-06 18:48:22

http://www.algorytm.org/index.php?option=com_content&task=view&id=109&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Lista

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Mobilny internet szybki jak
stacjonarny.Przy zakupie
program antywirusowy
Gratis

Lista

Napisa

ł Michał Knasiecki

wtorek, 16 sierpie

ń 2005

Lista

jest

to

liniowo

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

przypadkiem listy mo

że być

stos

(gdy pobra

ć, odczytać i wstawić element można tylko na

ko

ńcu listy) lub

kolejka

(pobra

ć i odczytać element można tylko na początku listy, a dodać

na ko

ńcu).

Listy mog

ą być posortowane (najmniejszy element jest w korzeniu). Rozważmy przypadek

jednokierunkowej listy posortowanej.
Aby doda

ć element do listy posortowanej należy sprawdzić, w którym miejscu powienien się

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

mi

ędzy nimi. Musimy więc ustawić wskaźnik aktualnego węzła na dodawany element, a

wska

źnik tego elementu

na

nast

ępnik.

Poniewa

ż jest

to

lista

jednokierunkowa,

przeszukiwanie jej nale

ży zawsze zaczynać od korzenia. Dodając więc pierwszy element do

pustej listy nale

ży zapamiętać jego wskaźnik, by później móc się do niego przenieść.

W przeciwie

ństwie do stosu i kolejki listy mogą zawierać dwa wskaźniki. Takie listy

nazywamy dwukierunkowymi, poruszać się możemy w niej w obydwu kierunkach, co
przyspiesza wszystkie operacje. Oto schemat listy dwukierunkowej:

Ostatnia aktualizacja ( wtorek, 16 sierpie

ń 2005 )

Mambo

is Free Software released under the GNU/GPL License.

Mobiletec Mobilne Systemy Informatyczne

Strona 1

Algorytmy i struktury danych - Kolejka

2007-10-06 18:48:33

http://www.algorytm.org/index.php?option=com_content&task=view&id=67&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Kolejka

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Tani Internet MULTIMO -
ju

ż za 10 zł netto. Zobacz

www.multimo.pl

Kolejka

Napisa

ł Michał Knasiecki

poniedzia

łek, 01 sierpień 2005

Kolejka jest struktur

ą liniowo

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

przypadku

stosu

, z t

ą różnicą, że usuwamy dane od początku a nie od końca.

Pierwszy element (a dok

ładniej wskaźnik do jego miejsca w pamięci) musi zostać

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ść

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.

Ka

żdy nowy klient staje na jej końcu, obsługa odbywa się jedynie na początku.

Schemat kolejki wygl

ąda następująco:

Ostatnia aktualizacja ( wtorek, 16 sierpie

ń 2005 )

Mambo

is Free Software released under the GNU/GPL License.

Mobiletec Mobilne Systemy Informatyczne

Strona 1

Algorytmy i struktury danych - Stos

2007-10-06 18:48:52

http://www.algorytm.org/index.php?option=com_content&task=view&id=41&Itemid...

FAQ

Reklama

Kontakt

Strona g

łówna

sobota, 06 pa

ździernik 2007

szukaj...

Start

Struktury danych

Klasyczne

Stos

template designed by

peekmambo.com

MENU G

ŁÓWNE

Start

Algorytmy

Kryptografia

Struktury danych

Kurs algorytmiki

Praktyka

Mapa serwisu

Historia strony

Wspó

łautorzy / CV

Forum

Zg

łoś błąd

Szukaj

Szybki dost

ęp do

internetu. Kup jeden z
modemów iPlusa ju

ż za 1

z

ł!

Stos

Napisa

ł Michał Knasiecki

pi

ątek, 29 lipiec 2005

Stos jest

struktur

ą liniowo

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,

równie

ż jedynie wierzchołek można usunąć.

Stos jest bardzo cz

ęsto wykorzystywaną strukturą danych. Działanie na nim jest częśto

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ś

indziej, ni

ż na samą górę.

Przyk

ładowe zastosowanie stosu możesz poznać w algorytmie

Inf-2-ONP

zmieniaj

ący

notacj

ę zapisu liczb z infiksowej na Odwrotną Notację Polską.

Oto schamt stosu:

Ostatnia aktualizacja ( wtorek, 16 sierpie

ń 2005 )

Mambo

is Free Software released under the GNU/GPL License.

Mobiletec Mobilne Systemy Informatyczne