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) | czas czytania: 5 minut, 46 sekund
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
Misiek999
Użytkownicy na czacie discord
gnysek (13:58, 18.02.19):
bo tam są głównie XMLe, wiec kazdy edytor do www się nada
gnysek (13:58, 18.02.19):
ja otwierałem w phpstormie i robiłem replace
nowy_user (13:45, 18.02.19):
BTW. Na forum YoYo coraz większe naciski ze strony użytkowników. Podoba mi się to, że użytkownicy wywierają presję na Yoyo, aby produkt i forum dalej się rozwijały. Nie podoba mi się natomiast to, że Yoyo samo nie wychodzi z inicjatywą :/
nowy_user (13:44, 18.02.19):
Dzięki za info, postaram się jeszcze pokombinować z GMEdit , może tam będzie ta opcja.
gnysek (13:28, 18.02.19):
a faktycznie, nie ma globalnego replace, to w GMS2 tylko, trzeba robić globalny find i ręcznie zmieniać
nowy_user (10:30, 18.02.19):
Niestety, w edit jest opcja Find a resource (Ctrl+R) ale to pozwala wyszukiwać np. całe obiekty sprity itd. Nie do końca mi o to chodziło. To, co ja bym chciał zrobić to np. podmienić nazwę jednej zmiennej, która jest dość nieintuicyjna, a pojawia się bardzo często, i jest porozsiewana po różnych obiektach i skryptach. Chciałbym móc podmienić nazwę tej zmiennej we wszystkich miejscach, za jednym zamachem...
gnysek (10:05, 18.02.19):
wejdź do menu "Edit" i tam chyba będzie, wraz ze skrótem.
nowy_user (9:24, 18.02.19):
Panowie, prosta sprawa, nie wiem czy czegoś nie widzę przez jakieś chwilowe zaćmienie umysłu, ale gdzie w GM1.4 jest opcja globalna 'search and replace' ? Lokalnie, dla danego obiektu pojawia sie po wciśnięciu ctrl+F , natomiast globalnie, jak wcisnę ctrl+shit+F to pojawia się sama wyszukiwarka, bez opcji replace... Chciałem zmienić nazwę jednej zmiennej, chyba nie będę musiał tego robić ręcznie?
Konrad-GM (0:12, 18.02.19):
Yup, dokładnie tak powinno chodzić, potem jest trochę więcej różnorodnych pułapek, więc robi się coraz trudniejsze
I am Lord (0:06, 18.02.19):
ale aż tak? www.youtube.com...eature=youtu.be
Konrad-GM (23:58, 17.02.19):
Ten kurczak szybko chodzi, więc to ficzer jest, żeby za łatwo nie dało się przejść gry
I am Lord (23:52, 17.02.19):
ok teraz 8, ale nie wiem czy u mnie czasem nie za szybko chodzi ten kurczak
I am Lord (23:50, 17.02.19):
5 jajaec zdobyłem
I am Lord (23:46, 17.02.19):
12 minut zostało a nie mam game playu jeszcze tylko sama grafika
I am Lord (23:46, 17.02.19):
ja nie zdąrze
Konrad-GM (23:41, 17.02.19):
Dodałem grę na ligę, ale zczaiłem się dopiero teraz, że czarny kolor to przecież też kolor kek, nie bijcie
gnysek (10:35, 15.02.19):
jak jeszcze gdzieś zostały, dawajcie znać
I am Lord (17:40, 14.02.19):
to się nie sprawdzi przy takiej małej ilości osób. Żadne posty się nie gubią tutaj w tłumie żeby je wyróżniać
I am Lord (17:40, 14.02.19):
wyłącz te oceny
gnysek (10:29, 14.02.19):
jeszcze wieczorem zajrzę w kod, jak nie znajdę żadnej opcji to wyłączę ocenianie w tych działach i tyle, i tak mało kto tego potrzebuje, to nie stackoverflow
gnysek (0:46, 14.02.19):
musiałbym chyba wyłączyć oceny
nowy_user (20:43, 13.02.19):
To prawda, jest to irytujące.
I am Lord (20:11, 13.02.19):
da się wymusić żeby to cholerne sortowanie po ocenie postu nie było domyślne? Straszliwie mnie wnerwia
gnysek (11:50, 13.02.19):
tzn. wcześniej też na forach się sporo działo, ale nie miałem internetu to nie widziałem
gnysek (11:49, 13.02.19):
Pamiętam, lata 2003-2008 to chyba takie najbujniejsze. Aż weszły facebooki i smartfony.
Temporal (17:18, 12.02.19):
jestem człowiekiem starej daty i żyje czasami, gdy wszystko działo się na forach internetowych
Temporal (17:17, 12.02.19):
wiem co to Discord, tak tylko głupoty wypisuje
I am Lord (17:12, 12.02.19):
discord to chat a nie portal społecznościowy
I am Lord (17:05, 12.02.19):
bo rozmowy się toczą na discordzie tylko
Temporal (16:51, 12.02.19):
boję się Discordów, Facebooków i Instagramów
SimianVirus7 (22:59, 11.02.19):
tu zwykle jest cicho z tego co wiem na discordzie więcej się dzieje
nowy_user (15:37, 11.02.19):
Wszyscy piszą gry, nik nie ma czasu na pogawędki
Temporal (15:33, 11.02.19):
co tu tak cicho?
nowy_user (17:20, 9.02.19):
Morał z tych historii: Róbcie backupy
Temporal (15:39, 9.02.19):
brzmi jak dobra copypasta
Konrad-GM (14:59, 9.02.19):
Kiedyś robiłem grę w Unity, crash co chwila, a potem ostatni crash usunął mi sporą część assetów w jakiś dziwny sposób, że nie mogłem odzyskać większości kodu czy modeli a kopia mocno była nieaktualna, usunąłem Unity i od tamtej pory nigdy nie wróciłem xD
I am Lord (13:52, 9.02.19):
miałem strzelankę topdown z generowanymi jaskiniami w planach
I am Lord (13:51, 9.02.19):
Ja nie oddałem na ligę bo mi crash GMS2 zepsuł projekt i się wkurzylem. Odinstalowałem go
Temporal (10:13, 9.02.19):
kiedy ten GM mi się znudzi? cały czas jestem pod wrażeniem jak dobry jest ten soft. Oczywiście ma jakieś swoje bolączki i są bardziej zaawansowane silniki, ale to wciąż doskonałe narzędzie zarówno dla początkujących twórców gier jak i zaawansowanych. Tworzenie gier w tym środowisku to sama przyjemność
gnysek (22:03, 8.02.19):
Nie wyjdzie. Jest plan na cały rok rozpisany i nie ma tam gms3. A zniżki były co roku.
nowy_user (18:22, 8.02.19):
Pojawiła się nowa promocja, Lunar Sale, nawet do 50% zniżki na GMS2 Mobile. Chyba niedługo wyjdzie GMS3, skoro co chwila nas zasypują promocjami
nowy_user (22:05, 5.02.19):
Dzięki, wyglada bardzo solidnie, chyba z niego skorzystam
gnysek (17:03, 5.02.19):
mydevil.net po tym jak hekko ceny podniosło
nowy_user (14:40, 5.02.19):
Hej, jaki niedrogi i dobry hosting polecacie do prostego landing Page’a, na którym mógłbym zaprezentować apkę zrobioną w GM? Najlepiej taki, który obsługuje WordPressa, bo bardzo do gustu przypadła mi wtyczka Elementor Page Builder
Sutikku (22:58, 4.02.19):
dziury w głowie
Sutikku (22:58, 4.02.19):
zapomniałem skończyć gierkę na lige .-.
SimianVirus7 (17:35, 4.02.19):
Myślę, że parę dobrych duszyczek by się znalazło i ufundowało nagrody. Jeśli pomysł się spodoba, ja również mogę dorzucić coś od siebie
SimianVirus7 (17:33, 4.02.19):
Można by zrobić jakiś worek gier (ale nie śmieciowych). Human: fall flat, Hollow Knight, Bioshock Inifite, Gothic Universe Edition. To wszystko dobre gry za małą cenę <20zł
Dester (17:13, 4.02.19):
nagrody na Steam na pewno były by bardzo motywujące
Dester (16:53, 4.02.19):
temat był za trudny
Ankieta
» Ile powinny trwać tury Ligi 24?
24h
48h
54h (piątek od 18:00)
7 dni
inna długość (podałem w komentarzu ankiety)

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

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