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
15 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 14, userów: 1, ukrytych: 0
I am Lord
Użytkownicy na czacie discord
Uzjel (22:42, 25.05.18):
Max, spróbuj piktochart
PsichiX (20:46, 25.05.18):
ale ja mowie serio. Ty chcesz infografike, ja mowie Ci moja cene za to.
Wojo (19:51, 25.05.18):
penguin robisz świetne pixelki
MaxGaming (19:11, 25.05.18):
Psichix nie próbuj być na siłę śmieszny bo Ci to nie wychodzi...
Danielus (19:11, 25.05.18):
RODO z GMC trafia do spamu w gmailu :d
PsichiX (18:44, 25.05.18):
50zl za 1024 piksle kwadratowe
MaxGaming (16:31, 25.05.18):
Jest ktoś kto mógłby mi machnąć infografikę?
gnysek (11:54, 25.05.18):
Toż bym z tych 20zł miesięcznie nie wypłacił sobie ZUSu za GMCLAN
gnysek (11:53, 25.05.18):
No moja firma działa jeszcze gdzieś indziej Poza tym, regulamin jest wspólny dla wszystkich stron, kosztowało mnie to dopisać "gmclan.org" do listy
Wojo (11:40, 25.05.18):
ale gmclan moze miec kare w granicach 6zł chyba ze gdzies indziej jeszcze dzialacie
gnysek (23:03, 24.05.18):
Kara jest od obrotów firmy, nie strony
Wojo (18:46, 24.05.18):
nie ma potrzeby tego robic imo, jakbys dostal mandat to przychód z gmclanu napewno go pokryje xD
gnysek (15:34, 24.05.18):
Niestety, pewnie wieczorem dodam popup o ciastkach również
gnysek (15:26, 24.05.18):
Jesteśmy gotowi na RODO, dodałem Politykę Prywatności
Ignatus (23:06, 20.05.18):
To bedzie w zasadach opcjonalnych- no i tylko jezeli przejdzie solidne testy, bo teraz dziala to wszystko idealnie wiec nie ma co kombinowac
I am Lord (22:58, 20.05.18):
Nie przekombinuj, chyba że chcesz zostawić to jako opcję dla zaawansowanych
Ignatus (22:49, 20.05.18):
wiec wrzucilem jako cel przyszly
Ignatus (22:49, 20.05.18):
ale to jeszcze nie przetestowane wiec do bazowej gry nie dodalem
Ignatus (22:49, 20.05.18):
to by dzialalo tak ze jezeli gracz ulozy karty o wartosci 1,2,3 (i w tej kolejnosci) dobiera 1 z 3 kart specjalnych
Ignatus (22:48, 20.05.18):
Jeszcze planuje przy przekroczeniu celu kampanii 10k dorzucic kilka kart i umiejetnosci
Ignatus (22:48, 20.05.18):
Pewnie że tak
I am Lord (22:42, 20.05.18):
żeby było więcej kart
I am Lord (22:41, 20.05.18):
kupując np 2 zestawy gry
I am Lord (22:41, 20.05.18):
zmodyfikować zasady*
I am Lord (22:40, 20.05.18):
zawsze można będzie zmodyfikować sobie jak się chce mieć losową rękę
Ignatus (22:33, 20.05.18):
Niektórzy na Pyrkonie dosłownie po 5 minut myśleli nad ruchem
Ignatus (22:32, 20.05.18):
Zerowa losowośc- gracze mają do dyspozycji symetryczne talie 7 kart od początku do dyspozycji.Jest takie ciężkie kombinowanie że aż sam jestem w szoku
I am Lord (22:28, 20.05.18):
Teraz przeczytałem opis gry Humor taki jak u Pratchetta
I am Lord (22:13, 20.05.18):
A powiedz mi jak dużą rolę gra szczęście? Kółko i krzyżyk był grą o zerowym szczęsciu, nie da się go wygrać gdy staną przeciwko sobie przeciwnicy na tym samym poziomie. U ciebie elementem losowym jest talia kart tak? Czy rozdanie mocno wpływa na przebieg gry?
I am Lord (22:11, 20.05.18):
Przez ciebie mam chęć zrobienia takiej gierki samemu
Uzjel (22:00, 20.05.18):
Od razu z góry mogę zaproponować port na iOS'a, bo właśnie się uzbroiłem w CAŁY sprzęt Powodzenia!
Ignatus (21:54, 20.05.18):
A jezeli sie powiedzie to oczywiscie bede to przekuwał w multi na andka w przyszłości
Ignatus (21:53, 20.05.18):
Ujzel:wydawcą jest póki co wspieram.to ;p Ale juz rozmawiam z jednym sklepem większym który mnie wychaczyl na Pyrkonie
Ignatus (21:51, 20.05.18):
Jak się skonczy kampania to beda chodzic w sklepie po 30-35 wiec na pewno jakis zysk bedzie
Ignatus (21:50, 20.05.18):
Bardzo dziękuje!!!!!!!!
Uzjel (21:50, 20.05.18):
O! Albo sprzedam z zyskiem!
Uzjel (21:50, 20.05.18):
Na początku czerwca mam ostatnie zajęcia, więc pewnie się nie uda Rozdam planszówkowym kolegom.
I am Lord (21:49, 20.05.18):
Może ich też to natchnie
I am Lord (21:49, 20.05.18):
To rozdaj maluchom ze szkoły
I am Lord (21:41, 20.05.18):
a nie bo przesyłka będzie kłopotliwa :d
I am Lord (21:41, 20.05.18):
Na gmclan do konkursu
Uzjel (21:34, 20.05.18):
Też dorzucę, ale nie wiem co zrobię z dodatkowymi sztukami :p
I am Lord (21:30, 20.05.18):
Wow ignatus zasady wyglądają na faktycznie grywalne, nie mam i tak z kim w to zagrać chyba że zrobisz kiedyś giereczkę na PC czy androida ale dorzucę grosza
Uzjel (21:25, 20.05.18):
Fajnie Ignatus, kto będzie wydawcą?
Ignatus (19:46, 20.05.18):
Panowie zachęcam do wspierania mojej kampanii gry karcianej.Po prawie 100 partiach na Pyrkonie nieskromnie stwierdzam ze jest zajebsicie grywalna. wspieram.to/czarowieze
Wojzax (19:27, 20.05.18):
No mi najwięcej oryginalnych pomysłów wpada gdzieś w plenerze. Nie że związanych z tym plenerem po prostu tak wyjście mi czasem działa na mózg.
Wojo (19:15, 20.05.18):
za pieniądze z genialnego pomysłu możesz spłacić kredyt za który się wyprowadziłeś
Wojo (19:14, 20.05.18):
wniosek jest taki, że trzeba wyprowadzić się do ciepłych krajów
Sutikku (14:52, 20.05.18):
zawsze jak jest ciepło to tyle pomysłów do tworzenia, a jak jest zima siedzi się w domu, tyle czasu i nic
I am vader (10:33, 19.05.18):
Bry :v
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.02672 sekund ] [ Liczba zapytań MySQL: 13 ]