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)
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
1 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 0, ukrytych: 0
Użytkownicy na czacie discord
I am Lord (22:51, 24.11.17):
Byłem kucem ale teraz jestem skrytym kucem
Wojo (22:38, 24.11.17):
Jak coś to nie do ciebie Huder
Wojo (22:37, 24.11.17):
Od kiedy polityka znów pojawiła się na gmclanie? Myślałem, że zbuntowane polityczne kuce już wyginęły P
I am Lord (22:07, 24.11.17):
Wyczuwam z tego doskonałe memy z "deal with it" www.pudelek.pl/...tlas_kotow_foto
hgter (1:05, 24.11.17):
Już sobie na wszelki wypadek przeniosłem jedną do steama taką razem z androidem. Ale wiele modułów, których licencje mam na mailu nie ma klucza steamowego. No nic pewnie przy formacie po prostu wezmę licencję yoyo z maila. Chyba, że to wyłączą. Ale nie spodziewam się. Nikt by im po czymś takim z 2.0 nie zaufał.
Ignatus (11:32, 23.11.17):
Chyba jedyna opcja przy formacie kompa to wersja steam?
gnysek (11:07, 23.11.17):
O kurde, zlikwidowali to... no to nie wiem, pewnie przyznaje każdą którą znajdzie
gnysek (11:03, 23.11.17):
licencje wybierasz chyba na stronie YYG
hgter (23:35, 22.11.17):
gnysek: Ok, dzięki. Tylko to ma zastosowanie też do 1.4? Bo ja mam kilka licencji z różnymi podpiętymi modułami. Ciekawe jak wybiera odpowiednią. No nic w razie czego mam spis na maila. Dopóki nie wyłączą serwerów powinno być ok.
PsichiX (21:53, 22.11.17):
imprezy firmowe w srode to nie jest trzezwy pomysl xD
gnysek (9:50, 22.11.17):
a jak coś dokupisz, to musisz raz jeszcze wpisać login i hasło w menu help > upgrade i zrobić restart
gnysek (9:50, 22.11.17):
teraz chyba tylko mejla podajesz i hasło, nie ma kodów
hgter (16:47, 21.11.17):
W PRODUCTS da się przełączyć na 1.4, alr tam jest spis wszystkiego co kupiłem, ale bez kodów. Jak się dobrać do kodów? Kiedyś było chyba coś takiego jako Recovery i na maila słali, ale tego też nie mogę znaleźć.
hgter (16:36, 21.11.17):
Chciałem sprawdzić jak to było z tym linuxe i zalogowałem się na moje konto w yoyo. Gdzie teraz są tam numery licencji? Bo szukam i szukam i nigdzie nie ma podsumowania ze spisem posiadanych modułów wraz z kodami. Kiedyś była ładna tabelka.
TO_mek (14:20, 21.11.17):
GMS 1.4 ma eksport do linuxa?
gnysek (12:38, 21.11.17):
W sumie powinienem napisać że słaba.
gnysek (10:51, 21.11.17):
Pełną + moduł. Dlatego napisałem, że oferta średnia.
hgter (0:56, 21.11.17):
Odnosząc się do ogłoszenie gnyska o subscypcji za $39: Tylko jak w tej wersji w "subskrypcji" można rozwiązać moduł na androida? Da się coś taniej? Muszę kupić moduł za 1450 zł? Czy też w tej wersji nie da się z niego skorzystać i muszę kupić pełną+moduł czyli dać 1800 zł?
PsichiX (17:42, 20.11.17):
mieli DLC pod tytulem "kompilacja do kodu natywnego", a biedaki cebulaki meczyc sie z powolnym gmlem xD
Wojo (16:09, 20.11.17):
może jeszcze dlc przyspieszające ładowanie gier?
Wojo (16:08, 20.11.17):
hahaha ten news o nowym gmie pokazuje jak jego poziom upadł na ryj
gnysek (9:37, 20.11.17):
Po prostu każdy sterownik inaczej interpretuje polecenia rysowania linii z directx i ogólnie nikt tego już nie używa w profesjonalnych grach.
gnysek (9:36, 20.11.17):
To nie wina gma tylko kart graficznych. I chyba nawet w dokumentacji jest to opisane czemu tak działa i że własnie lepiej rysować sprite.
hgter (21:40, 19.11.17):
Miałem napisać długi post o skopaniu draw_line w Gm. Ale to nie ma sensu (cyrki jakie w tym wychodzą są nieziemskie). Draw_line nie działa w Gm (działało nawet kurde qbasicu pod dosem) a już pod androidem to co się wyprawia to jakaś paranoja. Jak musisz mieć linię w swoim projekcie to narysuj ją sobie jako sprite.
Adriann (19:29, 19.11.17):
Hi hi
Saus (14:15, 18.11.17):
Siema śmieszki
hgter (10:42, 17.11.17):
Pozmieniałem wszystko na pliki i mam nadzieję, że będzie ok
hgter (10:41, 17.11.17):
Coś chyba nie jest do końca tak z dodawaniem grafik do postów. Wczoraj w nocy dodawałem screeny z gry przez linkowanie (zmieniałem ich wielkość przy pomocy narzędzi edycji w poście). Było wszystko ok, ale teraz jak zajrzałem to screeny wyparowały i tylko linki zostały. Natomiast jeden screen dodany jako plik był ok.
I am Lord (20:02, 16.11.17):
scroll byłby pokrętłem, może to wyglądać spoko
I am Lord (20:01, 16.11.17):
A zobacz w sumie bo nie sprawdzałem w jaki sposób są zrobione scrolle od myszek, tam też na pewno jest enkoder
I am Lord (20:01, 16.11.17):
ale no enkoder jednak fajniejsza sprawa bo nie ma ograniczenia obrotu
I am Lord (20:00, 16.11.17):
A na potencjometrach nie możesz?
Chell (19:13, 16.11.17):
knuje jakiś sprytny zegarek na rpi zero i tak mi zaswitalo ze takie pokrętło byłoby wygodnym inputem
I am Lord (19:08, 16.11.17):
A co konstruujesz?
I am Lord (19:08, 16.11.17):
A jak byś potrzebował liniowe enkodery to takie są np w drukarkach i skanerach
Chell (19:03, 16.11.17):
zawsze coś
I am Lord (18:59, 16.11.17):
w dodatku inkrementalne są tak jak chcesz ale wiesz jaka ich precyzja była
Chell (18:59, 16.11.17):
oo, super myśl, dzięki
I am Lord (18:58, 16.11.17):
skołuj sobie myszkę kulkową, tam są 2 takie enkodery obrotowe.
Chell (18:57, 16.11.17):
coś takiego ze starych komórek kojarzę, że jak normalny rotary encoder jest pionowy i nie da się go obracac jednym palcem tak mi chodzi o taki który jest płaski, wystaje z obudowy urządzenia tylko trochę z boku i można podkręcić
I am Lord (18:57, 16.11.17):
tzn budowa może być z tarczą wewnątrz enkodera a może być tak jak w starych kulkowych myszkach gdzie była tarcza na zewnątrz enkodera
Chell (18:55, 16.11.17):
jednak nie rysuje, lapek padl
I am Lord (18:54, 16.11.17):
no nie czaję o co ci chodzi z zatapianiem
Chell (18:54, 16.11.17):
już rysuje o co mi chodzi
I am Lord (18:53, 16.11.17):
ale to nadal liniowy tylko że się zwija
I am Lord (18:52, 16.11.17):
No to nie wiem, są jeszcze takie zwijane
Chell (18:51, 16.11.17):
bez max i min wartości w sensie
Chell (18:50, 16.11.17):
ale nie, bo wciąż zależy mi na samej czynności kręcenia, i żeby nie określał absolutnej wartości tylko inkrementowal i dekrementowal
Chell (18:50, 16.11.17):
masz refleks xD
I am Lord (18:48, 16.11.17):
encoder liniowy?
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.
Copyright © 2002-2017. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus (ranmus.pl), © 2017 {=|=} fable_inside();

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