19. Grafy i metody ich przeszukiwania. Zastosowania.

Graf w najprostszym ujęciu to zbiór wierzchołków oraz zbiór krawędzi, czyli par wierzchołków.

Graf nieskierowany jest to para G=(V,E), gdzie V to niepusty zbiór wierzchołków (vertices); E to zbiór krawędzi (edges) tj. podzbiór rodziny wszystkich dwuelementowych podzbiorów zbioru V.

Graf skierowany: jest to para G=(V,E), gdzie V j.w.; E to zbiór krawędzi tj. par uporządkowanych o elementach ze zbioru V. Ruch po grafie możliwy jest tylko w kierunkach wskazywanych przez krawędzie. Graf skierowany można sobie wyobrazić jako sieć ulic, z których każda jest jednokierunkowa.

Droga w grafie skierowanym - ciąg krawędzi takich, że koniec jednej krawędzi jest początkiem następnej.

Droga zamknięta jest to taka droga, która zaczyna i kończy się w tym samym wierzchołku (punkcie) x₁, x₂, ....x₁.

Długość drogi jest równa ilości krawędzi lub jest o 1 mniejsza od liczby wierzchołków grafu.

Cykl - droga zamknięta o długości co najmniej 1, taka że wszystkie wierzchołki są różne.

Graf acykliczny - graf skierowany nie mający cykli.

Droga bez cykli - acykliczna; to droga niezamknięta.

Krawędź wielokrotna - dwa punkty połączone są co najmniej dwiema krawędziami.

Przeszukiwanie w głąb - polega na wybraniu dowolnego wierzchołka i rekurencyjnemu wywołaniu funkcji przeszukującej dla każdego wierzchołka sąsiedniego. Przeszukanie powyższego grafu metodą w głąb zaczynając od wierzchołka A daje następujące wyniki: ABDECF.

Przeszukiwanie wszerz - wybieramy dowolny wierzchołek i przeszukujemy jego następniki, ale nie rekurencyjnie, tylko powierzchownie. Po przeszukaniu wszystkich następników zaczynamy przeszukiwać sąsiednie wierzchołki tych następników. Algorytm bazuje na przeszukaniu wierzchołków na jednym poziomie przed przystąpieniem do przeszukiwania kolejnych poziomów. Przeszukanie powyższego grafu metodą wszerz daje następujące wyniki: ABCDEF.

Grafy mają szerokie zastosowania w informatyce, a także w wielu dziedzinach życia codziennego, np.

- mapy - aby dowiedzieć się jaką najkrótszą drogą można dostać się z jednej miejscowości do drugiej, można w tym celu wykorzystać graf, którego wierzchołki będą odpowiadały miejscowościom, a krawędzie drogom.

- dokumenty hipertekstowe - przeszukując Internet napotykamy dokumenty, które zawierają odnośniki do innych dokumentów. Internet jest grafem, w którym wierzchołkami są dokumenty, a krawędziami odsyłacze.

- sieci - sieć komputerowa zbudowana jest z komputerów, które przesyłają między sobą informacje. Komputery w danej sieci są reprezentowane przez wierzchołki grafu, a połączenia między nimi przez krawędzie.

- struktura programu - kompilator buduje graf reprezentujący strukturę wywołań podprogramów w kompilowanym programie. Wierzchołkami grafu są różne funkcje, natomiast krawędzie są skojarzone z wywołaniami funkcji.

- katalogi ulokowane w naszych komputerach wraz z podkatalogami też tworzą graf.

---