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
44 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 41, userów: 3, ukrytych: 0
♔ Adriann ♔ , ANtY, ediepl

0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
Wojo (12:55, 25.05.17):
Ale i tak niektórzy żyją we własnym świecie w którym Windows jest złem numer jeden
Wojo (12:50, 25.05.17):
Mam na myśli te pseudo doskonałe sposoby którymi nabijacie kabze spryciarzowi
Wojo (12:49, 25.05.17):
Ale fakt faktem znaczna większość sposobów na zarabianie w necie jest poprostu mało opłacalna. No chyba że chcecie sobie dorobić mając te szesnaście lat. Na dłuższą metę śmiesznie jest oglądać dorosłego człowieka który z klikania pół dnia w reklamy dysponuje pieniędzmi pokoju 500zl i jeszcze się rzuca
Wojo (12:46, 25.05.17):
Nawet się o taką pracę nie starałem. Twoja stara zajęła etat
Fervi  (12:26, 25.05.17):
Wiem, że za tańczenie na rurze więcej ci płacą, ale nie każdy ma takie możliwości
Wojo (8:46, 25.05.17):
500zl przy solidnej pracy xD na 500zl to mi się nawet nie chce
Fervi  (22:39, 24.05.17):
Oczywiście nie mówię, by porzucić stare strony, tylko po prostu dołączyć do kolejnej
Fervi  (22:34, 24.05.17):
Oczywiście drugiej pensi na tym nie zbudujecie, ale z 500zł przy solidnej pracy
Fervi  (22:30, 24.05.17):
Moje bitcoiny nie zgadzają się z tobą xD
Wojo (22:13, 24.05.17):
To nie zadziała. Macie moje słowo
I am Lord (21:45, 24.05.17):
tak i dać nrgeekowi do zrecenzowania :p
Fervi  (21:00, 24.05.17):
Mógłbyś Kacz De Klałna w big box produkować
Fervi  (20:58, 24.05.17):
I admini GMClanu tańczą dla twojej przyjemności, a tak to lipa, po ptokach
Fervi  (20:58, 24.05.17):
Dziwactwo, ale gdyby kopać to wtedy, to dziś mieszkasz na karaibach
Fervi  (20:57, 24.05.17):
No wiesz, cała informatyka to dziwactwo. Ot taki Bitcoin
Fervi  (20:57, 24.05.17):
W zależności jak cię ludzie lubią
Fervi  (20:57, 24.05.17):
Dostajesz kryptowalutę Steem / Steem Dollars
I am Lord (20:26, 24.05.17):
Fervex zawsze jakieś dziwactwo wynajdziesz
I am Lord (20:24, 24.05.17):
O co z tym chodzi?
PatrykPlayingPOLSKA (18:19, 24.05.17):
@Fervi Gdy wpisałem sobie Steem do przeglądarki i poczytałem co nieco,wtedy się zczaiłem że nie chodzi o Steama (falcepalm)
Fervi  (17:45, 24.05.17):
Brzmi jak dobry Scam, ale działa
Fervi  (17:45, 24.05.17):
Portal a'la Reddit, w którym płacą ci za treści (w skrócie)
Fervi  (17:45, 24.05.17):
@PatrykPlayingPOLSKA: Chodzi o Steem, nie Steam
Fervi  (17:45, 24.05.17):
@Wojo - i dobrze, ja sobie odkładam hajs ze Steem
PatrykPlayingPOLSKA (15:37, 24.05.17):
Wydaje mi się że GMC na już grupę na steamie,a nawet dwie.
Wojo (15:25, 24.05.17):
Ten pomysł brzmi tak rozsądnie jak instalacja linuxa
Fervi  (15:05, 24.05.17):
Może powinniśmy przejść na Steem / (niebawem) Strimi? Można zarobić, a przy okazji zrobić grupę gejclanu
nowy_user (8:50, 23.05.17):
Dzięki już działa, rzeczywiscie umknęła mi opcja erase a colour , jest idealna do mojego problemu
I am Lord (18:10, 22.05.17):
A tak w ogóle to gumce też można rozmiar zwiększyć, tylko że ona ma miękkie krawędzie
I am Lord (18:08, 22.05.17):
aha Opacity na 0 jeszcze
I am Lord (18:08, 22.05.17):
Masz tak się to robi: i.imgur.com/IDtZODf.png
I am Lord (18:02, 22.05.17):
Nie wierzę co czytam
Uzjel (16:35, 22.05.17):
Aj ludzie, problemy se robicie
gnysek (16:34, 22.05.17):
GIMP ma przeźroczyste tła. GMS 1.x ma funkcję "make opaque", a GMS2 ma różdżkę która zaznacza na raz 1 kolor wszędzie (contignous).
Ignatus (16:16, 22.05.17):
Wlasnie GM ma funkcje ktorej mi w programach graficznych brakuje (albo nie wiem jak znalezc) "Erase a color"
nowy_user (15:46, 22.05.17):
Zaznaczanie róźdżką też jest strasznie toporne. No nie wierzę że w gm sudio nie ma innego sposobu. Przecież są ludzie, którxy tworzą grafiki np. w gimpie lub paincie, i nine chce mi się wierzyć że za każdym razem usuwają białe tło piksel po pikselu. Przecież to niedorzeczne.
nowy_user (15:26, 22.05.17):
gm studio 1 ; ehhh w gm 5.3 nie bylo problemu , tlo bylo lewym dolnym rogiem
gnysek (15:22, 22.05.17):
Ktory GM tak w ogóle?
gnysek (15:22, 22.05.17):
To zaznacz różdzką
nowy_user (15:07, 22.05.17):
Niestety przy 100% przezroczystosci, farba ,maluje na czarno, a zaznaczenie + delete owszem działa ale tylko na prostokątnych powierzzchniach. Dalej nie działa to tak jak trzeba
ANtY (13:05, 22.05.17):
spróbuj zaznaczenie + delete, jak pomoglem to daj okejke
gnysek (11:11, 22.05.17):
To weź farbę i ustaw 100% przeźroczystą
nowy_user (11:06, 22.05.17):
tak tylko że gumką muszę tak prezycyjnie piksel po pikselu, a ja chce cały obszar ograniczony konturami, tak samo jak farbą w paincie
ANtY (10:51, 22.05.17):
gumką
nowy_user (10:09, 22.05.17):
hej , jak zamalować tło na przezroczyste w edytorze spritow w game maker?
I am Lord (15:38, 21.05.17):
site:gmclan.org w google
BloodDzioch (14:39, 21.05.17):
Gdzie na community jest jakaś wyszukiwarka? Za cholery nie mogę znaleźć
Adriann (10:36, 21.05.17):
To odpada, potrzebuję czegoś animowanego pomiędzy
Threef (10:29, 21.05.17):
Nie da się. Możesz wstawić [1] pomiędzy [0] a [2], ale żadnych obiektów nie wsadzisz. Ona mają depth, ale silnik chyba rysuje je osobno. Możesz za to rysować draw_background()
Adriann (22:53, 20.05.17):
Tznnnn chcę umieścić jakiś obiekt między backgrond[0] a [1]
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.01492 sekund ] [ Liczba zapytań MySQL: 15 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev