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
117 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 117, userów: 0, ukrytych: 0


0 użytkownik(ów) na gmczacie i 0 bot(ów)
Shoutbox
Threef (19:32, 22.06.17):
gnysek na Ultimate, na X1 i PS4. 3 Moduły są teraz na subskrypcję
gnysek (19:16, 22.06.17):
Subskrypcja jest tylko na Ultimate, na resztę nie.
I am Lord (19:01, 22.06.17):
Vader no tutaj na głównej: i.imgur.com/SPrqXPK.png
Threef (17:42, 22.06.17):
Na razie to info że exporty na X1 i PS4 są ważne na 12 miesięcy
I am Lord (17:41, 22.06.17):
Teraz żałuję że kupiłem go :/
I am Lord (17:40, 22.06.17):
Najpierw baitują że nie będzie subskrypcji a teraz ją wprowadzają
Adriann (17:36, 22.06.17):
Cooooooooooooo?!
Threef (17:25, 22.06.17):
Przepraszam co...? GM:S2 ma mieć teraz moduły subskrypcyjnie? Na 12 miesięcy? lol
I am vader (13:39, 22.06.17):
Nie wiem jak dotrzeć do tego działu nawet
I am Lord (11:45, 22.06.17):
im vader moj jest w assorted top down
PatrykPlayingPOLSKA (10:00, 22.06.17):
Mi się wydaje że większość gości to boty ale może być też paru ludzi,trzeba jakoś zachęcić ludzi do zarejestrowania na tym forum,np można jakoś polepszyć tą polską dokumentajcę,coś do niej dodać,na steamworkshop gamemaker można jakoś popisać że jest takie ciekawe coś jak GMC,no sposobów może być wiele.
nowy_user (9:30, 22.06.17):
Chell , aktywnych userów może i dziesięciu, ale np. w tej chwili jest 133 gości! Unbelievable! Swoją drogą , ciekaw jestem dlaczego ludzie się tak ukrywają, zamiast po ludzku się zarejestrować.
Chell (22:56, 21.06.17):
niestety sprzedawanie assetow po zlotowke na ktore zbija sie po 5 osob jest malo oplacalne na forum na ktorym jest 10 aktywnych userow
nowy_user (22:52, 21.06.17):
A może powinniśmy stworzyć własny markietplace tu na gmclanie? Ja widzę same plusy: Po pierwsze - > ceny byłyby w złotówkach, więc więcej ludzi mogłoby sobie na nie pozwolić, Po drugie -> Nie wiem jak wy, ale ja wolałbym wspierać finansowo programistę od nas , ktoś kogo znam z forumowej aktywności zamiast jakiegoś anonimowego geeka z Californi lub Colorado. I po trzecie -> Zmotywowało by to nas wszystkich do twórczości.
I am vader (22:48, 21.06.17):
A który asset jest twój? Przegrzebałem showcase i top rated i nic podpisanego HuderLord nie znalazlem
I am Lord (19:06, 21.06.17):
Aha no super, nic się na głównej nic nie zmieniło pół toku już mój asset tam jest, yoygames zapomniało że ma ten MP że go nie moderują?
I am Lord (19:04, 21.06.17):
Dawno nie zaglądałem tam
nowy_user (12:47, 21.06.17):
Przepraszam , miało być Uzjel.
nowy_user (12:47, 21.06.17):
Ujzel: Właściwie jest cała masa świetnych assetów, wczoraj odkryłem marketplace i jestem pod wrażeniem co można zrobić w GMie, od razu chciałbym kupić wszystkie A tak całkiem serio to ten asset jest obłędny: marketplace.yoy...845/text-inputs Jest demo do ściągnięcia, no po prostu miodzio, bez porównania do darmowych , zbugowanych assetów
Chell (12:47, 21.06.17):
a 1 dolc a 5 ziko to, umowmy sie, nie jest az tak kolosalna roznica
Chell (12:46, 21.06.17):
user tobie to latwo bo w tych czasach warny sa tylko za bycie botem i dziecieca pornografie
Uzjel (12:42, 21.06.17):
Punkt 5 marketplace.yoy...games.com/terms
Uzjel (12:39, 21.06.17):
A jaki asset cię interesuje?
nowy_user (12:38, 21.06.17):
A z tymi zbiórkami to też chodziło mi bardziej o uczciwe rozwiązanie względem twórcy, żeby uszanować jego pracę, tzn . nie zbiórki po 20 osób na jeden asset, a raczej dwie lub 3 osoby max. Wtedy to miałoby sens imho.
nowy_user (12:35, 21.06.17):
Za free może nie, najrozsądniej byłoby zostawić wartość liczbową niezależnie od kraju natomiast zmieniać znak walutowy dla każdego kraju z osobna tzn dany extension kosztuje 19 $ dla mieszkańców USA, tym samym 19 GBP dla mieszkańców GB, 19zł dla mieszkańców Polski i 19 Juanów chińskich dla mieszkańców Państwa Środka.
Ignatus (12:29, 21.06.17):
Hmm to idąc tym tropem tacy mieszkańcy np Egipt powinni mieć wszystkie assety za free ?
nowy_user (11:35, 21.06.17):
Dlatego pora z tym skończyć, musimy tylko dostać zielone światło od góry na założenie takiego tematu, ponieważ rejestując się tutaj obiecałem sobie, że nigdy nie dostanę ani jednego warna.
Wojo (10:57, 21.06.17):
Ale po co mają sie dostosowywać do Polaków skoro Polacy dostosuja sie do innych
nowy_user (10:30, 21.06.17):
Wiesz w kwestii uczciwości to wydaje mi się, że wszystkie ceny w markecie w dolarach powinny być 4 razy tańsze dla Polaków , ponieważ dla Amerykanina 1$ to tak jak 1 zł dla Polaka. Zdaje jednak sobie sprawę z kontrowersji, i aby uniknąć warna wolę wcześniej zapytać zanim otworzę temat z propozycją zbiórki na różne extensiony.
Ignatus (10:12, 21.06.17):
Oczywiscie ze mozna, po zbiorce siana ten ktory kupil wyeksportuje asset z projektu i przesle rzeszcie ;p Uczciwe?Niekoniecznie- ale da się na pewno
nowy_user (9:45, 21.06.17):
Mam oczywiście na myśli marketplace z twórczością użytkowników GMa a nie sam sklep z głównymi produktami yoyo
nowy_user (9:02, 21.06.17):
Hej, czy można "złożyć się" w kilka osób i kupić jakąś rzecz w yoyo markecie? czy to jest dozwolone? Pytam, bo przez to, że ceny są w $, niektóre rzeczy są po prostu drogie.
Chell (22:16, 20.06.17):
prawda, rano padł mi dotyk w telefonie a aż tak mi nie zależy na alternatywnym wizerunku żeby korespondować mailami
Threef (22:11, 20.06.17):
Chell ponownie na fejsiku
Wojo (21:10, 20.06.17):
nie ma co się obijać do pracy rodacy :3 i tak aż do śmierci
nowy_user (19:21, 20.06.17):
Nie no, tak sobie czasem człowiek tylko ponarzeka, ale koniec końców jakby przyszło nam znowu korzystać z GM 5 lub GM 3 to pewnie byśmy błagali Gnyska i Ranmusa, żeby oddali nam GM:Studio
I am Lord (18:41, 20.06.17):
Gdzieś miałem GM3, chcesz : >
Chell (17:02, 20.06.17):
"Gm powyzej 7,0 to skandal" ~Wojo
nowy_user (16:56, 20.06.17):
Gnysek, najchętniej to bym cofnął wszystkie zmiany, od czasu GM 5.1 hehe, i w spokoju, gdzieś w drewnianej chatce programowałbym sobie w tym zacnym programie, co jakiś czas zerkając na równie drewniany gmclan. No ale cóż czasy bardzo szybko się zmieniły, a ja tak bardzo nie lubię zmian.
gnysek (15:45, 20.06.17):
Tak robią wszystkie nowoczesne IDE. Chcesz cofać zmiany - masz Ctrl+Z albo gita.
nowy_user (15:20, 20.06.17):
Dlaczego GMStudio robi mi autosave w momencie gdy klikam run ? W ogóle o to nie pytając?!
Chell (15:11, 20.06.17):
ja 100, generalnie zawsze bylem troche bardziej kumaty od innych
Wojo (14:30, 20.06.17):
Ja na gimbazjalnym tez mialem 98
gnysek (13:42, 20.06.17):
no, ale dalem temat w Valhalli forum.gmclan.or...showtopic=33625
nowy_user (13:39, 20.06.17):
Gratuluję, choć przyznam szczerze że ja też na maturze zdałem dość dobrze angielski ale dopiero teraz uczę się prywatnie z nativem , i widzę jak "kwadratowy" był mój język po nauce w szkole. Zalecam nie osiadanie na laurach i praktykowanie języka.
Sutikku (13:25, 20.06.17):
98% angielski gimnazjalny, elo i pozamiatane
ANtY (11:34, 20.06.17):
pozamiatane
Chell (11:13, 20.06.17):
35/40 z teorii E12, elo
nowy_user (14:17, 19.06.17):
Thank You very much indeed! Dzięki to działa!
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.00672 sekund ] [ Liczba zapytań MySQL: 14 ]

thecrims Otserv List Otserv LyricsTown Harry Potter Serwery Gier
dev nodev