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. 2
autor: Platyna (24.05.09)
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
130 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 126, userów: 4, ukrytych: 0
eyizuukuciqo, lew_leo, gimagiogoa, Chell

0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
ANtY (8:51, 25.07.17):
bodajze 1500 pln
Ignatus (21:53, 24.07.17):
orientuje sie ktos jaki jest koszt mini stoiska indie na PGA?
Chell (21:19, 24.07.17):
zbilbym fortune na tym twoim jednorekim bandycie
ΨΧΞ (20:56, 24.07.17):
i jak nieznosze JSa, tak uwazam, ze niestety bedzie on przyszloscia gier i apek mobilnych :<
ΨΧΞ (20:56, 24.07.17):
a ja pochwale sie zrobieniem przykladowej gry w jednorekiego bandyte w 3 dni w JavaScriptcie od zera - silnik powstal wraz z gra github.com/Psic...slots-in-3-days
tramur (12:28, 24.07.17):
Powiedziałem z niską barierą wejścia, bo stworzenie shoot em upa jest troszke trudniejsze niż w GM'ie na kodach, a co do optymalizacji to nie wiem co masz na myśli.
tramur (12:26, 24.07.17):
;P powiedzoałem
Threef (6:02, 24.07.17):
Nie ma niskiego poziomu wejścia. I wymaga masy optymalizacji
tramur (21:33, 23.07.17):
Ja bym optował za czymś zgoła odwrotnym: PICO-8. Ciekawy koncept mitycznej retro konsolki z niską barierą wejścia, ale jak najbardziej z programowaniem.
Ignatus (17:13, 23.07.17):
Raczej nie
exp (16:21, 23.07.17):
a klocki w game makerze traktujecie jako programowanie?
Fervi  (11:29, 23.07.17):
Jasne, że najlepiej jest nauczyć się ich języka itd. Natomiast coś na kształt uproszczonego Dooma (powiedzmy - w skrócie) można zrobić (teoretycznie) bez żadnej linijki kodu dodatkowej. Bardziej to nie tyle Game Maker typowy co edytor map z językiem programowania
Danielus (10:37, 23.07.17):
Prawda ale chodzi raczej o coś innego. Chodzi o prostotę, im coś prościej zrobić tym łatwiej estymować pracę i tym łatwiej to potem utrzymać. Dlatego firmy ciągnie do języków takie jak C# czy Java. Pamiętaj że to tylko narzędzia i zawsze trzeba wybierać odpowiednie narzędzia jeśli możesz zrobić coś w rok w c# to wybierasz c# niż 5 lat w C nawet kosztem 50% spadku wydajności. Chyba że wydajność jest punktem krytycznym projektu.
Wojo (10:22, 23.07.17):
Aż mnie krew zalewa ale to jest nowe pokolenie programistów - idiotów
Wojo (10:22, 23.07.17):
Czytałem blog jakiegoś barana, który pisał, że C# pomimo, że jest mało wydajny to i tak warto się go uczyć bo teraz RAM bez problemu można dokupić
Wojo (10:21, 23.07.17):
No mniej więcej o to mi chodziło. O uproszczenie, co wiąże się z tym, że ludzie nawet nie myślą o optymalizacji
Danielus (10:19, 23.07.17):
W sensie mam na myśli że na początku taki człowiek dostaje gotowce i jest zadowolny a potem mówi "a mam pomysł żeby tu była taka mechanika" i nagle ludzie się uśmiechają "a to sobie napisz bo na to nie ma gotowca" no i projekt upadł.
Danielus (10:17, 23.07.17):
Zawsze wolałem 2d, jakoś przyjemniej się gra i trochę mi szkoda że nie ma już tak potężnych produkcji 2d jak np homm3 ale cuż :f Programować nadal musisz umieć, zmienia się zakres tego co trzeba umieć bo języki się uproszczają i powstają języki vizualne ale ja to wciąż będę nazywał porgoramowaniem bo wymaga takiego samego myślenia jak zwykłe programowanie. Natomiast ludzi przychodzą robić gry myśląc że to ot tak zrobią i potem płacz że miało być bez programowania
Wojo (10:14, 23.07.17):
No bo 3D to skok technologiczny i daje większe możliwości, a miłośników 2D jest znacznie mniej
Ignatus (10:12, 23.07.17):
Nie wiem co ludzie widzą w tym żę coś jest 3D, jak jest słaby pomysł i mechanika to jeden pies jaki masz widok.Wszyscy amatorzy zakładają że 3D od razu daje grze 3punkty do oceny
Wojo (10:06, 23.07.17):
Na tym forum żaden z działów poza GM się nie sprawdza. Hmmm ciekawe dlaczego
Wojo (10:05, 23.07.17):
A jeśli chodzi o tego sandbox game maker to równie dobrze można dodać dział "GAME MAKER 3D" bo program i tak reprezentuje trochę niższy poziom
Wojo (10:01, 23.07.17):
Ale w dzisiejszych czasach serio się nie musisz znać na programowaniu ( a przynajmniej tak bardzo jak kiedyś ).
Danielus (9:49, 23.07.17):
:Nie trzeba znać się na programowaniu" najbardziej idiotyczna fraza jaka pojawiła się w naszym środowisku. Jak nie trzeba programować to znacyz że nie zrobisz nic innego jak klony istniejących rzeczy.
Fervi  (1:39, 23.07.17):
Może admin niech się zastanowi nad dodaniem subforum "Sandbox Game Maker". To taki Game Maker, który napierdziela gry w 3D i nie trzeba znać się na programowaniu (chyba, że coś lepszego chcemy) - jak w GMie xd
MaxGaming (19:00, 22.07.17):
Na AM i nie automatycznie bo trzeba do jakiegoś urzędu zamienić ale nie wiem dokładnie
Wojo (18:13, 22.07.17):
A to nie jest tak, że karta motorowerowa automatycznie zamienia się w a1 ?
MaxGaming (17:41, 22.07.17):
Ja mam A1, a właściwie jeszcze nie mam bo muszę praktykę zdać. Zaczałem jakoś dwa lata temu i nigdy nie skończyłem to doszedłem do wniosku że kiedyś trzeba(chociaż gdybym teraz zaczął mógłbym a2 nie a1) xD
Wojo (15:25, 22.07.17):
A tak na poważnie chciałem sobie kupić 125ke ale niedawno zauważyłem, że trzeba mieć B 3 lata a nie 2 tak jak myślałem :/
Wojo (15:21, 22.07.17):
hehe lewa w górę
MaxGaming (15:14, 22.07.17):
Motor masz pod maska w samochodzie
MaxGaming (15:14, 22.07.17):
Motocykl*
Wojo (11:35, 22.07.17):
Motor
ANtY (10:59, 22.07.17):
co to cbrka
MaxGaming (2:38, 22.07.17):
Po prostu nigdy nie sprawdzajcie vmaxa gdy jest po deszczu a za 200 metrów jest zakręt 90 stopni xd
MaxGaming (2:37, 22.07.17):
Za 5000zł bym nie zaszalał jeżeli chodzi o muscle cara xd
Chell (2:36, 22.07.17):
wniosek trzeba bylo kupic muscle cara
MaxGaming (2:35, 22.07.17):
Wniosek? Nie opłaca się wychodzić z domu XD
MaxGaming (2:35, 22.07.17):
Kupiłem CBRkę i pierwszego dnia ją rozbiłem <facepalm> Koszt naprawy jakieś 2000zł(a kupiłem za 5000zł) XDDDD
I am vader (23:26, 21.07.17):
Kodze projegd
Wojo (21:42, 21.07.17):
a siedze se w domu jak zawsze i podróżnikowałem sobie po mieście wcześniej i generalnie jestem nawet zadowolony
Ignatus (20:53, 21.07.17):
Słyszałem że taka gorzka czekolada
Threef (20:47, 21.07.17):
A nie piłem. Jak ta jelitówka smakuje? Lepsza od wiśniówki?
Chell (19:52, 21.07.17):
siedze w chacie z jelitowka, elo
Nikas (19:47, 21.07.17):
alkololo
ANtY (18:41, 21.07.17):
PRZYZNAWAĆ SIĘ, NIC NIE UKRYWAĆ
ANtY (18:41, 21.07.17):
NO ELO CO TAM
Wojo (5:23, 20.07.17):
O dzięki, doceniam starania
Danieo (0:13, 20.07.17):
Wszystkiego najlepszego!
Gibki Kaktus (21:02, 19.07.17):
Btw zalogowałem się specjalnie, żeby Ci życzenia złożyć xD
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.0068 sekund ] [ Liczba zapytań MySQL: 14 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev