IMG950 (5)

Struktura danych:

•    sposób uporządkowania informacji w komputerze np. rekord, tablica, graf, kolejka i stos

Grafy to struktura danych która odgrywa ważną role w algorytmice. Stosuje się je do rozwiązań różnego rodzaju problemów algorytmicznych - znajdowanie optymalnych dróg, obmyilanie strategii gry, rozwiązywania łamigłówek oraz rozwiązywanie wielu złożonych problemów technicznych.

Graf drzewa:

•    do reprezentacji hierarchii np. mistrzostwa sportowych

•    do opisu rozwoju populacji

•    GPS

•    gry komputerowe, systemy sztucznej inteligencji

•    projektowanie robotów mobilnych

•    przedstawiania sieci komputerowych

•    protokół RIP Rodzaje giefów.

•    Eulera

•    Hamiltona

Algorytm | oMkianla optymalnych dróg w grafie:

•    Boy-Warshal!

• f Joyd — Warshail

•    Dijkstry

•    BeOmana — Forda

ktpyytm Dijkstry

•    służy do wyznaczania najmniejszej odległości do ustalonego wierzchołka.

• graf nie może zawierać krawędzi o ujemnych wagach.

•    zbiór Q wierzchołków dla których nie obliczono jeszcze najkrótszej ścieżki

•    wektor Oji] odległość od wierzchołka s do i

Q-zawiera wszystkie wierzchołki D - pierwszy wiersz macierzy wag krawędzi A s-początek

Relaksacja krawędzi - sprawdzanie czy przy przejściu daną krawędzią grafu (u,v) „u" do „v" nfe otrzymamy krótszej niż dotychczasowa ścieżka z ,s” do „v"

Algorytm Dijkstry jest oparty o strategie zachłanną

Algorytm Beiimana - Forda:

• opiera się na założeniu ze wagi są w grafie ujemne