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
10 użytkownik(ów) aktywny(ch) przez ostatnie 15 minut:
gości: 9, userów: 1, ukrytych: 0
ediepl
Użytkownicy na czacie discord
I am vader (16:08, 16.12.17):
Ja koniec koncow nie wiem czy maja sie iskrzyc czy nie.
gnysek (14:10, 15.12.17):
o maczanach ?
Wojo (13:44, 15.12.17):
Swoją drogą jeśli jesteśmy przy temacie palenia to pamięam te wywody o maczanach, które się iskrzą
Wojo (13:43, 15.12.17):
Pierwsza rzecz jaką robię po spaleniu kuchni to napisanie o tym na gmclanie
gnysek (16:06, 14.12.17):
I już zaktualizowali GMS2 ponownie z hotfixem, bo to nowe okienko w room editorze nie działało prawidłowo...
Gibki Kaktus (12:49, 14.12.17):
Zgadnijcie kto spalił kuchnię i musial się wynieść? XD
gnysek (11:33, 14.12.17):
@Wojo - ten typek dawno sprzedał ten film i teraz robi go Disney
ANtY (9:49, 14.12.17):
szanuje
Chell (17:15, 13.12.17):
wysoka piątka
I am Lord (17:15, 13.12.17):
Nie oglądałem ani jednej części SW i jestem z tego dumny
Wojo (13:23, 13.12.17):
z resztą typek jest na tyle smutny ze musi wypuszczac co jakis czas nowa czesc swojego filmu bo nie potrafił zrobić jednego porządnego filmu
Wojo (13:22, 13.12.17):
nigdy nie ogladalem gwiezdnych wojen i jakos mnie do tego nie ciagnie
gnysek (10:32, 13.12.17):
ja wczoraj kupiłem bilet na SW na dziś, podobno 9/10
Chell (20:07, 12.12.17):
byle bez warnow
I am vader (19:52, 12.12.17):
A ja bede antychellowski i powiem, ze SW jest dobre, harry potter ok, a lotr to gówno i syf. A i SW I nie istnieje, tylko II-VI
Chell (19:51, 12.12.17):
to ja bede do bolu offstreamowy i powiem, ze SW to zawsze byla dla mnie mordega, najnudniejsze na swiecie, plus meczacy overhype. Harrego Pottera tez nie znosze, tylko LOTR
gnysek (17:06, 12.12.17):
i jeszcze zapomniałeś dodać, że zaczeło się na 4 części
Ignatus (16:49, 12.12.17):
Dałem radę wytrzymać połowę poprzedniej części, wątpie czy będzie lepiej..Będę do bólu mainstreamowy ale SW sie skoczylo na 6 episodzie tak jak obcy na 3 czeci
gnysek (16:40, 12.12.17):
na star warsy kto idzie do kina ?
gnysek (16:40, 12.12.17):
nic koleżku
ANtY (16:10, 12.12.17):
hehe co tam kolegowie
Wojo (16:49, 11.12.17):
Nie no zajebiscie jest sie starzec
Nikas (22:28, 10.12.17):
xDDDD no nieźle typy
Wojo (10:26, 10.12.17):
swoją drogą też bardzo nie lubię swoich urodzin
Wojo (10:26, 10.12.17):
Kiedyś miałem komplex dużych uszów
Wojzax (21:36, 9.12.17):
i wielkość uszu
Wojzax (21:36, 9.12.17):
wiek to tylko liczba
I am Lord (16:23, 9.12.17):
Mi o mojej osiemnastce powiedziała nauczycielka z angola
Sutikku (15:52, 9.12.17):
prosze nie straszyc za pare miesiecy mam 17
I am vader (15:17, 9.12.17):
Moje życie skończyło się po siedemnastce
exp (18:40, 8.12.17):
dwudzieste urodziny to była dla mnie trauma
Wojo (20:43, 7.12.17):
ja chyba z 9
ANtY (13:48, 6.12.17):
a ja 420 hihihihihui
gnysek (11:10, 6.12.17):
a ja 30! jestem 2x starszy niż gmclan
Morro (21:48, 5.12.17):
ja wciąż 14
I am Lord (21:29, 5.12.17):
Uzjel czemu w twoim filmie z flappy birdem przyjales taki zlo nawykowy styl pisania kodu?
PsichiX (21:15, 5.12.17):
a ja 69
Chell (20:29, 5.12.17):
(ja mam 18 jakby co)
Chell (20:29, 5.12.17):
nigdzie juz nie mozna sprawdzac wieku userow!
Adriann (22:45, 29.11.17):
Nie musisz dawać..wystarczy że postawisz serwer;3
Morro (20:52, 29.11.17):
Czyli tak jak myślałem
I am Lord (20:43, 29.11.17):
bo czat pewnie po tcp a ruch po udp :p
Sutikku (19:56, 29.11.17):
albo dopowiedz co jest nie tak, ze czat w almorce dziala spoko, ale grasz nie porusza sie po mapie?
Morro (19:41, 29.11.17):
a może zlitujesz się i wrzucisz na jakimś laptopie w tle serwer Almorki ;> ?
gnysek (19:01, 29.11.17):
mam mam, z Szczecin Games Show, aczkolwiek to nie musi być ostatnia wersja serwera.
Chell (18:44, 29.11.17):
bo nie masz
PsichiX (17:14, 29.11.17):
no to sobie pogralismy :<
gnysek (17:02, 29.11.17):
ja mam ale nie dam, bo łatwo zdekopilować
Uzjel (16:41, 29.11.17):
Nie było chyba oficjalnej apki z serwerem
Adriann (16:08, 29.11.17):
Możliwe że na...dysku starego komputera na strychu..jakieś 115km stąd
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.02277 sekund ] [ Liczba zapytań MySQL: 13 ]