Grafy to jedna z najważniejszych struktur danych w informatyce, wykorzystywana do modelowania sieci społecznych, map drogowych, zależności między zadaniami i wielu innych problemów. 

Wiemy już, że każdy graf składa się z dwóch zbiorów: zbioru wierzchołków i zbioru krawędzi.  Ich implementacja wymaga przemyślenia, jak przechowywać wierzchołki i krawędzie, aby operacje były szybkie i efektywne. Wybór odpowiedniej struktury danych – macierzy sąsiedztwa, listy sąsiedztwa czy innych bardziej zaawansowanych reprezentacji – zależy od charakterystyki grafu, liczby wierzchołków, gęstości połączeń i rodzaju operacji, które będziemy wykonywać. W tym e‑materiale poznamy trzy najczęściej stosowane sposoby implementacji grafów – macierz sąsiedztwa, listę sąsiedztwa oraz macierz incydencji.

Ćwiczenie na rozgrzewkę: