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. 2
autor: Platyna (24.05.09) | czas czytania: 6 minut, 50 sekund
Wstęp do teorii grafów - cz. 2

Sposoby reprezentacji grafów
     Człowiekowi najłatwiej wyobrazić sobie graf jako rysunek na którym punktami oznaczamy wierzchołki, a odcinkami (lub strzałkami) krawędzie grafu. W przypadku komputera jest trochę trudniej. Nie zrozumie, jeśli mu pokażemy nasze bazgroły. ;) W tej części artykułu omówione zostaną dwa najczęściej spotykane sposoby reprezentacji grafów w programowaniu. Przedstawione zostaną ich wady, zalety, możliwości jakie nam dają a także różne sposoby implementacji.
     UWAGA W zrozumieniu poniższych treści przydatne może okazać się zaznajomienie z podstawowymi strukturami danych (listy, kolejki, stosy itp.).
Miłej lektury :)

Macierz sąsiedztwa
     Jest to chyba najbardziej intuicyjny sposób przetrzymywania grafu. Polega on na utworzeniu macierzy o liczbie kolumn i wierszy równej liczbie wierzchołków grafu. Macierz jest czymś w rodzaju prostokątnej tabeli danych o określonej liczbie wierszy i kolumn. W komórce na pozycji (i,j) (gdzie i to numer wiersza, a j numer kolumny) będziemy przechowywali wartość 1 jeżeli istnieje krawędź prowadząca od wierzchołka i do wierzchołka j lub wartość 0 jeżeli taka krawędź nie istnieje. W przypadku grafów ważonych z krawędziami o określonych wagach zamiast 1 będziemy przechowywali wagę krawędzi. Myślę, że najlepiej będzie jeśli pokażę jakiś przykład. Rysunek 2 przedstawia spójny graf skierowany oraz odpowiadającą mu macierz sąsiedztwa.

     Może teraz coś o wadach i zaletach takiej reprezentacji grafów. Największą wadą takiego rozwiązania jest jego złożoność pamięciowa. Gdy byśmy chcieli w taki sposób przechowywać graf o bardzo dużej ilości wierzchołków, np. 100.000 musieli byśmy utworzyć macierz posiadającą 10.000.000.000 komórek, a tego nie wytrzymał by żaden komputer. No, a jakie korzyści nam daje macierz sąsiedztwa? Przede wszystkim możemy w prosty sposób, w czasie stałym sprawdzić czy dane dwa wierzchołki są połączone krawędzią. W tym celu wystarczy sprawdzić zawartość jednej komórki macierzy. W równie prosty sposób możemy usunąć lub dodać nową krawędź do grafu zmieniając w tym celu jedną wartość. Niestety gorzej ma się sprawa z wyszukaniem wszystkich sąsiadów danego wierzchołka. Aby odnaleźć wszystkie wierzchołki połączone z wierzchołkiem i musimy przeszukać cały wiersz i macierzy w poszukiwaniu jedynek.
     Taka reprezentacja grafu ma jeszcze jedną wadę. Rozważmy sytuację w której od pewnego wierzchołka i do wierzchołka j prowadzi więcej niż jedna krawędź. W takim wypadku w odpowiedniej komórce zamiast wartości 1 mogli byśmy przechowywać liczbę krawędzi łączących wierzchołki i i j. Gorzej sytuacja się ma jeśli wszystkim takim krawędziom przypisane są różne wagi. Na szczęście z takimi grafami nie mamy często do czynienia.

Implementacja
     Tutaj nie ma specjalnie o czym opowiadać. Znam tylko jeden sposób implementacji macierzy sąsiedztwa i jest on bardzo prosty. Polega na utworzeniu dwuwymiarowej tablicy o obu wymiarach równych liczbie wierzchołków. Tablica ta będzie odpowiadała naszej macierzy.

