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: 12 | ocena: 8.17 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
1 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 0, ukrytych: 0
Użytkownicy na czacie discord
I am Lord (22:51, 24.11.17):
Byłem kucem ale teraz jestem skrytym kucem
Wojo (22:38, 24.11.17):
Jak coś to nie do ciebie Huder
Wojo (22:37, 24.11.17):
Od kiedy polityka znów pojawiła się na gmclanie? Myślałem, że zbuntowane polityczne kuce już wyginęły P
I am Lord (22:07, 24.11.17):
Wyczuwam z tego doskonałe memy z "deal with it" www.pudelek.pl/...tlas_kotow_foto
hgter (1:05, 24.11.17):
Już sobie na wszelki wypadek przeniosłem jedną do steama taką razem z androidem. Ale wiele modułów, których licencje mam na mailu nie ma klucza steamowego. No nic pewnie przy formacie po prostu wezmę licencję yoyo z maila. Chyba, że to wyłączą. Ale nie spodziewam się. Nikt by im po czymś takim z 2.0 nie zaufał.
Ignatus (11:32, 23.11.17):
Chyba jedyna opcja przy formacie kompa to wersja steam?
gnysek (11:07, 23.11.17):
O kurde, zlikwidowali to... no to nie wiem, pewnie przyznaje każdą którą znajdzie
gnysek (11:03, 23.11.17):
licencje wybierasz chyba na stronie YYG
hgter (23:35, 22.11.17):
gnysek: Ok, dzięki. Tylko to ma zastosowanie też do 1.4? Bo ja mam kilka licencji z różnymi podpiętymi modułami. Ciekawe jak wybiera odpowiednią. No nic w razie czego mam spis na maila. Dopóki nie wyłączą serwerów powinno być ok.
PsichiX (21:53, 22.11.17):
imprezy firmowe w srode to nie jest trzezwy pomysl xD
gnysek (9:50, 22.11.17):
a jak coś dokupisz, to musisz raz jeszcze wpisać login i hasło w menu help > upgrade i zrobić restart
gnysek (9:50, 22.11.17):
teraz chyba tylko mejla podajesz i hasło, nie ma kodów
hgter (16:47, 21.11.17):
W PRODUCTS da się przełączyć na 1.4, alr tam jest spis wszystkiego co kupiłem, ale bez kodów. Jak się dobrać do kodów? Kiedyś było chyba coś takiego jako Recovery i na maila słali, ale tego też nie mogę znaleźć.
hgter (16:36, 21.11.17):
Chciałem sprawdzić jak to było z tym linuxe i zalogowałem się na moje konto w yoyo. Gdzie teraz są tam numery licencji? Bo szukam i szukam i nigdzie nie ma podsumowania ze spisem posiadanych modułów wraz z kodami. Kiedyś była ładna tabelka.
TO_mek (14:20, 21.11.17):
GMS 1.4 ma eksport do linuxa?
gnysek (12:38, 21.11.17):
W sumie powinienem napisać że słaba.
gnysek (10:51, 21.11.17):
Pełną + moduł. Dlatego napisałem, że oferta średnia.
hgter (0:56, 21.11.17):
Odnosząc się do ogłoszenie gnyska o subscypcji za $39: Tylko jak w tej wersji w "subskrypcji" można rozwiązać moduł na androida? Da się coś taniej? Muszę kupić moduł za 1450 zł? Czy też w tej wersji nie da się z niego skorzystać i muszę kupić pełną+moduł czyli dać 1800 zł?
PsichiX (17:42, 20.11.17):
mieli DLC pod tytulem "kompilacja do kodu natywnego", a biedaki cebulaki meczyc sie z powolnym gmlem xD
Wojo (16:09, 20.11.17):
może jeszcze dlc przyspieszające ładowanie gier?
Wojo (16:08, 20.11.17):
hahaha ten news o nowym gmie pokazuje jak jego poziom upadł na ryj
gnysek (9:37, 20.11.17):
Po prostu każdy sterownik inaczej interpretuje polecenia rysowania linii z directx i ogólnie nikt tego już nie używa w profesjonalnych grach.
gnysek (9:36, 20.11.17):
To nie wina gma tylko kart graficznych. I chyba nawet w dokumentacji jest to opisane czemu tak działa i że własnie lepiej rysować sprite.
hgter (21:40, 19.11.17):
Miałem napisać długi post o skopaniu draw_line w Gm. Ale to nie ma sensu (cyrki jakie w tym wychodzą są nieziemskie). Draw_line nie działa w Gm (działało nawet kurde qbasicu pod dosem) a już pod androidem to co się wyprawia to jakaś paranoja. Jak musisz mieć linię w swoim projekcie to narysuj ją sobie jako sprite.
Adriann (19:29, 19.11.17):
Hi hi
Saus (14:15, 18.11.17):
Siema śmieszki
hgter (10:42, 17.11.17):
Pozmieniałem wszystko na pliki i mam nadzieję, że będzie ok
hgter (10:41, 17.11.17):
Coś chyba nie jest do końca tak z dodawaniem grafik do postów. Wczoraj w nocy dodawałem screeny z gry przez linkowanie (zmieniałem ich wielkość przy pomocy narzędzi edycji w poście). Było wszystko ok, ale teraz jak zajrzałem to screeny wyparowały i tylko linki zostały. Natomiast jeden screen dodany jako plik był ok.
I am Lord (20:02, 16.11.17):
scroll byłby pokrętłem, może to wyglądać spoko
I am Lord (20:01, 16.11.17):
A zobacz w sumie bo nie sprawdzałem w jaki sposób są zrobione scrolle od myszek, tam też na pewno jest enkoder
I am Lord (20:01, 16.11.17):
ale no enkoder jednak fajniejsza sprawa bo nie ma ograniczenia obrotu
I am Lord (20:00, 16.11.17):
A na potencjometrach nie możesz?
Chell (19:13, 16.11.17):
knuje jakiś sprytny zegarek na rpi zero i tak mi zaswitalo ze takie pokrętło byłoby wygodnym inputem
I am Lord (19:08, 16.11.17):
A co konstruujesz?
I am Lord (19:08, 16.11.17):
A jak byś potrzebował liniowe enkodery to takie są np w drukarkach i skanerach
Chell (19:03, 16.11.17):
zawsze coś
I am Lord (18:59, 16.11.17):
w dodatku inkrementalne są tak jak chcesz ale wiesz jaka ich precyzja była
Chell (18:59, 16.11.17):
oo, super myśl, dzięki
I am Lord (18:58, 16.11.17):
skołuj sobie myszkę kulkową, tam są 2 takie enkodery obrotowe.
Chell (18:57, 16.11.17):
coś takiego ze starych komórek kojarzę, że jak normalny rotary encoder jest pionowy i nie da się go obracac jednym palcem tak mi chodzi o taki który jest płaski, wystaje z obudowy urządzenia tylko trochę z boku i można podkręcić
I am Lord (18:57, 16.11.17):
tzn budowa może być z tarczą wewnątrz enkodera a może być tak jak w starych kulkowych myszkach gdzie była tarcza na zewnątrz enkodera
Chell (18:55, 16.11.17):
jednak nie rysuje, lapek padl
I am Lord (18:54, 16.11.17):
no nie czaję o co ci chodzi z zatapianiem
Chell (18:54, 16.11.17):
już rysuje o co mi chodzi
I am Lord (18:53, 16.11.17):
ale to nadal liniowy tylko że się zwija
I am Lord (18:52, 16.11.17):
No to nie wiem, są jeszcze takie zwijane
Chell (18:51, 16.11.17):
bez max i min wartości w sensie
Chell (18:50, 16.11.17):
ale nie, bo wciąż zależy mi na samej czynności kręcenia, i żeby nie określał absolutnej wartości tylko inkrementowal i dekrementowal
Chell (18:50, 16.11.17):
masz refleks xD
I am Lord (18:48, 16.11.17):
encoder liniowy?
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.
Copyright © 2002-2017. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus (ranmus.pl), © 2017 {=|=} fable_inside();

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