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
4 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 3, ukrytych: 0
I am vader, Uzjel, hgter
Użytkownicy na czacie discord
Wojo (11:51, 20.06.18):
jest tak samo koło dupy jak polska koło grecji
gnysek (11:43, 20.06.18):
a udziec to nie jest jakoś koło dupy ?
Penguin (9:00, 20.06.18):
XD
Wojo (22:39, 19.06.18):
jak ból dupy może być pyszny? co najwyżej dupa może być pyszna ale zakładam, że taka nie jest
I am vader (21:55, 19.06.18):
Pysnzy jest bol dupy tych wszystkich cebulaczkow i sebixow ktorych obchodzi pilka nozna.
gnysek (20:23, 19.06.18):
to nie udawaj wielkiego fana, udawaj małego fana
Wojo (19:13, 19.06.18):
Mi to wszystko jedno bo i tak nie lubię piłki nożnej, po co udawać wielkiego fana bo Polska gra w piłke nożną?
MaxGaming (19:11, 19.06.18):
Jak mogliśmy to przegrać
Wojo (14:40, 19.06.18):
na necie można znaleźć ciekawe sekrety o nim ale ja nic nie wiem
Wojo (14:39, 19.06.18):
mnie bardzo ciekawi ten jego coaching. Gdybym miał pieniędzy bez końca to za te pieniądze zapewniłbym sobie niezłą rozrywkę
ANtY (13:36, 19.06.18):
www.pangrodzki....sklep/mars-2488 niech ktoś to kupi i powie mi czy jacek uporał sie z bałaganem
ANtY (13:24, 19.06.18):
www.pangrodzki....-damsko-meskich rozgalezil sie na wszystkie rynku
Chell (12:12, 19.06.18):
75% z teorii e13, już się niczego nie boję
MaxGaming (22:48, 18.06.18):
"to moja ulubiona stronka zaraz po gmclanie"
Wojo (22:48, 18.06.18):
w ogole skoncz typie spam w shoutboxie robic i pisac jakies bzdury zamiast wejsc na gmczat i siedziec w ciszy razem z 16 użytkownikami....
Wojo (22:47, 18.06.18):
nie wole bo tam nie wchodze takie zarty - serio
MaxGaming (22:46, 18.06.18):
Wolisz gmclan? Na prawdę jest on przed tą stronką?
Wojo (22:44, 18.06.18):
a to moja ulubiona stronka zaraz po gmclanie
MaxGaming (22:44, 18.06.18):
position_meeting - co zrobić żeby wykrywał mi maski także tych obiektów które są rysowane w gui? da się to zrobić?
Wojo (22:44, 18.06.18):
15 bez czytania
MaxGaming (22:42, 18.06.18):
nie no mordo żartuje oczywiście żeby nie bylo że jakiś złośliwy jestem
MaxGaming (22:42, 18.06.18):
15 z wliczona przerwą na czytanie komentarzy? xd
Wojo (22:42, 18.06.18):
no i czytam tylko komentarze i nikt sie tam niczym nie przejmuje
Wojo (22:41, 18.06.18):
pudło bo 15
MaxGaming (22:41, 18.06.18):
Wojo nie oszukjmy się, twoja przygoda na phubie pewnie trwa 30 sekund XDD
Wojo (22:40, 18.06.18):
i tak kilka ostatnich kartkowek poprawilem czytajac streszczenia bo bym nie zdał
MaxGaming (22:40, 18.06.18):
To jest raczej propozycja dla tych którzy lubią pracę nad sobą i ogólnie cieżką pracę a nie leniwienie się xd tacy to tylko do szkoły
Wojo (22:40, 18.06.18):
zamiast czytać małego księcia to teraz spędzam czas na robieniu tego co lubię czyli oglądaniu phuba
MaxGaming (22:38, 18.06.18):
Możesz przeczytać je samemu. Ja sam czytam lektury których nie przeczytałem w szkole jak mam wolny czas
Wojo (22:37, 18.06.18):
ale co mi po kasie jakbym nie znał przygód tomka sojera
MaxGaming (22:37, 18.06.18):
Nie rozumiem jak działa to draw_gui. Jak po prostu wstawię w room_editorze jakiś obiekt i dam mu w draw gui draw_self() to rysuje się jako gui, ale nie jest wykrywany w tym miejscu w którym jest ale w tym w którym go postawiłem na start(jakby maska się z nim nie przemieszcza) podczas użycia position_meeting
Wojo (22:37, 18.06.18):
ja gdybym 2 i 3 klasę liceum przesiedział w pracy to mialbym fajny pieniadz na rozruch
MaxGaming (21:55, 18.06.18):
kto po takiej szkole jest gotowy do pracy? Ja osobiście czuję się oszukany i czuję że zmarnowałem te 4 lata. CHociaż moze nie zmarnowałem bo mam już doświadczenie
MaxGaming (21:55, 18.06.18):
nikt nigdy nie wspomniał nawet słowem o jquery a co mówić dalej w szkole
MaxGaming (21:55, 18.06.18):
Uważam że jeśli ktoś nie wie do końca czego chce, albo ma bardzo słabe pojęcie o IT to spoko jest technikum. Jeśli ktoś zna się już na tym czym chce trochę to lepiej usiąść w domu i pouczyć się samemu z książek/kursów/tutoriali
MaxGaming (21:54, 18.06.18):
Robisz technika 4 lata i nikt praktycznie nie bierze go pod uwagę
MaxGaming (21:53, 18.06.18):
jak kończyłem czwartą jeden już jeździł w audi za 150 tyś a drugi w mercedesie za 80tyś nie mówiąc o reszcie hajsu
MaxGaming (21:52, 18.06.18):
Moich dwóch znajomych rzucili technikum na pierwszym roku, posiedzieli 2 lata w domu ucząć się różnych technlogii front-end i back-endowych i założyli firmę kiedy ja byłem w trzeciej klasie
MaxGaming (21:49, 18.06.18):
Ale jak uczyli ich pisać wszystko z pamięci to nie dziwne...
MaxGaming (21:49, 18.06.18):
no kurde kto tak pisze strony internetowe? czego to ma nauczyć? I ciągle uczenei na pamięć. Nikt ode mnie z klasy nie umiał w jakikolwiek sposób debugować kodu. Jak zapomnieli wstawić średnika to wszystko pisali od nowa albo płacz proszę panią nie działa
MaxGaming (21:48, 18.06.18):
Albo na kartce papieru kazali nam pisać stronki całe
MaxGaming (21:46, 18.06.18):
Lub program/stronę dla klienta
MaxGaming (21:45, 18.06.18):
dostawaliśmy pracę na 4h to robiłem ją w godzinę a przez 3h na przykład robiłem kurs C# z jakiś stronek
MaxGaming (21:45, 18.06.18):
A co robiłem na lekcjach? Siedziałem i uczyłem się na własną rekę zupełnie innych rzeczy. Ale przeszkadzało mi to ze muszę tam siedzieć i jeszcze czasami tracić czas na jakieś durne zadania na zaliczenie podczas gdy ja w tym czasie uczyłem się zupełnie czego innego już
MaxGaming (21:44, 18.06.18):
Więc to wcale nie było tak że rozdawali te szóstki
MaxGaming (21:44, 18.06.18):
ostatnio jakąkolwiek szóstkę z zawowdowych w tej szkole miał ktoś 4 lata przede mna
MaxGaming (21:44, 18.06.18):
I były to jedyne 6tki z zawodowych w ciągu ostatnich 4 lat historii tej szkoły
MaxGaming (21:43, 18.06.18):
Ja z zawodowych miałem same 6tki na koniec
MaxGaming (21:43, 18.06.18):
Ale szkoła w Polsce w ogóle nie ma uczyć. Program nauczania E12/E13/E14 sprawia że człowiek wie o każdej z tych dziedziń tylko kompletne podstawy i nie nadaje się nawet zaliczając na 100% wszystkie egzaminy do pracy w jakimkolwiek zawodzie jeśli sam się nie douczy
Wojo (21:42, 18.06.18):
w szkole niskie oceny miałem za zbędną teorię. Sprawdzian z lektury itp. A z wypracowań miałem piąteczki ale co z tego skoro o kant uja mozna to rostrzasc
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.02032 sekund ] [ Liczba zapytań MySQL: 13 ]