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
I am vader
Użytkownicy na czacie discord
I am vader (12:50, 18.08.18):
gratki
Penguin (11:29, 18.08.18):
Gratulacje
exp (22:07, 17.08.18):
gratuluję również, kariera z przyszłością
Chell (15:00, 17.08.18):
dzieki
Wojo (11:37, 17.08.18):
Gratulacje
Chell (7:00, 17.08.18):
jaką stawkę myślicie że mogę wołać ako junior php po miesiącu praktyk i 2 stażu?
Chell (6:59, 17.08.18):
gmclany, zaraz będę kończył staż i zaczynał pracę na pół etatu
gnysek (9:54, 16.08.18):
niewiele, ale jest szybsze.
MaxGaming (3:25, 16.08.18):
Skoro pliki o rozszerzeniu html(przy standardowej konfiguracji serwera) są po prostu wyświetlane, a te z rozszerzeniem php wykonywane to czy użycie pliku html o tym samym kodzie jest szybsze niż pliku php(jeśli w źródle pliku znajduje się oczywiście sam kod hrml)?
Wojo (17:12, 15.08.18):
Exp podglądaj sobie reportaże o chwilowkach i o tym jak ludzie mają problemy z wyjaśnieniem że nie brali żadnego kredytu
exp (15:16, 15.08.18):
max czemu nie mógł udowodnić, nie chcieli sprawdzić jego podpisu? numer dowodu się zgadzał?
exp (15:15, 15.08.18):
no to też może się przydać, bo typ na koncie google miał podane imię i nazwisko i w adresie prawdopodobnie miał datę urodzenia, więc jak ktoś mnie okradnie, to mam podejrzanego. ale wątpię, że prokuratura będzie zainteresowana tym
I am vader (12:27, 15.08.18):
Nie powinno też się mordować ale to nie powstrzymuje ludzi
Wojo (22:26, 14.08.18):
Ale z drugiej strony nie powinno się kogoś okradać mimo wszystko
Sutikku (21:57, 14.08.18):
exp w formie dowodu mógłby pokazać, że nieumyślnie wysłał komuś swoje dane?
MaxGaming (17:37, 14.08.18):
Mój znajomy własnie wpadł w taką chwilówkę i jako że nie potrafił udowdnić że to nie on wziął to musi to spłacać
exp (17:36, 14.08.18):
no jak czytałem o tym, to w takiej sytuacji musisz de facto udowodnić niewinność
Wojo (19:56, 13.08.18):
z tym są różne scenariusze ale i tak powinien ktoś to uregulować bo to jest nienormalne jak mozna czlowiekowi zniszczyc zycie przez bledy mlodosci
exp (19:46, 13.08.18):
zna mój adres zameldowania, a nie zamieszkania, więc wyjebongo. boję się tylko o chwilówki itd. podobno w razie przyjścia komornika łatwo zamknąć sprawę, ale i tak nie chciałbym takich nieprzyjemności
Sutikku (19:29, 13.08.18):
osobiście myślę, że nic Ci nie grozi, ewentualnie pizza co wieczór będzie przyjeżdżać
exp (15:33, 13.08.18):
przez głupią literówkę wysłałem skan pewnego papieru niewłaściwej osobie. robię to regularnie i zrobiłem się trochę nieostrożny
exp (15:31, 13.08.18):
myślicie, że grozi mi coś, jeśli obcy człowiek posiadł prawie wszystkie moje dane osobowe? (ale nie zna mojego numeru dowodu)
gnysek (10:20, 11.08.18):
Dobra zrestartowałem serwer.
gnysek (10:36, 10.08.18):
wynajem!
MaxGaming (0:23, 10.08.18):
chodiz mi bardziej o doświadczenie niż hajs bo pracować wolę na swoim za mniej niż na etacie za więcej ale jednak pierwsza praca po technikum informatycznym od razu w marketingu to fajna sprawa. Tylko jeździć ponad 100km w jedną stronę codziennie pociągiem?
MaxGaming (0:22, 10.08.18):
więc nie mam pojęcia co robić
MaxGaming (0:22, 10.08.18):
wgl to zaproponowano mi prace w dziale marketingu jednej z polskich firm dzięki temu co uczę się na własną rekę, sam dyrektor działu marketingu stwierdził że woli takie osoby niż te świeżo po studiach które na studiach nie nauczą się praktycznie nic co jest na prawdę potrzebne w tej pracy ale... w WWA a ja mam jednak daleko żeby codziennie tam dojedżać
MaxGaming (23:56, 9.08.18):
nie wytłumaczysz że na prawdę rząd nie może stworzyć tych pieniędzy na 500 plus
MaxGaming (23:55, 9.08.18):
Obsługi telefonu dziecko się samo potrafi nauczyć. Teraz spróbuj nauczyć tego moją babcię. Zrozumcie że ludzie są różni. Znam 20 latków których
I am Lord (23:13, 9.08.18):
I nie chodził na żadne dokształcające najęcia
I am Lord (23:13, 9.08.18):
Mój tata pojechał do Norwegii bez języka i się nauczył go w rok już tak że coś tam rozumiał w pracy a przez 3 latach już w miarę płynnie gada
I am Lord (23:11, 9.08.18):
Przebywanie w obcym środowisku dłuższy czas sam w sobie uczy człowieka jezyka
Sutikku (22:46, 9.08.18):
zgadzam się
MaxGaming (22:40, 9.08.18):
Ale język nie jest potrzebny żeby przetrwać widocznie. Odpuścice trochę. Każda rozsądna osoba by się uczyła języka ale nie jest to jakiś przymus. Myślę że to właśnie dzięki temu że takie osoby nie myślą "nie znasz języka, nie próbuj" to przynajmniej nie siedzą na zasiłkach w Polsce tylko na zmywaku w Anglii
Sutikku (22:36, 9.08.18):
o przepraszam za przekleństwa, wydawały się tak adekwatne do treści, ze nie zauważyłem.
Sutikku (22:34, 9.08.18):
a co to za robienie gierek jak wychodzą Ci chujowe i są rakiem gamingu, i co z Ciebie za żołnierz jak chujowo strzelasz? Grunt, że próbują, efekty słabe fakt. Nie uważam, że to dobre i mądre wyjście, nie miałbym strefy komfortu gdybym nie mógł komunikować się w czyimś kraju, ale potrafię takich ludzi zrozumieć. Dziwniejsze jest dla mnie, że będąc tak długo w danym kraju język sam się nie podłapie.
Wojo (21:20, 9.08.18):
najwyraźniej nie jesteś patustem skoro nie potrafisz pojąć tego jak można żyć na krawędzi i bez żadnych zmartwień
I am vader (20:11, 9.08.18):
Ale co to za życie jak się izolujesz i stajesz się rakiem narodu?
Sutikku (17:40, 9.08.18):
potrafią i próbują ;p
Sutikku (17:40, 9.08.18):
słabe porównania, bo za granicę przeważnie jedzie się zarobić i żyć, a skoro oni zarabiają i żyją, to więcej im do szczęścia nie trzeba
I am vader (17:20, 9.08.18):
Jak idziesz na wojnę uczysz się strzelać, bo inaczej zginiesz. Jak chcesz zrobić grę to uczysz się programowania, bo inaczej nie dasz rady. Jak idziesz do szkoły uczysz się tego co Ci każą, bo inaczej jesteś idiotą. Jak wyjeżdżasz za granicę, uczysz się jezyka i kultury, bo inaczej jesteś pasożytem. Proste. Nie potrafisz, nie próbuj.
Wojo (14:32, 9.08.18):
Zazwyczaj są to ludzie, którzy nie lubią gdy narzuca im się jakiekolwiek zasady
exp (13:44, 9.08.18):
max, jeżeli nauczenie się języka kraju, w którym mieszka się na stałe jest dla niektórych niemożliwe ze względu na "strefę komfortu" to już nie wiem, co mam powiedzieć xd
exp (13:43, 9.08.18):
też znam ukraińców, którzy mówią po polsku, niektórzy bardzo dobrze. tak samo, jak wielu polaków w anglii czy niemczech też dobrze zna język miejscowy. nigdzie nie mówiłem, że wszyscy są źli, ale wielu
Wojo (13:15, 9.08.18):
propaganda cały czas istnieje tylko jest bardziej lub mniej intensywna. Aktualnie nie ma żadnej szansy aby dziecko nie było skażone propagandą (no chyba, że mieszka w jaskini)
MaxGaming (12:14, 9.08.18):
nie słuchałem jak ktoś kiedyś na tym forum polecał w każdym nowym telefonie taśmą zaklejać ten czujnik zalania i teraz mam problem XD
MaxGaming (12:09, 9.08.18):
za dużo propagandy już poszło. Trzeba by czekać a nowe pokolenie które nie jest skażone propagandą A o zgrozo propaganda nie ustaje
MaxGaming (12:08, 9.08.18):
W sumie demokracja to jedna wielka pułapka. Co możemy niby zrobić? Chodzić po domach i tłumaczyć ludziom żeby głosować na inne partie? Nie da rady przekonać większości
MaxGaming (12:07, 9.08.18):
sądzą że są sprytni bo wolą PO albo PiS, a to jest jeden ciort
MaxGaming (12:07, 9.08.18):
Ale tak jest w obie strpny. "Wpjna" PO/PiS to pułapka w którą większośc ludzi się łapie
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.03094 sekund ] [ Liczba zapytań MySQL: 13 ]