Fastbar
Powrót do strony głównej
Trzymaj pliki na gmclan.org!
Game Maker w pytaniach i odpowiedziach!
Polska dokumentacja
Tabela wyników ligi 24
Pobierz GM
Akademia GMCLANu
Kategorie bazy artykułów
Artykuły -> Kąciki programowania -> Algorytmy i struktury danych
Treść artykułu
Wprowadzenie do teorii grafów - cz. 3
autor: Platyna (24.05.09)
Wstęp do teorii grafów - cz. 3

Podstawowe algorytmy grafowe
     Witam w ostatniej części tego artykułu. Opiszę działanie oraz sposoby implementacji dwóch podstawowych algorytmów operujących na grafach. Jest to DFS i BFS. Przyjemnej lektury. ;)

DFS (Przeszukiwanie w głąb)
     DFS to skrót od Depth-first search. Algorytm ten jest wykorzystywany w bardzo wielu problemach. Służy do przeglądania kolejnych wierzchołków grafu w taki sposób, że zaczynając od dowolnego wierzchołka (korzenia) poruszamy się w głąb grafu. Gdy znajdziemy się w wierzchołku, od którego nie możemy już dojść do żadnego nieodwiedzonego wcześniej, cofamy się o jeden poziom wyżej i przeglądamy kolejnych sąsiadów. Rysunek 5 przedstawia przebieg algorytmu zaczynając od wierzchołka 1. Na czerwono oznaczono wierzchołki odwiedzone, a na zielono wierzchołek, w którym aktualnie się znajdujemy. Kolejność odwiedzania poszczególnych sąsiadów nie ma znaczenia.

     Jak łatwo się domyśleć, w przypadku grafów niespójnych algorytm zakończy swoje działanie przed sprawdzeniem wszystkich wierzchołków. Jest to więc dobry sposób na sprawdzenie spójności grafu.

Implementacja
     Najprostszą metodą implementacji DFSa jest zastosowanie rekurencji, czyli wywołania algorytmu wewnątrz samego siebie. Stwórzmy sobie tablicę O, która dla każdego wierzchołka będzie przechowywała wartość 1 jeżeli był on już odwiedzony lub wartość 0 jeżeli nie. Następnie stwórzmy funkcję DFS przyjmującą jeden argument w (numer wierzchołka, od którego zaczynamy przeszukiwanie). Funkcja ta musi aktualnemu wierzchołkowi ustawić wartość w tablicy O na 1 oraz przejrzeć w pętli wszystkich sąsiadów wierzchołka w i wywołać samą siebie dla tych jeszcze nieodwiedzonych.
     Tutaj widzimy jak ważna jest odpowiednia reprezentacja grafu. Gdybyśmy wykorzystali macierz sąsiedztwa musielibyśmy za każdym razem przeglądać WSZYSTKIE wierzchołki i sprawdzać czy są połączone z wierzchołkiem w. Listy sąsiedztwa dają nam szybki dostęp do jego sąsiadów.

Złożoność czasowa i pamięciowa
     Algorytm wymaga od nas zapamiętania dla każdego wierzchołka czy był on odwiedzany czy nie. Nietrudno, więc zauważyć, że zapotrzebowanie na pamięć jest proporcjonalne do liczby wierzchołków grafu.
     Trochę inaczej ma się sprawa złożoności czasowej. Algorytm musi dla każdego wierzchołka grafu sprawdzić wszystkich jego sąsiadów (czy byli już odwiedzani czy nie). Przy reprezentacji grafu za pomocą list sąsiedztwa czas sprawdzania wszystkich sąsiadów będzie, więc proporcjonalny do liczby krawędzi wychodzących z wierzchołka. Widzimy więc, że całkowity czas działania algorytmu będzie proporcjonalny do liczby krawędzi grafu.

BFS (Przeszukiwanie wszerz)
     BFS (Breadth-first search) ma bardzo podobne zastosowania co DFS. Również służy do przejrzenia wszystkich wierzchołków grafu jednak obiera trochę inną strategię. DFS najpierw skupiał się na jednym rozgałęzieniu, po czym przechodził do przetwarzania kolejnych. BFS natomiast najpierw sprawdza wszystkich sąsiadów danego wierzchołka, a następnie sąsiadów tych sąsiadów itd. aż do przetworzenia całego grafu. W przykładzie z Rysunku 5 kolejność odwiedzania wierzchołków przy użyciu DFSa była następująca: 1, 2, 4, 3, 7, 5, 6. Przy zastosowaniu algorytmu BFS wierzchołki będą odwiedzane w takiej kolejności: 1, 2, 3, 4, 7, 6, 5. Dla lepszego zrozumienia przeanalizujmy może jeszcze jeden przykład. Rysunek 6 przedstawia przebieg algorytmu dla pewnego grafu.


