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
2 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 1, userów: 1, ukrytych: 0
SimianVirus7
Użytkownicy na czacie discord
MaxGaming (13:24, 21.10.18):
kurde trzeba było przeczytać umowę licencyjną to bym uniknął kłopotów haha
Wojo (9:26, 21.10.18):
Ponoć nabiał rozpuszcza kapsaicynę, polej się mlekiem. Tak czy inaczej jest to nauczka za kasowanie stopki z woocomerce
MaxGaming (0:21, 21.10.18):
jestem cały w gazie pieprzowym jakieś pomysły?
MaxGaming (16:53, 20.10.18):
a ktoś wie na pewno? xd
exp (16:16, 20.10.18):
wydaje mi się, że nie możesz tego usunąć z racji tego, że jest darmowa
MaxGaming (13:53, 20.10.18):
zresztą precież woocomerce usuwa ze stopki jakby wpis że to wordpress
MaxGaming (13:53, 20.10.18):
to akurat nie jest takie oczywiste bo wydaję mi się że w przypadku woocomorce nie jest to zakazane
Wojo (8:45, 20.10.18):
Jak usuniesz to będziesz
MaxGaming (0:33, 20.10.18):
chodzi mi jak to z licencją jest, czy nie będę jej łamał
Wojo (22:17, 19.10.18):
zresztą, nie wiem
Wojo (22:16, 19.10.18):
tak
MaxGaming (19:21, 19.10.18):
Czy mogę usunąć w stopce "Zbudowany za pomocą Storefront i WooCommerce."?
Wojo (12:55, 19.10.18):
i cała ta dychotomia społeczeństwa wydaje się śmieszna dla osoby, która ma trochę względnego obycia w różnych środowiskach
Wojo (12:52, 19.10.18):
zresztą, zaprzestańmy tej dywagacji oraz popisu swojej erudycji
Wojo (12:51, 19.10.18):
ja w ogóle nie rozumiem tej protekcjonalnej postawy
ANtY (8:05, 19.10.18):
stalaktyzacja??
MaxGaming (0:08, 19.10.18):
exp stagmatyzacji brania narkotyków podczas zawodów mma? XD
exp (23:32, 18.10.18):
nie wiem dokładnie o czym mówicie ale stygmatyzacji brania narkotyków nie rozumiem i chyba nie zrozumiem
Sutikku (18:21, 18.10.18):
w mojej opinii też był sćpany, pozdrawiam, aż specjalnie sobie obejrzałem te gale bo tak ogólnie to mnie to nie interesowało
Wojo (19:03, 17.10.18):
mam nadzieję, że wiesz co jest pięć
Wojo (18:44, 17.10.18):
Jezu MaxGaming przeczytaj raz jeszcze co napisałem (pierwsze zdanie zaczynające się kluczowymi słowami "W MOIM PRZYPADKU"
MaxGaming (16:30, 17.10.18):
Jezu Wojo przeczytaj raz jeszcze co napisałem(punkt 3).
Wojo (13:55, 17.10.18):
Niemniej jednak wielu ludzi twierdzi w takim momencie, że coś paliłem
Wojo (13:54, 17.10.18):
W moim przypadku czerwone oczy (właściwie to lekko różowe białka) oraz opadające powieki pojawiają się najczęściej zimą gdy wchodzę z zimnego dworu do ciepłego pomieszczenia. Zresztą co ja się będę tłumaczył jak tu każdy wie swoje
MaxGaming (13:41, 17.10.18):
I 1. czerwone oczy nie są po takich środkach tylko po marihuanizacji. 2. Czerwone oczy od kamery są trochę inne niż te po paleniu. 3, Tak, marihuanizacje ciężko rozpoznać bo jest tyle opcji by mieć takie czerwone oczy. 4, nie widzę u niego ani trochę czerwonych oczu. To jeszcze odnośnie wcześniejszej wiadomości
Wojo (13:39, 17.10.18):
xD
MaxGaming (13:36, 17.10.18):
uwierzył że nie był. Pokazywałem to kilku kolegą co dużo ćwiczą i kliku co znają mefedron i jego efekty. Wszyscy to samo stwierdzili co ja.
MaxGaming (13:34, 17.10.18):
Popieram. Tak jak mówię adrenalina nie działa tak na nikogo oprócz niego. Poza tym Wojo za młody jesteś widocznie i za mało zmefedrowanowanych osób widziałeś żeby nie wiedzieć co jest pięć. Uważam że każdy kto trochę miał z tym styczność w ciągu pierwszej minuty wywiadu zorientuje się co jest pięć. Ale ogólnie Wojo od dawna zauważyłem że masz takie dzieciakie, naiwne myślenie. To nie jest sprawa która jest dla mnie jakaś istotna był naćpany to był, to nie moja
Ignatus (13:11, 17.10.18):
Obserwuję od 15 lat MMA i Adbustera od początku.Był w h*j naćpany Nikt się tak nie zachowuje nawet 10 sekund po walce
Wojo (13:02, 17.10.18):
I jak próbujecie sobie i innym wkręcać, że był naćpany to jest godne politowania (żeby nie było, nie bronię go dlatego bo jestem jego fanem, wręcz przeciwnie, irytuje mnie jego osoba)
Wojo (12:57, 17.10.18):
to dlaczego by nie zrobić specjalnej gali dla takich walk?
Wojo (12:57, 17.10.18):
Pomysłów mają dużo, lepsze to niż wpakowanie na oficjalną galę jednej walki aktora z muzykiem. I tak każdy nie będący w temacie ogląda galę dla tej jednej "popularnej" walki. Skoro w telewizji i w internecie trąbi się o wygranej muzyka z aktorem, a większość zwycięstw w tej samej gali pomija
Wojo (12:55, 17.10.18):
Uważajcie jak chcecie. Moim zdaniem taka oficjalna gala freakfightów jest dobra, zawsze coś ciekawego się dzieje. Jednemu wypada szczęka, drugi łamie nogę, trzeci chudzielec bije się z mięśniakiem, walki bliźniaków
ANtY (12:51, 17.10.18):
sorki ale nie bede tego ogladal xd
Ignatus (11:40, 17.10.18):
Obejrzyjcie wywiady ze wszystkimi uczestnikami FAMEMMA po walce, ba ,obejrzyjcie losowe kilkanaście/kilkadziesiąt wywiadów minuta po walce- NIKT NIGDY nie zachowywał się jak AdBuster- nawet oficjalny ćpun Popek .To on jeden na świecie tak reaguje na "emocje" że w niczym nie przypomina siebie na codzień?Nie ma co bronić typa-ewidnentnie się naćpał...
MaxGaming (11:37, 17.10.18):
no znam tą walkę
MaxGaming (11:36, 17.10.18):
To że oni się tak słabo przygotowują to właśnie problem. Z drugiej strony jedną rundę a nie kilka ciosów xd Poza tym mam na myśli takie nastawienie żeby wygrać z kimś zamiast pokonywać swoje słabości. To bardzo nie sportowy sposób myślenia. Jak rozróżniam jedno od drugiego? Jeśli myśli o wygranej z przeciwnikiem kombinujesz jak go przechyrzyć tak na prawdę(dowiedzieć się jakoś jaką ma stategie i treningi, a to wziąć jakąs przedtreningówkę fajną lub zaćpać, a t
Wojo (10:12, 17.10.18):
Zobacz słynną walkę pudziana z najmanem (najman przegrał jak coś), ona nie trwała długo między innymi z tego względu, że to był freakfight
Wojo (10:11, 17.10.18):
wyjaśnienia były 15 października czyli jakoś dwa dni po gali (jeśli się nie mylę), a jeśli chodzi o szybkie walki to trudno się spodziewać półgodzinnych walk jak u zawodowców. To są ludzie trenujący średnio po dwa miesiące i daleko im do zawodowego poziomu
MaxGaming (4:07, 17.10.18):
tylko dwie weszły do drugiej rundy jak dobrze pamiętam
MaxGaming (4:07, 17.10.18):
pomijam już ile trwały walki
MaxGaming (4:06, 17.10.18):
wgl nie ten state of mind zawodników
MaxGaming (4:06, 17.10.18):
dla mnie tam mało było sportu
MaxGaming (4:06, 17.10.18):
A rafon to otwarcie mówił że lubi sterydy tylko ileś tam przed walką musi przestać i po walce znowu ostro sterydy
MaxGaming (4:04, 17.10.18):
Zresztą nas to nie dotyczy to w sumie nie istotne. ale tak czy siak ja jestem w 90% pewien że coś tu mocno nie grało i stawiałbym na jakieś stymukanty/euforyki nowej generacji
MaxGaming (4:02, 17.10.18):
ja ogldałem jeszcze przed walką jakiś wywiad, nie pamiętam ile przed. Ale wysłalem znajomym że on jest na 80% naćpany. Było to widać ale nie tak mocno jak tutaj gdy doszły emocje. A mefedropodbne rcki mają ro do siebie że emocje są przetwarzane trochę inaczej i jeśi są duże to bardzo łatwo komuś kto wie co jest 5 rozpoznać czy ktoś jest porobiony czy nie nawet bez takich rzeczy jak źrenice itp
MaxGaming (4:00, 17.10.18):
można gdybać ale albo gośc ma jakieś mocne zaburzenia psychiczne albo był naćpany, nie chce mi się wierzyć że tak wygląda trzeźwy człowek Mam znajomych którzy trenują sporty walki, widziałem już ich naladowanych po wygranej czy przegranek walce gdy nimi emocje kipiały ale to zupełnie co innego. Podobnie zawodicy fame mma 2. Oprócz niego nikt nie wyglądał na naćpanego a nie jednym emocje mocno targały
MaxGaming (3:59, 17.10.18):
YT nie działa akualnie Wojo ale jeśli to ten filmik gdzie adbuster pokazuje testy zrobione tam chyba 9 czy 10 dni po to już wyjasniłem to wcześniej
MaxGaming (3:58, 17.10.18):
oglądłem najpierw całe wywiady i znim zobaczyłem tą kompilację już w pierwszej minucie wiedziałem co jest pięc
Wojo (10:48, 16.10.18):
www.youtube.com...h?v=XhmsV_IBles tutaj masz jakieś wyjaśnienia
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.
[ Polityka prywatności ]
Copyright © 2002-2018. GMCLAN.ORG
Wszelkie prawa zastrzeżone. Kopiowanie materiałów bez zgody redakcji zabronione!
© 2002-2017 Ranmus (ranmus.pl), © 2017-2018 {=|=} fable_inside();

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