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
4 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 4, userów: 0, ukrytych: 0
Użytkownicy na czacie discord
doctor (11:31, 26.04.19):
Np. PHP umożliwia przerobienie JSON na tablice, tablice można sortować, mieszać (...), a w GM CHYBA trzeba użyć DSów
doctor (11:30, 26.04.19):
Ja się zdecentralizowałem, elo benc. Ciekawi mnie czemu w GM stosuje się DSy zamiast ogarnąć strukturę tablic?
Wojo (11:11, 26.04.19):
Fervi czasami był człowiekiem dalszym od rzeczywistości niż ja sam.
doctor (0:18, 26.04.19):
A no (Steem dokładniej). Trochę upada, ale parę gier jest (czy dobre ...? Tak sobie). Steem Monsters, Drug Wars czy NextColony
I am Lord (23:10, 25.04.19):
Fervi już chyba z 2 lata temu coś gadał o blockchainowym steemit
MaxGaming (21:52, 25.04.19):
Ja jak przeglądam fora biznesowe to kojarzy mi się od razu z bajką Pinki i Mózg - "Co dzisiaj robimy? - Jak to co? Budować kolejnego blockchaina!"
doctor (21:08, 25.04.19):
Kiedyś czytałem o blockchainie do robienia zdecentralizowanych baz danych, chyba kompatybilnych z SQLite
MaxGaming (18:18, 25.04.19):
Plotki mówią, że niedługo powstanie blockchain do robienia blockchainów
doctor (17:50, 25.04.19):
Nie no, już kiedyś mówiłem xD Czasem jak projekt wypali (pewnie nie) to nagle dają dużo hajsuf
Wojo (17:30, 25.04.19):
Jest 2019 rok, trudno się dziwić, że nawet na niszowym forum ktoś o tym wspomniał
MaxGaming (14:40, 25.04.19):
Kiedy nawet na gmclanie ludzie już mówią o blockchainie
doctor (14:08, 25.04.19):
hmm, nie o to mi chodziło, ale może coś wywnioskuję
doctor (14:05, 25.04.19):
No proszę, widać da się zrobić mój projekt i zintegrować z magicznym blokczejnem - dzięki
gnysek (11:34, 25.04.19):
Oczywiście, że tak. Jest przykład wysyłania i odbierania danych na stronie - gmclan.org/index.php?plik=227
doctor (11:23, 25.04.19):
Pytanie też inne - czy może się strona w PHP jakoś skomunikować z grą? Np. by grać potrzebujesz się autoryzować w PHP, który potem login ze strony przekazuje do gry?
doctor (11:20, 25.04.19):
To spróbuję, bo myslałem, że 1.4 początkowo nie miał takiej opcji, a to w sumie dużo by zmieniło ... Tylko muszę ogarnąć jak wgrać Game Makera, bo tak sobie chodzi
gnysek (0:34, 25.04.19):
Generalnie do tej samej domeny bez problemu.
gnysek (0:34, 25.04.19):
Zawsze się dało. Tylko nie do każdego serwera ale to już zabezpieczenia przeglądarek. Poczytaj o CORS.
doctor (19:42, 24.04.19):
Czy da się wysyłać HTTP Requesty (Events) z poziomu gry w GMS1.4 HTML5? Bo kiedyś się chyba nie dało ...
doctor (19:41, 24.04.19):
Moim zdaniem Game Maker poniżej Studio 2.0 są specjalnie komplikowane. Wgranie 1.4 jest wielkim problemem Elo
SimianVirus7 (20:50, 18.04.19):
ten program działa, bo odpalanie starych game makerowych gier w trybie zgodności nie zdaje egzaminu (przynajmniej u mnie)
exp (17:52, 18.04.19):
pamiętam że ktoś zrobił naprawdę dobrego tower defence na początku ligi
MaxGaming (21:21, 17.04.19):
groups.google.c...ers/w17mO9qGiD0 - możliwe, że to by komuś mogło pomóc. Resztę kodu mam tylko potrzebuję systemu który pozwoli mi rozgraniczyć sesję przeglądarki między kontrolkami webbrowser
MaxGaming (21:15, 17.04.19):
Jest ktoś w stanie napisać mi funkcje o której mówię w poście na forum(abym mógł w dwóch kontrolkach webbrowser być zalogowany na dwa różne konta na stronach WWW) za 50-150zł? Podejrzewam, że jeśli ktoś zna rozwiązanie to jest kilka linijek kodu, ale ja nie mam pojęcia już jak to ugryźć. Blokowanie ciasteczek uniemożliwia logowanie, a usuwanie ich co sesje usuwa też z innej aktywnej sesji.
I am Lord (18:50, 17.04.19):
A zobaczcie jakie gierki były robione na ligę na początku. Przecież z nich teraz by szło zrobić całkiem dobre pełnoprawne gierki, kiedyś to był gmclan
nowy_user (15:24, 17.04.19):
Z drugiej jednak strony, gdyby wspomniani GMclanowicze urodzili się 15 lat później i ich czas twórczości przypadłby na dzisiejsze czasy, to bez wątpienia zostaliby pełnoetatowymi twórcami gier i mogliby spełniać swoje marzenia. A tak to nie wiadomo co z nimi się dzieje, pewnie mają jakąś ‘normalną’, wysysającą z kreatywności i nadziei pracę.
nowy_user (15:05, 17.04.19):
To prawda, GMS nas rozpieściło. Kiedyś, gdy prawie nikt nie zarabiał na tworzeniu gier w GMie, to tworząc nowy projekt nawet nie myślałeś o $, tylko o tym, aby innym sprawić radość. Dzięki temu mieliśmy okazję zagrać w naprawdę niezłe produkcje za free, a gdyby powstały dziś to musielibyśmy za nie słono zapłacić. Mam tu na myśli np. Bruce Lee 2004 Mataska, Mario Forever Borka czy też Jump! Jump! Anacondy.
I am Lord (13:09, 17.04.19):
bo odbiera przyjemność
I am Lord (13:09, 17.04.19):
A teraz z co bym się nie zabrał to myślę z tyłu głowy jak na tym zarobić i to mi psuje wszystklo
I am Lord (13:08, 17.04.19):
Kiedyś to było, robiliśmy gry dla samej frajdy i była masa pomysłów
gnysek (10:58, 17.04.19):
na szczęście takich artystów jak BigShark i PrzeAss kojarzę.
gnysek (10:36, 17.04.19):
Liczę na Cairo 4
I am Lord (0:05, 17.04.19):
xd
I am Lord (0:05, 17.04.19):
BigShark
Wojo (16:00, 16.04.19):
Nieważne, już znalazłem
Wojo (16:00, 16.04.19):
Ja jakoś nie mogę znaleźć profilu Pietra.
Wojo (15:45, 16.04.19):
To jest na tyle bierny człowiek, że nie zakładał wcześniej konta
gnysek (15:38, 16.04.19):
mnie zastanawia kim faktycznie jesteś, bo nie nowym_userem, znasz znacznie więcej historii niż ja.
nowy_user (20:02, 15.04.19):
Chociaż Ranmus chyba wybaczył już Pieterowi(przywódcy buntu), bo zdaje się że widziałem Pietera ostatnio na GMclanie. Po wielu latach w końcu zakopali topór wojenny
nowy_user (19:57, 15.04.19):
I tak wygląd jest dużo lepszy niż u konkurencji, mam tu na myśli oczywiście GMxxl. Ich stronka chyba już nawet nie istnieje, pewnie Ranmus ma osobistą satysfakcję: swego czasu kilku prominentnych użytkowników Gmclanu nieźle napsuło mu krwi, tworząc Gmxxl'a, dokonując tym samym wielkiego rozłamu na Polskiej scenie GMa.
MaxGaming (19:34, 15.04.19):
Mi tam pasuję głównie wersja mobilna stronki. Jest świetna
gnysek (19:16, 15.04.19):
btw. kiedyś był taki podobny zielony motyw do jPortal, od Ranmy, ale niestety w odmętach internetu zaginął - niby w internecie jest wszystko, ale szczerze to 15 lat temu było więcej niż dziś
gnysek (19:15, 15.04.19):
żadne droczenie, nigdy nikt z was nic lepszego nie zaproponował, więc wiem, że każdemu pasuje
XBlacKX (15:22, 15.04.19):
też lubię ten wygląd, chciałem się podroczyć tylko
I am Lord (12:54, 15.04.19):
to jest niezła archeologia
I am Lord (12:54, 15.04.19):
Apropos Gothiczka @Wojo www.youtube.com...h?v=raudY3eVrGI
gnysek (11:34, 15.04.19):
btw. naprawiłem też wyświetlanie błędów przy wysyłaniu shoutów które... chyba nigdy przez 15 lat się nie wyświetlały, a były zaprogramowane Brakowało 2-3 linijek kodu.
gnysek (11:10, 15.04.19):
A skoro obecny działa... nie wiem czy sens go zmieniać, i tracić 300-400 godzin na pisanie zmian.
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.02921 sekund ] [ Liczba zapytań MySQL: 13 ]