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
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
118 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 117, userów: 1, ukrytych: 0
Ignatus

0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
Threef (19:32, 22.06.17):
gnysek na Ultimate, na X1 i PS4. 3 Moduły są teraz na subskrypcję
gnysek (19:16, 22.06.17):
Subskrypcja jest tylko na Ultimate, na resztę nie.
I am Lord (19:01, 22.06.17):
Vader no tutaj na głównej: i.imgur.com/SPrqXPK.png
Threef (17:42, 22.06.17):
Na razie to info że exporty na X1 i PS4 są ważne na 12 miesięcy
I am Lord (17:41, 22.06.17):
Teraz żałuję że kupiłem go :/
I am Lord (17:40, 22.06.17):
Najpierw baitują że nie będzie subskrypcji a teraz ją wprowadzają
Adriann (17:36, 22.06.17):
Cooooooooooooo?!
Threef (17:25, 22.06.17):
Przepraszam co...? GM:S2 ma mieć teraz moduły subskrypcyjnie? Na 12 miesięcy? lol
I am vader (13:39, 22.06.17):
Nie wiem jak dotrzeć do tego działu nawet
I am Lord (11:45, 22.06.17):
im vader moj jest w assorted top down
PatrykPlayingPOLSKA (10:00, 22.06.17):
Mi się wydaje że większość gości to boty ale może być też paru ludzi,trzeba jakoś zachęcić ludzi do zarejestrowania na tym forum,np można jakoś polepszyć tą polską dokumentajcę,coś do niej dodać,na steamworkshop gamemaker można jakoś popisać że jest takie ciekawe coś jak GMC,no sposobów może być wiele.
nowy_user (9:30, 22.06.17):
Chell , aktywnych userów może i dziesięciu, ale np. w tej chwili jest 133 gości! Unbelievable! Swoją drogą , ciekaw jestem dlaczego ludzie się tak ukrywają, zamiast po ludzku się zarejestrować.
Chell (22:56, 21.06.17):
niestety sprzedawanie assetow po zlotowke na ktore zbija sie po 5 osob jest malo oplacalne na forum na ktorym jest 10 aktywnych userow
nowy_user (22:52, 21.06.17):
A może powinniśmy stworzyć własny markietplace tu na gmclanie? Ja widzę same plusy: Po pierwsze - > ceny byłyby w złotówkach, więc więcej ludzi mogłoby sobie na nie pozwolić, Po drugie -> Nie wiem jak wy, ale ja wolałbym wspierać finansowo programistę od nas , ktoś kogo znam z forumowej aktywności zamiast jakiegoś anonimowego geeka z Californi lub Colorado. I po trzecie -> Zmotywowało by to nas wszystkich do twórczości.
I am vader (22:48, 21.06.17):
A który asset jest twój? Przegrzebałem showcase i top rated i nic podpisanego HuderLord nie znalazlem
I am Lord (19:06, 21.06.17):
Aha no super, nic się na głównej nic nie zmieniło pół toku już mój asset tam jest, yoygames zapomniało że ma ten MP że go nie moderują?
I am Lord (19:04, 21.06.17):
Dawno nie zaglądałem tam
nowy_user (12:47, 21.06.17):
Przepraszam , miało być Uzjel.
nowy_user (12:47, 21.06.17):
Ujzel: Właściwie jest cała masa świetnych assetów, wczoraj odkryłem marketplace i jestem pod wrażeniem co można zrobić w GMie, od razu chciałbym kupić wszystkie A tak całkiem serio to ten asset jest obłędny: marketplace.yoy...845/text-inputs Jest demo do ściągnięcia, no po prostu miodzio, bez porównania do darmowych , zbugowanych assetów
Chell (12:47, 21.06.17):
a 1 dolc a 5 ziko to, umowmy sie, nie jest az tak kolosalna roznica
Chell (12:46, 21.06.17):
user tobie to latwo bo w tych czasach warny sa tylko za bycie botem i dziecieca pornografie
Uzjel (12:42, 21.06.17):
Punkt 5 marketplace.yoy...games.com/terms
Uzjel (12:39, 21.06.17):
A jaki asset cię interesuje?
nowy_user (12:38, 21.06.17):
A z tymi zbiórkami to też chodziło mi bardziej o uczciwe rozwiązanie względem twórcy, żeby uszanować jego pracę, tzn . nie zbiórki po 20 osób na jeden asset, a raczej dwie lub 3 osoby max. Wtedy to miałoby sens imho.
nowy_user (12:35, 21.06.17):
Za free może nie, najrozsądniej byłoby zostawić wartość liczbową niezależnie od kraju natomiast zmieniać znak walutowy dla każdego kraju z osobna tzn dany extension kosztuje 19 $ dla mieszkańców USA, tym samym 19 GBP dla mieszkańców GB, 19zł dla mieszkańców Polski i 19 Juanów chińskich dla mieszkańców Państwa Środka.
Ignatus (12:29, 21.06.17):
Hmm to idąc tym tropem tacy mieszkańcy np Egipt powinni mieć wszystkie assety za free ?
nowy_user (11:35, 21.06.17):
Dlatego pora z tym skończyć, musimy tylko dostać zielone światło od góry na założenie takiego tematu, ponieważ rejestując się tutaj obiecałem sobie, że nigdy nie dostanę ani jednego warna.
Wojo (10:57, 21.06.17):
Ale po co mają sie dostosowywać do Polaków skoro Polacy dostosuja sie do innych
nowy_user (10:30, 21.06.17):
Wiesz w kwestii uczciwości to wydaje mi się, że wszystkie ceny w markecie w dolarach powinny być 4 razy tańsze dla Polaków , ponieważ dla Amerykanina 1$ to tak jak 1 zł dla Polaka. Zdaje jednak sobie sprawę z kontrowersji, i aby uniknąć warna wolę wcześniej zapytać zanim otworzę temat z propozycją zbiórki na różne extensiony.
Ignatus (10:12, 21.06.17):
Oczywiscie ze mozna, po zbiorce siana ten ktory kupil wyeksportuje asset z projektu i przesle rzeszcie ;p Uczciwe?Niekoniecznie- ale da się na pewno
nowy_user (9:45, 21.06.17):
Mam oczywiście na myśli marketplace z twórczością użytkowników GMa a nie sam sklep z głównymi produktami yoyo
nowy_user (9:02, 21.06.17):
Hej, czy można "złożyć się" w kilka osób i kupić jakąś rzecz w yoyo markecie? czy to jest dozwolone? Pytam, bo przez to, że ceny są w $, niektóre rzeczy są po prostu drogie.
Chell (22:16, 20.06.17):
prawda, rano padł mi dotyk w telefonie a aż tak mi nie zależy na alternatywnym wizerunku żeby korespondować mailami
Threef (22:11, 20.06.17):
Chell ponownie na fejsiku
Wojo (21:10, 20.06.17):
nie ma co się obijać do pracy rodacy :3 i tak aż do śmierci
nowy_user (19:21, 20.06.17):
Nie no, tak sobie czasem człowiek tylko ponarzeka, ale koniec końców jakby przyszło nam znowu korzystać z GM 5 lub GM 3 to pewnie byśmy błagali Gnyska i Ranmusa, żeby oddali nam GM:Studio
I am Lord (18:41, 20.06.17):
Gdzieś miałem GM3, chcesz : >
Chell (17:02, 20.06.17):
"Gm powyzej 7,0 to skandal" ~Wojo
nowy_user (16:56, 20.06.17):
Gnysek, najchętniej to bym cofnął wszystkie zmiany, od czasu GM 5.1 hehe, i w spokoju, gdzieś w drewnianej chatce programowałbym sobie w tym zacnym programie, co jakiś czas zerkając na równie drewniany gmclan. No ale cóż czasy bardzo szybko się zmieniły, a ja tak bardzo nie lubię zmian.
gnysek (15:45, 20.06.17):
Tak robią wszystkie nowoczesne IDE. Chcesz cofać zmiany - masz Ctrl+Z albo gita.
nowy_user (15:20, 20.06.17):
Dlaczego GMStudio robi mi autosave w momencie gdy klikam run ? W ogóle o to nie pytając?!
Chell (15:11, 20.06.17):
ja 100, generalnie zawsze bylem troche bardziej kumaty od innych
Wojo (14:30, 20.06.17):
Ja na gimbazjalnym tez mialem 98
gnysek (13:42, 20.06.17):
no, ale dalem temat w Valhalli forum.gmclan.or...showtopic=33625
nowy_user (13:39, 20.06.17):
Gratuluję, choć przyznam szczerze że ja też na maturze zdałem dość dobrze angielski ale dopiero teraz uczę się prywatnie z nativem , i widzę jak "kwadratowy" był mój język po nauce w szkole. Zalecam nie osiadanie na laurach i praktykowanie języka.
Sutikku (13:25, 20.06.17):
98% angielski gimnazjalny, elo i pozamiatane
ANtY (11:34, 20.06.17):
pozamiatane
Chell (11:13, 20.06.17):
35/40 z teorii E12, elo
nowy_user (14:17, 19.06.17):
Thank You very much indeed! Dzięki to działa!
Ankieta
» Jakiej wersji GameMakera głównie Używasz?
GameMaker: Studio 2
GameMaker: Studio
GameMaker 8.1 i starsze
Żadnej

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!

[ Czas generowania strony: 0.01462 sekund ] [ Liczba zapytań MySQL: 15 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev