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: 5, userów: 1, ukrytych: 1
ANtY
Użytkownicy na czacie discord
doctor (11:31, 26.04.19):
Np. PHP umożliwia przerobienie JSON na tablice, tablice można sortować, mieszać (...), a w GM CHYBA trzeba użyć DSów
doctor (11:30, 26.04.19):
Ja się zdecentralizowałem, elo benc. Ciekawi mnie czemu w GM stosuje się DSy zamiast ogarnąć strukturę tablic?
Wojo (11:11, 26.04.19):
Fervi czasami był człowiekiem dalszym od rzeczywistości niż ja sam.
doctor (0:18, 26.04.19):
A no (Steem dokładniej). Trochę upada, ale parę gier jest (czy dobre ...? Tak sobie). Steem Monsters, Drug Wars czy NextColony
I am Lord (23:10, 25.04.19):
Fervi już chyba z 2 lata temu coś gadał o blockchainowym steemit
MaxGaming (21:52, 25.04.19):
Ja jak przeglądam fora biznesowe to kojarzy mi się od razu z bajką Pinki i Mózg - "Co dzisiaj robimy? - Jak to co? Budować kolejnego blockchaina!"
doctor (21:08, 25.04.19):
Kiedyś czytałem o blockchainie do robienia zdecentralizowanych baz danych, chyba kompatybilnych z SQLite
MaxGaming (18:18, 25.04.19):
Plotki mówią, że niedługo powstanie blockchain do robienia blockchainów
doctor (17:50, 25.04.19):
Nie no, już kiedyś mówiłem xD Czasem jak projekt wypali (pewnie nie) to nagle dają dużo hajsuf
Wojo (17:30, 25.04.19):
Jest 2019 rok, trudno się dziwić, że nawet na niszowym forum ktoś o tym wspomniał
MaxGaming (14:40, 25.04.19):
Kiedy nawet na gmclanie ludzie już mówią o blockchainie
doctor (14:08, 25.04.19):
hmm, nie o to mi chodziło, ale może coś wywnioskuję
doctor (14:05, 25.04.19):
No proszę, widać da się zrobić mój projekt i zintegrować z magicznym blokczejnem - dzięki
gnysek (11:34, 25.04.19):
Oczywiście, że tak. Jest przykład wysyłania i odbierania danych na stronie - gmclan.org/index.php?plik=227
doctor (11:23, 25.04.19):
Pytanie też inne - czy może się strona w PHP jakoś skomunikować z grą? Np. by grać potrzebujesz się autoryzować w PHP, który potem login ze strony przekazuje do gry?
doctor (11:20, 25.04.19):
To spróbuję, bo myslałem, że 1.4 początkowo nie miał takiej opcji, a to w sumie dużo by zmieniło ... Tylko muszę ogarnąć jak wgrać Game Makera, bo tak sobie chodzi
gnysek (0:34, 25.04.19):
Generalnie do tej samej domeny bez problemu.
gnysek (0:34, 25.04.19):
Zawsze się dało. Tylko nie do każdego serwera ale to już zabezpieczenia przeglądarek. Poczytaj o CORS.
doctor (19:42, 24.04.19):
Czy da się wysyłać HTTP Requesty (Events) z poziomu gry w GMS1.4 HTML5? Bo kiedyś się chyba nie dało ...
doctor (19:41, 24.04.19):
Moim zdaniem Game Maker poniżej Studio 2.0 są specjalnie komplikowane. Wgranie 1.4 jest wielkim problemem Elo
SimianVirus7 (20:50, 18.04.19):
ten program działa, bo odpalanie starych game makerowych gier w trybie zgodności nie zdaje egzaminu (przynajmniej u mnie)
exp (17:52, 18.04.19):
pamiętam że ktoś zrobił naprawdę dobrego tower defence na początku ligi
MaxGaming (21:21, 17.04.19):
groups.google.c...ers/w17mO9qGiD0 - możliwe, że to by komuś mogło pomóc. Resztę kodu mam tylko potrzebuję systemu który pozwoli mi rozgraniczyć sesję przeglądarki między kontrolkami webbrowser
MaxGaming (21:15, 17.04.19):
Jest ktoś w stanie napisać mi funkcje o której mówię w poście na forum(abym mógł w dwóch kontrolkach webbrowser być zalogowany na dwa różne konta na stronach WWW) za 50-150zł? Podejrzewam, że jeśli ktoś zna rozwiązanie to jest kilka linijek kodu, ale ja nie mam pojęcia już jak to ugryźć. Blokowanie ciasteczek uniemożliwia logowanie, a usuwanie ich co sesje usuwa też z innej aktywnej sesji.
I am Lord (18:50, 17.04.19):
A zobaczcie jakie gierki były robione na ligę na początku. Przecież z nich teraz by szło zrobić całkiem dobre pełnoprawne gierki, kiedyś to był gmclan
nowy_user (15:24, 17.04.19):
Z drugiej jednak strony, gdyby wspomniani GMclanowicze urodzili się 15 lat później i ich czas twórczości przypadłby na dzisiejsze czasy, to bez wątpienia zostaliby pełnoetatowymi twórcami gier i mogliby spełniać swoje marzenia. A tak to nie wiadomo co z nimi się dzieje, pewnie mają jakąś ‘normalną’, wysysającą z kreatywności i nadziei pracę.
nowy_user (15:05, 17.04.19):
To prawda, GMS nas rozpieściło. Kiedyś, gdy prawie nikt nie zarabiał na tworzeniu gier w GMie, to tworząc nowy projekt nawet nie myślałeś o $, tylko o tym, aby innym sprawić radość. Dzięki temu mieliśmy okazję zagrać w naprawdę niezłe produkcje za free, a gdyby powstały dziś to musielibyśmy za nie słono zapłacić. Mam tu na myśli np. Bruce Lee 2004 Mataska, Mario Forever Borka czy też Jump! Jump! Anacondy.
I am Lord (13:09, 17.04.19):
bo odbiera przyjemność
I am Lord (13:09, 17.04.19):
A teraz z co bym się nie zabrał to myślę z tyłu głowy jak na tym zarobić i to mi psuje wszystklo
I am Lord (13:08, 17.04.19):
Kiedyś to było, robiliśmy gry dla samej frajdy i była masa pomysłów
gnysek (10:58, 17.04.19):
na szczęście takich artystów jak BigShark i PrzeAss kojarzę.
gnysek (10:36, 17.04.19):
Liczę na Cairo 4
I am Lord (0:05, 17.04.19):
xd
I am Lord (0:05, 17.04.19):
BigShark
Wojo (16:00, 16.04.19):
Nieważne, już znalazłem
Wojo (16:00, 16.04.19):
Ja jakoś nie mogę znaleźć profilu Pietra.
Wojo (15:45, 16.04.19):
To jest na tyle bierny człowiek, że nie zakładał wcześniej konta
gnysek (15:38, 16.04.19):
mnie zastanawia kim faktycznie jesteś, bo nie nowym_userem, znasz znacznie więcej historii niż ja.
nowy_user (20:02, 15.04.19):
Chociaż Ranmus chyba wybaczył już Pieterowi(przywódcy buntu), bo zdaje się że widziałem Pietera ostatnio na GMclanie. Po wielu latach w końcu zakopali topór wojenny
nowy_user (19:57, 15.04.19):
I tak wygląd jest dużo lepszy niż u konkurencji, mam tu na myśli oczywiście GMxxl. Ich stronka chyba już nawet nie istnieje, pewnie Ranmus ma osobistą satysfakcję: swego czasu kilku prominentnych użytkowników Gmclanu nieźle napsuło mu krwi, tworząc Gmxxl'a, dokonując tym samym wielkiego rozłamu na Polskiej scenie GMa.
MaxGaming (19:34, 15.04.19):
Mi tam pasuję głównie wersja mobilna stronki. Jest świetna
gnysek (19:16, 15.04.19):
btw. kiedyś był taki podobny zielony motyw do jPortal, od Ranmy, ale niestety w odmętach internetu zaginął - niby w internecie jest wszystko, ale szczerze to 15 lat temu było więcej niż dziś
gnysek (19:15, 15.04.19):
żadne droczenie, nigdy nikt z was nic lepszego nie zaproponował, więc wiem, że każdemu pasuje
XBlacKX (15:22, 15.04.19):
też lubię ten wygląd, chciałem się podroczyć tylko
I am Lord (12:54, 15.04.19):
to jest niezła archeologia
I am Lord (12:54, 15.04.19):
Apropos Gothiczka @Wojo www.youtube.com...h?v=raudY3eVrGI
gnysek (11:34, 15.04.19):
btw. naprawiłem też wyświetlanie błędów przy wysyłaniu shoutów które... chyba nigdy przez 15 lat się nie wyświetlały, a były zaprogramowane Brakowało 2-3 linijek kodu.
gnysek (11:10, 15.04.19):
A skoro obecny działa... nie wiem czy sens go zmieniać, i tracić 300-400 godzin na pisanie zmian.
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.02001 sekund ] [ Liczba zapytań MySQL: 12 ]