Implementacja
     Tak jak w DFS będziemy potrzebowali pewnej tablicy O przechowującej dla każdego wierzchołka odpowiednią wartość zależnie od tego czy był on już odwiedzony. Dodatkowo utwórzmy sobie kolejkę K zawierającą wierzchołki do odwiedzenia. Na początku znajdować się będzie na niej jedynie wierzchołek początkowy w. Następnie dopóki w kolejce znajdują się jeszcze jakieś nieprzetworzone wierzchołki należy je kolejno zdejmować i przeszukiwać ich sąsiadów. Jeżeli znajdziemy takiego sąsiada, którego jeszcze nie wrzucaliśmy do kolejki (odpowiednia wartość tablicy O jest równa 0) należy to uczynić i zmienić wartość w tablicy O. Przeanalizujemy przebieg algorytmu dla przykładu z Rysunku 6. Na początku w kolejce znajduje się jedynie wierzchołek 1. Ściągamy go i wrzucamy do kolejki wierzchołki 7 i 3. Zdejmujemy 7 i wrzucamy 2 i 6. Nasz kolejka wygląda teraz tak: 3, 2, 6. Bierzemy 3 i wrzucamy do kolejki jej sąsiadów, czyli 4 i 5 (w kolejce mamy: 2, 6, 4, 5). Teraz zdejmujemy 2 itd. Podobnie jak w algorytmie DFS, tak i tutaj korzystna jest reprezentacja grafu przy pomocy list sąsiedztwa.

Złożoność czasowa i pamięciowa
     Algorytm BFS oprócz tablicy O wymaga od nas również zapamiętania kolejki nieodwiedzonych dotąd wierzchołków. Złożoność pamięciowa będzie więc istotnie większa niż w algorytmie DFS.
     Podobnie jak DFS, BFS musi dla każdego wierzchołka przejrzeć wszystkich jego sąsiadów. Będzie ich tyle ile krawędzi wychodzących z wierzchołka. Złożoność czasowa algorytmu BFS będzie więc również proporcjonalna do całkowitej liczby krawędzi grafu.
     Widzimy więc, że algorytm ten jest mniej praktyczny niż DFS. Zwykle wiec się go nie używa. Istnieje jednak klika przypadków, w których BFS może się okazać lepszym rozwiązaniem. Wyobraźmy sobie graf, w którym krawędzie układają się w długi ciąg bez żadnych rozgałęzień. W takim przypadku liczba wywołanych w sobie DFSów była by równa liczbie wszystkich wierzchołków. Dla bardzo dużych danych mogłoby to zaowocować brakiem pamięci.

Przykłady zastosowania
-Sprawdzenie spójności grafu
-Wyszukanie najkrótszej drogi od danego wierzchołka do wszystkich pozostałych (pomijając wagi krawędzi)
-Wyznaczenie silnie spójnych składowych grafu skierowanego (jedynie DFS)
-Sortowanie topologiczne (jedynie DFS)

To już jest koniec...
     ...niniejszego artykułu. Był to jedynie zalążek zagadnienia teorii grafów. Istnieje jeszcze wiele algorytmów wykorzystywanych w różnych problemach, czasami nawet takich, które na pozór nie mają nic wspólnego z grafami. Cieszę się, że dobrnąłeś do tego miejsca. Mam nadzieję, że coś z tej lektury wyniosłeś, że udało mi się przybliżyć ci mniej więcej zagadnienie grafów. Polecam teraz poćwiczyć w praktyce implementacje omówionych tutaj algorytmów. Dziękuję, za przeczytanie mych wypocin :)
głosów: 13 | ocena: 7.62 oceń zasób | dodał: Platyna
Komentarze
stron: 1

1


av

Dawidds (16:25, 24.05.2009)

Liczyłem, że pod koniec artykułu podasz praktyczny przykład zastosowania tego...
Tak czy siak, jestem teraz o te parę słów (albo i więcej... ^^) mądrzejszy.

10/10.

av

Makary155 (19:42, 24.05.2009)

Świetne!

stron: 1

1



Dodaj komentarz:
Treść:
Menu
Panel użytkownika
Jesteś niezalogowany!

