Czym jest graf?

Graf to struktura danych, która modeluje zbiór rzeczy i połączenia między nimi. Rzeczy nazywamy wierzchołkami (lub węzłami), a połączenia — krawędziami.

Grafy są wszędzie. Sieci społecznościowe to grafy (ludzie są wierzchołkami, a znajomości — krawędziami). Mapy dróg to grafy (skrzyżowania są wierzchołkami, a ulice — krawędziami). Internet, drzewa zależności i mapy gier to również grafy.

W tym kursie skupimy się na grafie nieskierowanym: jeśli krawędź łączy u i v, to v jest również połączony z u. Nie ma kierunku. Dla uproszczenia jako kluczy wierzchołków użyjemy liczb całkowitych.

Wewnątrz będziemy przechowywać graf jako listę sąsiedztwa: mapę, która przyporządkowuje każdemu wierzchołkowi listę jego sąsiadów. Dzięki temu pobranie sąsiadów wierzchołka wymaga jednego dostępu do mapy, czego potrzebuje większość algorytmów grafowych.

Operacje, które zaimplementujemy w naszej klasie Graph, to:

1. addVertex: Dodaj nowy wierzchołek, który nie ma jeszcze żadnych krawędzi.
2. addEdge: Połącz dwa wierzchołki.
3. hasEdge: Sprawdź, czy dwa wierzchołki są połączone.
4. getNeighbors: Pobierz listę sąsiadów wierzchołka.
5. removeEdge: Usuń połączenie między dwoma wierzchołkami.
6. size: Policz, ile wierzchołków ma graf.

Zbudujmy klasę Graph!