Listy sąsiedztwa
     Drugą często spotykaną reprezentacją grafu są tzw. listy sąsiedztwa. Polega ona na tym, że dla każdego wierzchołka tworzymy listę jego sąsiadów (czyli wierzchołków połączonych z nim pojedynczą krawędzią). Zwykle złożoność pamięciowa takiego rozwiązania jest znacznie lepsza niż w przypadku macierzy. Dla każdego wierzchołka tworzymy tyle zmiennych ile ma on sąsiadów, a więc tyle ile istnieje krawędzi odchodzących od niego. Tak więc całkowita złożoność pamięciowa tej reprezentacji jest proporcjonalna do liczby krawędzi grafu. No, ale niestety zdarzają się przypadki w których rozwiązanie to będzie równie pamięciożerne co macierz sąsiedztwa . Rozważmy taką reprezentację dla grafu pełnego skierowanego. Będzie miał on (n*(n-1)) krawędzi, a więc będzie wymagał od nas utworzenia właśnie tylu zmiennych. Na szczęście w praktyce rzadko mamy do czynienia z takimi grafami. Rysunek 3 przestawia przykładowy niespójny graf oraz odpowiadające mu listy sąsiedztwa.

     A na co nam pozwala takie rozwiązanie? Przede wszystkim możemy w prosty sposób uzyskać informacje o wszystkich sąsiadach danego wierzchołka. Jest to bardzo użyteczne przy implementowaniu wielu algorytmów grafowych. Przy odpowiedniej implementacji również dodanie krawędzi jest niezwykle proste, gdyż sprowadza się jedynie do dodania nowego wierzchołka do odpowiedniej listy. Niestety coś za coś. Gorzej sprawa się ma jeśli chcemy sprawdzić czy istnieje krawędź prowadząca od wierzchołka i do j. W tym celu musimy przeszukać całą listę sąsiadów wierzchołka i by sprawdzić czy występuje na niej wierzchołek j. Podobnie wygląda usuwanie krawędzi. Należy odnaleźć odpowiedni wierzchołek na liście i go stamtąd usunąć.

Implementacja
     Wymienione wcześniej wady i zalety list sąsiedztwa są w dużym stopniu zależne od sposobu implementacji i zastosowanej struktury danych. Postaram się przybliżyć wam dwa najpopularniejsze sposoby.

Sposób 1 - Tablica wskaźników
     Jest to zdecydowanie najgorsza metoda, jednak należy się z nią zapoznać. Polega na utworzeniu pewnej tablicy (lub vectora) o rozmiarze równym ilości wszystkich krawędzi. Nazwijmy ją A. W kolejnych pierwszych komórkach przechowywać będziemy sąsiadów wierzchołka numer 1. Następne komórki będą przechowywać sąsiadów wierzchołka 2, itd. Uzyskamy w ten sposób listę sąsiadów wszystkich wierzchołków. Jednak skąd będziemy wiedzieć w którym miejscu kończą się sąsiedzi jedynki, a zaczynają się sąsiedzi dwójki? Jest na to prosty sposób. Należy utworzyć drugą tablicę (nazwijmy ją W), która dla każdego wierzchołka będzie przechowywała informację o tym, w którym miejscu tablicy A zaczynają się jego sąsiedzi. Kończyć oczywiście będą się w miejscu wskazywanym przez następną komórkę tablicy W. Rysunek 4 przedstawia przykładowy graf oraz odpowiadające mu zawartości tablic A i W. Podstawową wadą takiego rozwiązania jest fakt, że gdybyśmy chcieli usunąć jakąś krawędź musieli byśmy przesunąć wszystkie następujące po niej wartości tablicy A o jedną komórkę w lewo oraz zmienić wartości wskaźników. Podobnie sprawa się ma z dodawaniem krawędzi.


Sposób 2 - Lista jednokierunkowa
     Sposób ten polega na utworzeniu dla każdego wierzchołka listy jednokierunkowej przechowującej jego sąsiadów. Lista taka to pewna struktura danych, która pozwala na na przyspieszenie pewnych operacji. Przykładowo: możemy usunąć dowolny element ze środka listy bez potrzeby przestawiania wszystkich jego następników. Przypominam, że jest to właśnie to co sprawiało, że poprzednia omówiona implementacja nie była zbyt dobra. Nie będę tłumaczył tutaj jak to dokładnie działa, gdyż wymagało by to szczegółowego omówienia list. Zachęcam jednak do przejrzenia innych źródeł i zapoznania się z tą strukturą danych.

I to by było na tyle...
     ...w tej części artykułu. W następnej części omówione zostaną dwa podstawowe algorytmy operujące na grafach: DFS i BFS. :)


Przejdź do następnej części
głosów: 5 | ocena: 8.19 oceń zasób | dodał: Platyna
Komentarze
Dodaj komentarz:
Treść:
Menu
Panel użytkownika
Jesteś niezalogowany!

