Wikipedysta:Thorlak/brudnopis3

Graf to doskonała struktura danych do reprezentowania zależności pomiędzy różnymi obiektami. Składa się on z dwóch zbiorów: pierwszego - zbioru wierzchołków oznaczanego przez V (ang. Verices) oraz drugiego - zbioru krawędzi oznaczanego przez E (ang. Edges). Jeżeli pomiędzy dwoma wierzchołkami zachodzi jakaś zależność określona przez jakąś konkretną relację to istnieje krawędź łącząca te dwa wierzchołki. Mniej więcej tak może brzmieć uproszczona definicja matematyczna.

Jak można wykorzystać tą strukturę w praktyce? Powiedzmy, że chcielibyśmy zareprezentować w jakiś użyteczny sposób mapę drogową Polski, ponieważ będziemy potrzebować jej do programu, który będzie zainstalowany w nawigacji GPS. W takim wypadku w zbiorze V znalazłyby się nazwy miejscowości, a w zbiorze E wszystkie istniejące połączenia drogowe pomiędzy tymi miastami. Dzięki takiej reprezentacji oraz przy wykorzystaniu odpowiednich algorytmów, które służą do znajdowania najkrótszych ścieżek w grafie będzie można ustalić najbardziej optymalną trasę prowadzącą z jednego miasta do drugiego.

Podstawowe pojęcia

edytuj

Definicja matematyczna

edytuj

Ścieżka w grafie

edytuj

Reprezentacja grafu

edytuj

Lista sąsiedztwa

edytuj

Macierz sąsiedztwa

edytuj

Analiza obu reprezentacji

edytuj