Pojęcie grafu

Algorytmy grafowe

• przeszukiwanie w głąb (DFS)
• przeszukiwanie wszerz (BFS)

Definicja

Grafem nazywamy strukturę złożoną z wierzchołków i krawędzi łączących te wierzchołki. Takie struktury danych mają szerokie zastosowanie w wielu dziedzinach nauki takich jak matematyka, informatyka, kryptografia, topologia, chemia itd. 

Graf nieskierowany

Graf nieskierowany połączenie między dwoma wierzchołkami A i B jest dwukierunkowe (A <--> B). Oznacza to, że możemy przejść z wierzchołka A do B i z B do A.

Przykład grafu nieskierowanego

Graf skierowany

W tym rodzaju grafów nadany jest kierunek poruszania się między dwoma wierzchołkami:

Zauważmy, że przejście z wierzchołka 1 do 3 jest możliwe tylko poprzez wierzchołek numer 5, natomiast z 9 możemy tylko wyjść ale nie ma możliwości przejścia do niego.

Graf wagowy

W grafie wagowym (skierowanym lub nieskierowanym) każda krawędź ma nadaną wagę. Wierzchołki można porównać do miast, krawędzie do dróg łączących te miasta, natomiast odległości między tymi miastami to wagi.

Drzewo

Drzewo to taki graf, w którym istnieje dokładnie jedna droga między dwoma wierzchołkami. W drzewie o n wierzchołkach jest dokładnie n-1 krawędzi.