Nie masz konta? Zarejestruj się
Użytkownicy on-line
7 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 6, userów: 1, ukrytych: 0
ANtY
Użytkownicy na czacie discord
gnysek (13:58, 18.02.19):
bo tam są głównie XMLe, wiec kazdy edytor do www się nada
gnysek (13:58, 18.02.19):
ja otwierałem w phpstormie i robiłem replace
nowy_user (13:45, 18.02.19):
BTW. Na forum YoYo coraz większe naciski ze strony użytkowników. Podoba mi się to, że użytkownicy wywierają presję na Yoyo, aby produkt i forum dalej się rozwijały. Nie podoba mi się natomiast to, że Yoyo samo nie wychodzi z inicjatywą :/
nowy_user (13:44, 18.02.19):
Dzięki za info, postaram się jeszcze pokombinować z GMEdit , może tam będzie ta opcja.
gnysek (13:28, 18.02.19):
a faktycznie, nie ma globalnego replace, to w GMS2 tylko, trzeba robić globalny find i ręcznie zmieniać
nowy_user (10:30, 18.02.19):
Niestety, w edit jest opcja Find a resource (Ctrl+R) ale to pozwala wyszukiwać np. całe obiekty sprity itd. Nie do końca mi o to chodziło. To, co ja bym chciał zrobić to np. podmienić nazwę jednej zmiennej, która jest dość nieintuicyjna, a pojawia się bardzo często, i jest porozsiewana po różnych obiektach i skryptach. Chciałbym móc podmienić nazwę tej zmiennej we wszystkich miejscach, za jednym zamachem...
gnysek (10:05, 18.02.19):
wejdź do menu "Edit" i tam chyba będzie, wraz ze skrótem.
nowy_user (9:24, 18.02.19):
Panowie, prosta sprawa, nie wiem czy czegoś nie widzę przez jakieś chwilowe zaćmienie umysłu, ale gdzie w GM1.4 jest opcja globalna 'search and replace' ? Lokalnie, dla danego obiektu pojawia sie po wciśnięciu ctrl+F , natomiast globalnie, jak wcisnę ctrl+shit+F to pojawia się sama wyszukiwarka, bez opcji replace... Chciałem zmienić nazwę jednej zmiennej, chyba nie będę musiał tego robić ręcznie?
Konrad-GM (0:12, 18.02.19):
Yup, dokładnie tak powinno chodzić, potem jest trochę więcej różnorodnych pułapek, więc robi się coraz trudniejsze
I am Lord (0:06, 18.02.19):
ale aż tak? www.youtube.com...eature=youtu.be
Konrad-GM (23:58, 17.02.19):
Ten kurczak szybko chodzi, więc to ficzer jest, żeby za łatwo nie dało się przejść gry
I am Lord (23:52, 17.02.19):
ok teraz 8, ale nie wiem czy u mnie czasem nie za szybko chodzi ten kurczak
I am Lord (23:50, 17.02.19):
5 jajaec zdobyłem
I am Lord (23:46, 17.02.19):
12 minut zostało a nie mam game playu jeszcze tylko sama grafika
I am Lord (23:46, 17.02.19):
ja nie zdąrze
Konrad-GM (23:41, 17.02.19):
Dodałem grę na ligę, ale zczaiłem się dopiero teraz, że czarny kolor to przecież też kolor kek, nie bijcie
gnysek (10:35, 15.02.19):
jak jeszcze gdzieś zostały, dawajcie znać
I am Lord (17:40, 14.02.19):
to się nie sprawdzi przy takiej małej ilości osób. Żadne posty się nie gubią tutaj w tłumie żeby je wyróżniać
I am Lord (17:40, 14.02.19):
wyłącz te oceny
gnysek (10:29, 14.02.19):
jeszcze wieczorem zajrzę w kod, jak nie znajdę żadnej opcji to wyłączę ocenianie w tych działach i tyle, i tak mało kto tego potrzebuje, to nie stackoverflow
gnysek (0:46, 14.02.19):
musiałbym chyba wyłączyć oceny
nowy_user (20:43, 13.02.19):
To prawda, jest to irytujące.
I am Lord (20:11, 13.02.19):
da się wymusić żeby to cholerne sortowanie po ocenie postu nie było domyślne? Straszliwie mnie wnerwia
gnysek (11:50, 13.02.19):
tzn. wcześniej też na forach się sporo działo, ale nie miałem internetu to nie widziałem
gnysek (11:49, 13.02.19):
Pamiętam, lata 2003-2008 to chyba takie najbujniejsze. Aż weszły facebooki i smartfony.
Temporal (17:18, 12.02.19):
jestem człowiekiem starej daty i żyje czasami, gdy wszystko działo się na forach internetowych
Temporal (17:17, 12.02.19):
wiem co to Discord, tak tylko głupoty wypisuje
I am Lord (17:12, 12.02.19):
discord to chat a nie portal społecznościowy
I am Lord (17:05, 12.02.19):
bo rozmowy się toczą na discordzie tylko
Temporal (16:51, 12.02.19):
boję się Discordów, Facebooków i Instagramów
SimianVirus7 (22:59, 11.02.19):
tu zwykle jest cicho z tego co wiem na discordzie więcej się dzieje
nowy_user (15:37, 11.02.19):
Wszyscy piszą gry, nik nie ma czasu na pogawędki
Temporal (15:33, 11.02.19):
co tu tak cicho?
nowy_user (17:20, 9.02.19):
Morał z tych historii: Róbcie backupy
Temporal (15:39, 9.02.19):
brzmi jak dobra copypasta
Konrad-GM (14:59, 9.02.19):
Kiedyś robiłem grę w Unity, crash co chwila, a potem ostatni crash usunął mi sporą część assetów w jakiś dziwny sposób, że nie mogłem odzyskać większości kodu czy modeli a kopia mocno była nieaktualna, usunąłem Unity i od tamtej pory nigdy nie wróciłem xD
I am Lord (13:52, 9.02.19):
miałem strzelankę topdown z generowanymi jaskiniami w planach
I am Lord (13:51, 9.02.19):
Ja nie oddałem na ligę bo mi crash GMS2 zepsuł projekt i się wkurzylem. Odinstalowałem go
Temporal (10:13, 9.02.19):
kiedy ten GM mi się znudzi? cały czas jestem pod wrażeniem jak dobry jest ten soft. Oczywiście ma jakieś swoje bolączki i są bardziej zaawansowane silniki, ale to wciąż doskonałe narzędzie zarówno dla początkujących twórców gier jak i zaawansowanych. Tworzenie gier w tym środowisku to sama przyjemność
gnysek (22:03, 8.02.19):
Nie wyjdzie. Jest plan na cały rok rozpisany i nie ma tam gms3. A zniżki były co roku.
nowy_user (18:22, 8.02.19):
Pojawiła się nowa promocja, Lunar Sale, nawet do 50% zniżki na GMS2 Mobile. Chyba niedługo wyjdzie GMS3, skoro co chwila nas zasypują promocjami
nowy_user (22:05, 5.02.19):
Dzięki, wyglada bardzo solidnie, chyba z niego skorzystam
gnysek (17:03, 5.02.19):
mydevil.net po tym jak hekko ceny podniosło
nowy_user (14:40, 5.02.19):
Hej, jaki niedrogi i dobry hosting polecacie do prostego landing Page’a, na którym mógłbym zaprezentować apkę zrobioną w GM? Najlepiej taki, który obsługuje WordPressa, bo bardzo do gustu przypadła mi wtyczka Elementor Page Builder
Sutikku (22:58, 4.02.19):
dziury w głowie
Sutikku (22:58, 4.02.19):
zapomniałem skończyć gierkę na lige .-.
SimianVirus7 (17:35, 4.02.19):
Myślę, że parę dobrych duszyczek by się znalazło i ufundowało nagrody. Jeśli pomysł się spodoba, ja również mogę dorzucić coś od siebie
SimianVirus7 (17:33, 4.02.19):
Można by zrobić jakiś worek gier (ale nie śmieciowych). Human: fall flat, Hollow Knight, Bioshock Inifite, Gothic Universe Edition. To wszystko dobre gry za małą cenę <20zł
Dester (17:13, 4.02.19):
nagrody na Steam na pewno były by bardzo motywujące
Dester (16:53, 4.02.19):
temat był za trudny
Ankieta
» Ile powinny trwać tury Ligi 24?
24h
48h
54h (piątek od 18:00)
7 dni
inna długość (podałem w komentarzu ankiety)

GMCLAN to serwis o programie Game Maker i nie tylko.
[ Polityka prywatności ]
Copyright © 2002-2019. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus (ranmus.pl), © 2017-2019 {=|=} fable_inside();

[ Czas generowania strony: 0.01992 sekund ] [ Liczba zapytań MySQL: 12 ]