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. 1
autor: Platyna (24.05.09)
Wstęp do teorii grafów - cz. 1

Wprowadzenie
     Witam w pierwszej części artykułu mającego na celu wprowadzenie czytelnika do zagadnienia teorii grafów. Przedstawione tu zostaną podstawowe pojęcia dotyczące grafów, trochę teorii oraz kilka przykładów ich zastosowania. Czyli w skrócie: Z czym to się je. ;)
     Na początku należy powiedzieć, co to w ogóle jest teoria grafów? Według Wikipedii, jest to dział matematyki zajmujący się badaniem własności grafów. Ale w takim razie czym jest graf? W dużym uproszczeniu, jest to zbiór wierzchołków oraz łączących je krawędzi. Bardziej formalnie jest to pewna struktura danych, czyli sposób uporządkowania informacji w komputerze. Rysunek 1 przedstawia przykładowy spójny graf. Ma on 7 wierzchołków i 8 krawędzi.


Podstawowe pojęcia dotyczące grafów
     Wiem, że nikt nie lubi masy teorii no ale niestety trzeba się z tym zapoznać. Na szczęście nie będzie tu żadnych pogiętych, wymyślnych nazw tylko bardzo intuicyjne pojęcia. :)

Rodzaje grafów:
Graf spójny - jest to graf w którym poruszając się po krawędziach możemy znaleźć ścieżkę między dowolną parą wierzchołków.
Graf pełny - jest to taki graf w którym każda para wierzchołków jest połączona pojedynczą krawędzią.
Graf acykliczny - jest to graf w którym nie występują żadne cykle, tj. nie mamy żadnej możliwości chodzenia w kółko. :)
Graf skierowany - rodzaj grafu w którym każda krawędź ma swój określony kierunek w którym możemy się po niej poruszać. Przykładowo, jeśli krawędź prowadzi od wierzchołka 2 do wierzchołka 4 to nie możemy jej wykorzystać do podróży z wierzchołka 4 do 2. ;)

Mam nadzieję, że nie muszę wyjaśniać takich pojęć jak graf niespójny, graf cykliczny czy graf nieskierowany. Liczę na waszą wrodzoną inteligencję ;)
Istnieje jeszcze wiele rodzajów grafów jednak nie będę tu ich wszystkich wyjaśniał. Wymieniłem te najważniejsze.

Inne pojęcia:
Cykl - Już przy definicji grafu acyklicznego powiedziałem czym jest cykl, jednak tutaj podam bardziej sztywną definicję. Cykl to droga zamknięta, czyli taka której pierwszy wierzchołek jest jednocześnie ostatnim. Na grafie z rysunku 1 możemy odnaleźć dwa rozłączne cykle.
Waga krawędzi - Krawędziom grafu możemy przypisywać różne wagi. Jest to jakby koszt podróży tą krawędzią.
Stopień wierzchołka - Jest to liczba krawędzi sąsiadujących z wierzchołkiem. W grafach skierowanych możemy wyróżnić stopień wchodzący i wychodzący czyli odpowiednio liczbę krawędzi prowadzących do i wierzchołka z niego wychodzących.
Sąsiad wierzchołka - Jest to wierzchołek połączony z danym wierzchołkiem pojedynczą krawędzią.

Przykłady zastosowania grafów
     No dobrze, wszystko pięknie, ale po co nam to? Rozważmy następujący problem: Jaś wraca ze szkoły. Jest bardzo zmęczony po ciężkim dniu i chciałby jak najszybciej położyć się w wygodnym łóżku. Chciałby więc dowiedzieć się jaka jest najkrótsza droga ze szkoły do domu prowadząca jedynie po wyznaczonych ścieżkach. Możemy mu powiedzieć, żeby nie marudził i zdrzemną się na jakimś kamieniu, albo możemy przedstawić ten problem w postaci grafu i w ten sposób pomóc Jasiowi w znalezieniu najkrótszej drogi do domu. ;)
     Gdybyśmy wszystkie skrzyżowania dróg w miasteczku Jasia potraktowali jako jakieś punkty, natomiast drogi jako krawędzie wychodzące z tych punktów, o wagach równych długości odpowiadających im dróg, uzyskali byśmy graf przedstawiający system dróg w miasteczku. Istnieje tzw. algorytm Dijkstry znajdujący najkrótszą drogę od dowolnego wierzchołka do wszystkich pozostałych.
     No, ale co nas obchodzi jakiś Jaś i jego problemy? Jakie korzyści nam dostarczają grafy? Otóż okazuje się, że algorytmy oparte na grafach znajdują wiele praktycznych zastosowań. Przykładowo, możliwość szybkiego wyliczenia najkrótszej drogi przez komputer jest zastosowana w samochodowych GPSach. Wiem, że większość osób czytających ten artykuł to amatorzy programowania gier. Również w tej dziedzinie grafy są nam niezwykle pomocne. Wyobraźmy sobie, że piszemy sztuczną inteligencję postaci sterowanej przez komputer i chcemy by postać ta była w stanie odnaleźć najkrótszą drogę między jakimiś punktami nie wpadając po drodze na ściany, czy inne przeszkody. Wystarczy w odpowiedni sposób przedstawić mapę gry jako graf. Analogicznie możemy zaprogramować inteligentny pocisk omijający przeszkody, albo komputerowego przeciwnika w jakiejś samochodówce.

I to by było na tyle...
     ...w tej części artykułu. Być może trochę cię zanudziłem, ale wydaje mi się, że to była ta nudniejsza część. Dalej będzie ciekawiej. W następnych częściach opiszę sposoby reprezentacji grafów w programowaniu, oraz kilka podstawowych algorytmów operujących na grafach. Czyli trochę więcej praktyki (oczywiście teorii też nie zabraknie). ;)


Przejdź do następnej części
głosów: 4 | ocena: 7.75 oceń zasób | dodał: Platyna
Komentarze
stron: 1

1


av

propaganja (14:25, 4.06.2009)

kim był dijkstra?

stron: 1

1



Dodaj komentarz:
Treść:
Menu
Panel użytkownika
Jesteś niezalogowany!

Nie masz konta? Zarejestruj się
Użytkownicy on-line
4 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 4, userów: 0, ukrytych: 0
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.01469 sekund ] [ Liczba zapytań MySQL: 13 ]