Nie masz konta? Zarejestruj się
Użytkownicy on-line
2 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 1, ukrytych: 0
Gibki Kaktus
Użytkownicy na czacie discord
Chell (21:14, 11.12.18):
owszem, wykrzacza sie jak jest url bez sciezki po /
Sutikku (20:25, 11.12.18):
tfu, gmclan nie gm
Sutikku (20:25, 11.12.18):
GameMaker ma nową ikonkę teraz jak mam otwartą kartę, czy po prostu nigdy na to nie zwracałem uwagi?
Konrad-GM (16:14, 11.12.18):
ImageMagick?
gnysek (23:14, 10.12.18):
tyle ikonek przerabiać ?
exp (19:10, 10.12.18):
a może dać żółtą obwódkę wokół ikonek
gnysek (17:29, 10.12.18):
poszukam jeszcze jak znaleźć, które aktualny user czytał i wtedy dokończę to, żeby działało jak trzeba
gnysek (17:28, 10.12.18):
ale na forum też przeczytane są szare, a nieprzeczytane kolorowe
Chell (16:37, 10.12.18):
a moze by tak nowosci dac na szaro, a odczytane na kolorowo? teraz tak smutno wyglada
gnysek (14:50, 10.12.18):
Tu masz pobieranie danych: gmclan.org/index.php?plik=227
nowy_user (14:04, 10.12.18):
Hmm., a jak dużo jest z tym roboty? Podejrzewam, że to już raczej wymaga konkretnego skilla... póki co znalazłem coś takiego, wygląda nieźle, korzystał ktoś? : marketplace.yoy...unt-online-data
gnysek (13:49, 10.12.18):
Ja robiłem, za pomocą zapytań normalnych z GMa (http_request albo coś takiego) + PHP na serwerze.
nowy_user (13:32, 10.12.18):
Hej, czy ktoś z was kiedyś robił prosty system logowania i rejestracji w GMie? Tak aby konto zapisywało się na serwerze, i aby admin mógł w razie czego zablokować dostęp.Polecacie jakiś dobry extention ( może być płatny) , żeby nie wynajdować koła od nowa?
exp (23:59, 9.12.18):
teraz spoko wygląda
MaxGaming (23:28, 9.12.18):
To już dużo lepsze! Chociaż nadal wygląda trochę jakby to był bug a nie feature
gnysek (22:33, 9.12.18):
ok, to zostawię wersję pierwszą jaką miałem - zmniejszenie przeźroczystości. Będą lekko jaśniejsze ikonki.
MaxGaming (22:24, 9.12.18):
ale nie wszystko na szaro(bo najczęściej większość tematów jest szara przez mały ruch)
MaxGaming (22:24, 9.12.18):
lepiej już oznaczyć wykrzyknikiem małym te nowe, albo coś
MaxGaming (22:23, 9.12.18):
Według mnie to glupio działa. Nagle wszystko jest szare jakby się zepsuło
gnysek (17:26, 9.12.18):
Od teraz posty napisane przed waszą ostatnią wizytą dostaną szarka ikonkę na stronie głównej - łatwiej znaleźć nowy kontent
MaxGaming (17:22, 9.12.18):
po prostu rób coś, zdobywaj doświadczenie i czytaj na jakiś temat żeby się rozwijać
exp (16:43, 9.12.18):
kurczę chciałbym się znać na czymś tak jak ty na gamedevie
exp (16:42, 9.12.18):
aha, więc to o to chodzi
gnysek (13:51, 9.12.18):
prawdopodobnie po to, żeby Steam VAT odprowadzał w stanach, w których trzeba, w Twoim imieniu.
gnysek (13:51, 9.12.18):
bo teraz 100$ wystarczy, tylko z polskiego punktu widzenia musisz zgłosić firmę do podatku (zerowego), w USA (telefonicznie), żeby dostać ichni NIP.
exp (13:40, 9.12.18):
właśnie też wyczytałem to w regulaminie, no ale coś mi tu nie pasuje. ludzie ciągle wrzucają na steama takie gówienka, że nie wierzę, że oni się tak wysilali
gnysek (13:24, 9.12.18):
musiałbyś założyć firmę, zawrzeć umowę ze steam itd.
Temporal (9:52, 8.12.18):
ambicje zawsze nas gubią
exp (22:52, 7.12.18):
w sensie 99 dolarów
exp (22:50, 7.12.18):
tak z ciekawości, jakbym chciał sprzedawać swoją grę, np. na steamie, to po prostu wystarczy zrobić upgrade do wersji "developer" za cztery stówki?
exp (14:37, 7.12.18):
ale mój poprzedni koncept był całkiem fajny i chyba oryginalny. było to tak jakby połączenie spelunky i contry, choć nie do końca
exp (14:36, 7.12.18):
znów naszła mnie ochota na zrobienie gierki i dobrze wiem, że skończy się tak, że mój prosty pomysł się rozrośnie i nigdy jej nie skończę
MaxGaming (23:53, 6.12.18):
co tam u was mordeczki
MaxGaming (3:01, 5.12.18):
też o tym myślałem, lub po prostu ograniczenie np maks 4 strzał i trzeba wytwarzaćnowe
gnysek (23:04, 4.12.18):
Dzida/oszczep. Można rzucać i ma jakaś tam wytrzymałośc, nie trzeba naboi, w razie czego można wytwarzać nową.
exp (19:16, 4.12.18):
może zastawianie pułapek
MaxGaming (17:45, 4.12.18):
U mnie to działa trochę inaczej. Ciężko ranne zwierze przyśpiesza i albo ucieka albo podejmuje walkę i wtedy szarżuje w naszym kierunku
MaxGaming (17:41, 4.12.18):
np łuk, tylko trzeba to tak zrobić aby taki łuk nadawał się jedynie do absolutnie podstawowych celów
MaxGaming (17:41, 4.12.18):
ze trzeba coś zrobić jako taką broń powszednią która akurat będzie miała sporo naboi i łatwo je będzie zdobyć
MaxGaming (17:40, 4.12.18):
hmm, ciekawy system, ale na razie chodzi mi
gnysek (17:37, 4.12.18):
wtedy można mieć mało naboi i ryzykujesz, albo strzelasz 2/3 razy i zgon od razu, albo czekasz aż padnie
gnysek (17:36, 4.12.18):
duże powinny krwawić, jednym strzałem = czekasz 5 minut na śmierć, albo strzelasz dalej
MaxGaming (17:35, 4.12.18):
a chodzi mi o stworzenie bardzo realnego respectu dla dużych zwierząt, chcę żeby polowanie na coś dużego było dla gracza czymś wyjątkowym i odświętnym, kiedy znajdzie jakąś amunicję do fajniejszej broni
MaxGaming (17:34, 4.12.18):
Co nie jest takie proste, bo strzelanie z łuku 3 razy żeby zabić zająca to na przykłąd pomyłka i byłoby bardzo śmiesznie. Zabicie zająca za jendym strzałem = obrażeniom na tyle dużym że na upartego upolowałoby się i dużo większe zwierzęta
MaxGaming (17:34, 4.12.18):
coś takiego żeby nie dało się z tego za wiele zrobić, ale żeby wystarczyło na polowanie na najprostrze zwierzęta pokorju zająca żeby zdobyć pożywienie
MaxGaming (17:33, 4.12.18):
a same pociski będą na wagę złota. Tylko muszę wymyślić jak w to wszystko wpleść uzbrojenie inne niż broń palna
MaxGaming (17:33, 4.12.18):
broń krótka na prawdę nie za bardzo nadaję się do polowania ze względu na swój bardzo mały zasięg i celność, broń pokroju kar98k dla gracza który według fabuły nie za bardzo miał wcześniej kontakt z militariami nie jest szybka do przeładowania i chociaż ma duży zasięg i potrafi powalać z nóg na prawdę szybko to jednak jeden pochopny strzał i zanim przeładujemy to możemy być już martwi
MaxGaming (17:31, 4.12.18):
ale jednoczęśnie funkcjonalna. Unikam realizmu na siłę który by komplikował rozgrywkę i zmieniał ją w niezrozumiałą, a staram się to nadrobić po prostu realizmem w postaci ograniczeń które nałożone są na nas
MaxGaming (17:30, 4.12.18):
jak wspominałem już moja gra ma być jak najprostrza zarówno dla gracza jak i dla mnie w rozwijaniu
MaxGaming (17:30, 4.12.18):
a w grze otwartego świata wcale być nie miało, dopiero w trakcie tworzenia doszedłem do wniosku że można to łatwo i fajnie zrobić i jednoocześnie uniknąc problemów typu "mam misje fabularną 10tyś pikseli ode mnie"
Ankieta
» Jakie kursy najchętniej widziałbyś na stronie ?
GM Studio
GM Studio 2
Godot
Construct

GMCLAN to serwis o programie Game Maker i nie tylko.
[ Polityka prywatności ]
Copyright © 2002-2018. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus (ranmus.pl), © 2017-2018 {=|=} fable_inside();

[ Czas generowania strony: 0.02013 sekund ] [ Liczba zapytań MySQL: 13 ]