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
24 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 23, userów: 1, ukrytych: 0
Wojo
Użytkownicy na czacie discord
MaxGaming (13:24, 21.10.18):
kurde trzeba było przeczytać umowę licencyjną to bym uniknął kłopotów haha
Wojo (9:26, 21.10.18):
Ponoć nabiał rozpuszcza kapsaicynę, polej się mlekiem. Tak czy inaczej jest to nauczka za kasowanie stopki z woocomerce
MaxGaming (0:21, 21.10.18):
jestem cały w gazie pieprzowym jakieś pomysły?
MaxGaming (16:53, 20.10.18):
a ktoś wie na pewno? xd
exp (16:16, 20.10.18):
wydaje mi się, że nie możesz tego usunąć z racji tego, że jest darmowa
MaxGaming (13:53, 20.10.18):
zresztą precież woocomerce usuwa ze stopki jakby wpis że to wordpress
MaxGaming (13:53, 20.10.18):
to akurat nie jest takie oczywiste bo wydaję mi się że w przypadku woocomorce nie jest to zakazane
Wojo (8:45, 20.10.18):
Jak usuniesz to będziesz
MaxGaming (0:33, 20.10.18):
chodzi mi jak to z licencją jest, czy nie będę jej łamał
Wojo (22:17, 19.10.18):
zresztą, nie wiem
Wojo (22:16, 19.10.18):
tak
MaxGaming (19:21, 19.10.18):
Czy mogę usunąć w stopce "Zbudowany za pomocą Storefront i WooCommerce."?
Wojo (12:55, 19.10.18):
i cała ta dychotomia społeczeństwa wydaje się śmieszna dla osoby, która ma trochę względnego obycia w różnych środowiskach
Wojo (12:52, 19.10.18):
zresztą, zaprzestańmy tej dywagacji oraz popisu swojej erudycji
Wojo (12:51, 19.10.18):
ja w ogóle nie rozumiem tej protekcjonalnej postawy
ANtY (8:05, 19.10.18):
stalaktyzacja??
MaxGaming (0:08, 19.10.18):
exp stagmatyzacji brania narkotyków podczas zawodów mma? XD
exp (23:32, 18.10.18):
nie wiem dokładnie o czym mówicie ale stygmatyzacji brania narkotyków nie rozumiem i chyba nie zrozumiem
Sutikku (18:21, 18.10.18):
w mojej opinii też był sćpany, pozdrawiam, aż specjalnie sobie obejrzałem te gale bo tak ogólnie to mnie to nie interesowało
Wojo (19:03, 17.10.18):
mam nadzieję, że wiesz co jest pięć
Wojo (18:44, 17.10.18):
Jezu MaxGaming przeczytaj raz jeszcze co napisałem (pierwsze zdanie zaczynające się kluczowymi słowami "W MOIM PRZYPADKU"
MaxGaming (16:30, 17.10.18):
Jezu Wojo przeczytaj raz jeszcze co napisałem(punkt 3).
Wojo (13:55, 17.10.18):
Niemniej jednak wielu ludzi twierdzi w takim momencie, że coś paliłem
Wojo (13:54, 17.10.18):
W moim przypadku czerwone oczy (właściwie to lekko różowe białka) oraz opadające powieki pojawiają się najczęściej zimą gdy wchodzę z zimnego dworu do ciepłego pomieszczenia. Zresztą co ja się będę tłumaczył jak tu każdy wie swoje
MaxGaming (13:41, 17.10.18):
I 1. czerwone oczy nie są po takich środkach tylko po marihuanizacji. 2. Czerwone oczy od kamery są trochę inne niż te po paleniu. 3, Tak, marihuanizacje ciężko rozpoznać bo jest tyle opcji by mieć takie czerwone oczy. 4, nie widzę u niego ani trochę czerwonych oczu. To jeszcze odnośnie wcześniejszej wiadomości
Wojo (13:39, 17.10.18):
xD
MaxGaming (13:36, 17.10.18):
uwierzył że nie był. Pokazywałem to kilku kolegą co dużo ćwiczą i kliku co znają mefedron i jego efekty. Wszyscy to samo stwierdzili co ja.
MaxGaming (13:34, 17.10.18):
Popieram. Tak jak mówię adrenalina nie działa tak na nikogo oprócz niego. Poza tym Wojo za młody jesteś widocznie i za mało zmefedrowanowanych osób widziałeś żeby nie wiedzieć co jest pięć. Uważam że każdy kto trochę miał z tym styczność w ciągu pierwszej minuty wywiadu zorientuje się co jest pięć. Ale ogólnie Wojo od dawna zauważyłem że masz takie dzieciakie, naiwne myślenie. To nie jest sprawa która jest dla mnie jakaś istotna był naćpany to był, to nie moja
Ignatus (13:11, 17.10.18):
Obserwuję od 15 lat MMA i Adbustera od początku.Był w h*j naćpany Nikt się tak nie zachowuje nawet 10 sekund po walce
Wojo (13:02, 17.10.18):
I jak próbujecie sobie i innym wkręcać, że był naćpany to jest godne politowania (żeby nie było, nie bronię go dlatego bo jestem jego fanem, wręcz przeciwnie, irytuje mnie jego osoba)
Wojo (12:57, 17.10.18):
to dlaczego by nie zrobić specjalnej gali dla takich walk?
Wojo (12:57, 17.10.18):
Pomysłów mają dużo, lepsze to niż wpakowanie na oficjalną galę jednej walki aktora z muzykiem. I tak każdy nie będący w temacie ogląda galę dla tej jednej "popularnej" walki. Skoro w telewizji i w internecie trąbi się o wygranej muzyka z aktorem, a większość zwycięstw w tej samej gali pomija
Wojo (12:55, 17.10.18):
Uważajcie jak chcecie. Moim zdaniem taka oficjalna gala freakfightów jest dobra, zawsze coś ciekawego się dzieje. Jednemu wypada szczęka, drugi łamie nogę, trzeci chudzielec bije się z mięśniakiem, walki bliźniaków
ANtY (12:51, 17.10.18):
sorki ale nie bede tego ogladal xd
Ignatus (11:40, 17.10.18):
Obejrzyjcie wywiady ze wszystkimi uczestnikami FAMEMMA po walce, ba ,obejrzyjcie losowe kilkanaście/kilkadziesiąt wywiadów minuta po walce- NIKT NIGDY nie zachowywał się jak AdBuster- nawet oficjalny ćpun Popek .To on jeden na świecie tak reaguje na "emocje" że w niczym nie przypomina siebie na codzień?Nie ma co bronić typa-ewidnentnie się naćpał...
MaxGaming (11:37, 17.10.18):
no znam tą walkę
MaxGaming (11:36, 17.10.18):
To że oni się tak słabo przygotowują to właśnie problem. Z drugiej strony jedną rundę a nie kilka ciosów xd Poza tym mam na myśli takie nastawienie żeby wygrać z kimś zamiast pokonywać swoje słabości. To bardzo nie sportowy sposób myślenia. Jak rozróżniam jedno od drugiego? Jeśli myśli o wygranej z przeciwnikiem kombinujesz jak go przechyrzyć tak na prawdę(dowiedzieć się jakoś jaką ma stategie i treningi, a to wziąć jakąs przedtreningówkę fajną lub zaćpać, a t
Wojo (10:12, 17.10.18):
Zobacz słynną walkę pudziana z najmanem (najman przegrał jak coś), ona nie trwała długo między innymi z tego względu, że to był freakfight
Wojo (10:11, 17.10.18):
wyjaśnienia były 15 października czyli jakoś dwa dni po gali (jeśli się nie mylę), a jeśli chodzi o szybkie walki to trudno się spodziewać półgodzinnych walk jak u zawodowców. To są ludzie trenujący średnio po dwa miesiące i daleko im do zawodowego poziomu
MaxGaming (4:07, 17.10.18):
tylko dwie weszły do drugiej rundy jak dobrze pamiętam
MaxGaming (4:07, 17.10.18):
pomijam już ile trwały walki
MaxGaming (4:06, 17.10.18):
wgl nie ten state of mind zawodników
MaxGaming (4:06, 17.10.18):
dla mnie tam mało było sportu
MaxGaming (4:06, 17.10.18):
A rafon to otwarcie mówił że lubi sterydy tylko ileś tam przed walką musi przestać i po walce znowu ostro sterydy
MaxGaming (4:04, 17.10.18):
Zresztą nas to nie dotyczy to w sumie nie istotne. ale tak czy siak ja jestem w 90% pewien że coś tu mocno nie grało i stawiałbym na jakieś stymukanty/euforyki nowej generacji
MaxGaming (4:02, 17.10.18):
ja ogldałem jeszcze przed walką jakiś wywiad, nie pamiętam ile przed. Ale wysłalem znajomym że on jest na 80% naćpany. Było to widać ale nie tak mocno jak tutaj gdy doszły emocje. A mefedropodbne rcki mają ro do siebie że emocje są przetwarzane trochę inaczej i jeśi są duże to bardzo łatwo komuś kto wie co jest 5 rozpoznać czy ktoś jest porobiony czy nie nawet bez takich rzeczy jak źrenice itp
MaxGaming (4:00, 17.10.18):
można gdybać ale albo gośc ma jakieś mocne zaburzenia psychiczne albo był naćpany, nie chce mi się wierzyć że tak wygląda trzeźwy człowek Mam znajomych którzy trenują sporty walki, widziałem już ich naladowanych po wygranej czy przegranek walce gdy nimi emocje kipiały ale to zupełnie co innego. Podobnie zawodicy fame mma 2. Oprócz niego nikt nie wyglądał na naćpanego a nie jednym emocje mocno targały
MaxGaming (3:59, 17.10.18):
YT nie działa akualnie Wojo ale jeśli to ten filmik gdzie adbuster pokazuje testy zrobione tam chyba 9 czy 10 dni po to już wyjasniłem to wcześniej
MaxGaming (3:58, 17.10.18):
oglądłem najpierw całe wywiady i znim zobaczyłem tą kompilację już w pierwszej minucie wiedziałem co jest pięc
Wojo (10:48, 16.10.18):
www.youtube.com...h?v=XhmsV_IBles tutaj masz jakieś wyjaśnienia
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.03265 sekund ] [ Liczba zapytań MySQL: 13 ]