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
5 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 4, userów: 1, ukrytych: 0
lenin
Użytkownicy na czacie discord
I am Lord (11:21, 18.06.18):
Predzej na cebulowym a nie normalnym
gnysek (11:18, 18.06.18):
nie no, na 4 chanie masz jeszcze porno i to czasem <18
I am Lord (11:15, 18.06.18):
To forum jest wiekszym rakiem niz 4chan
gnysek (10:55, 18.06.18):
tylko, że wszystkie 100 tematów ma tę samą odpowiedź i żadną inną
gnysek (10:55, 18.06.18):
"użyj opcji szukaj, temat wałkowany 100 razy"
Wojo (15:09, 17.06.18):
chociaz elektroda jest o wiele gorsza
Wojo (15:09, 17.06.18):
tez ma swoje głupie zasady ale nie jest jakiś zwariowany
exp (14:35, 17.06.18):
tylko gmclan jest niezastąpiony
Wojo (13:44, 17.06.18):
youtube lubię ale czasami robi głupie akcje.
Wojo (13:44, 17.06.18):
gg i fora zastąpił facebook oprogramowanie mobilne zastąpił android, video google zastąpił youtube
Wojo (13:42, 17.06.18):
Chociażby ten przykład z lombardem. Większość sklepów na allegro ma numer gg na którym odpowiada na pytania
Wojo (12:40, 17.06.18):
Właśnie vader ma rację
gnysek (12:37, 17.06.18):
GG? Chyba slack.
Wojo (9:19, 17.06.18):
Tzw. MICROsoft
Chell (9:13, 17.06.18):
z tego co pisał wojo chodzi o firmy jakichś zboczuchów
I am vader (2:19, 17.06.18):
GG jest używane w sferze biznesowej do kontaktów wewnątrz i poza firmą.
Wojo (20:53, 16.06.18):
w 2018 uzywam gg ja, kolega i jakieś zboczuchy
exp (20:45, 16.06.18):
ale czasem tu zaglądam, nawet zacząłem robić dwie gierki, ale po czasie stwierdzałem, że jednak słabe to było. ale może niedługo zacznę kolejną, bo mam pomysł
exp (20:44, 16.06.18):
chociaż o gmclan można by powiedzieć to samo xdd
exp (20:44, 16.06.18):
jakoś tak, w sumie nie wiedziałem, że ktoś jeszcze używa gg w 2018
Wojo (20:39, 16.06.18):
w ogole czemu z gg zrezygnowales? Ostatnimi dni siedzę głównie tam i dostępny jest tylko kumpel i lombard
Wojo (20:38, 16.06.18):
też jestem tego zdania exp
exp (20:38, 16.06.18):
do tego po prostu trzeba mieć odpowiednie ciało i stylówę, jak max mówił
exp (20:37, 16.06.18):
tak jak mówiłem, znaczna większość mężczyzn, zwłaszcza w naszym wieku wygląda bardzo źle z długimi włosami i jest traktowania mniej poważnie, o dziewczynach nie wspominając
exp (20:35, 16.06.18):
ja też bardzo, bardzo długo zanosiłem się, żeby ściąć włosy i było kilka podejść. ale koniec końców uważam, że to była bardzo dobra decyzja
Wojo (19:17, 16.06.18):
i nie jest to zmyślona historia
Wojo (19:13, 16.06.18):
moj kolega miał dziewczynę, która była wszędzie i u każdego (jeśli wiesz o co chodzi). Jestem przekonany,że nie była z nim dlatego, że ma dużo forsy tylko dlatego, że to poukładany typek
MaxGaming (18:47, 16.06.18):
Ja jestem tego zdania że np jak ktoś ma takie marudne podejście do życia to ja się nie denerwuje tylko co najwyżej próbuje mu pokazać że można myśleć inaczej
MaxGaming (18:46, 16.06.18):
To kwestia drobnego ogarnięcia np ścięcia włosów ale głównie tego żeby pozbyć się blokady że taki ktoś jak ja nie może mieć dziewczyny
MaxGaming (18:45, 16.06.18):
Bo prawda jest taka że wszyscy którzy chcą mieć dziewczynę a nigdy nie mieli to mają głównie problem w głowie. Na prawdę znam typów którzy wyglądają jak sto nieszczęść a mają dziewczyny wyglądające genialnie.
MaxGaming (18:44, 16.06.18):
Nie no żarty żartami ale serio nie ma co tak gadac
Wojo (18:42, 16.06.18):
Max ale pamiętaj, że trzy razy zero to wciąż zero
MaxGaming (18:35, 16.06.18):
Chell ale ja tam dopisałem że chodzi o osoby które same nie czują się dobrze ze swoich wyglądem ale jakby przez brak pewności siebie oburzają się na chęć pomocy, a nie o takich które chcą mieć w 100% świadomie długie włosy
MaxGaming (18:33, 16.06.18):
Że to była dobra decyzja
MaxGaming (18:33, 16.06.18):
I serio ja się nie dziwię vaderowi. Nie każdy jest przyzwyczajony do zmian, niektórzy się bardzo boją. Ale moja rada jest taka żeby za bardzo nie kombinować, nie podchodzić tak idealistycznie tylko ściąć jej. Jak ci się akurat ta krótka fryzura nie spodoba to do innej krótkiej będziesz nie długo czekał. Na pewno wśród osób które cię od zawsze znają w długich będziesz mógł się na początku czuć nie swojo ale jak zobaczysz że obcy ludzie zupełnie inaczej na Ciebie r
MaxGaming (18:31, 16.06.18):
No to że takie marudzenie potrafi być denerwujące okej, ale ten cala akcja z wyglądem Vadera to nie zbyt była fajna.
MaxGaming (18:29, 16.06.18):
Nie wiem może chłopaki mają jakąś większą spine o której nie wiemy no ale wygląda to źle ze strony gnyska
MaxGaming (18:29, 16.06.18):
Kiedyś jak byłem mniej pewny siebie też tak miałem. Aa bo pomyślą że jestem taki jak ta osoba(tzn jaki?) I wgl. A teraz już dawno takimi rzeczami się nie przejmuje
MaxGaming (18:28, 16.06.18):
I nie gadajcie że jest jakimś alfa. Jak ktoś nie chce się pokazywać z kimś kto wygląda na kuca to świadczy o jego braku pewności siebie. Ja teraz mam gdzieś takie coś. Jak ktoś jest spoko to dlaczego miałbym go oceniać dlatego że wygląda tak a nie inaczej
MaxGaming (18:27, 16.06.18):
No gnysek trochę nie ładnie zagrał. Mówi do niego koleżka jeszcze coś tam że chce się z nim zobaczył a on ciśnie
MaxGaming (18:26, 16.06.18):
Za to obciąłem się na patola kiedyś tak na 1 mm cała głowa
MaxGaming (18:25, 16.06.18):
Ja takich typowi długich nigdy nie miałem
MaxGaming (18:25, 16.06.18):
Ale tak poważnie jako motywację powiem że ścięcie włosów na krótko to przynajmniej 3x większe szanse na zainteresowanie sobą jakiejś kobiety. W sumie mało kto ma długie włosy i ma dziewczynę. Chyba że ma długie ale rzeczywiście jest to część jakiejś fajnej styluweczki
MaxGaming (18:24, 16.06.18):
Pomyślcie o tych laskach które tylko czekają aż zetknięcie włosy xd
exp (18:19, 16.06.18):
no i zakola skurwysyn najgorszy
exp (18:19, 16.06.18):
z kształtem głowy niestety prawda, m.in. przez to zdecydowałem się mieć trochę dłuższe włosy
exp (18:18, 16.06.18):
chociaż np. george carlin wyglądał z tym spoko nawet
Wojo (17:37, 16.06.18):
niektorzy nie potrafia sie pogodzic z tym ze lysieja wiec zapuszczaja wlosy i wyglada to komicznie
Wojo (17:36, 16.06.18):
no i zalezy tez od tego jaka kto ma linie wlosow i czy ma zakola
Wojo (17:36, 16.06.18):
typ fryzury nalezy tez dopasowac do ksztaltu glowy a to moze byc niepocieszjace dla niektorych
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.02678 sekund ] [ Liczba zapytań MySQL: 12 ]