Wikipedysta:Thorlak/brudnopis3

Grafy

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.