Wiemy już, że każdy graf składa się z dwóch zbiorów: zbioru wierzchołków i zbioru krawędzi. Przechowywanie obu zbiorów w pamięci programu w postaci zwykłych tablic jest bardzo nieefektywne, ponieważ gdybyśmy chcieli sprawdzić, czy w grafie istnieje dana krawędź, trzeba by było przeszukać całą tablicę krawędzi. W niektórych algorytmach, gdzie sprawdzanie sąsiedztwa dwóch wierzchołków wykonuje się dość często, reprezentacja ta bardzo spowalniałaby program.

Aby tego uniknąć, wykorzystuje się znacznie efektywniejsze sposoby reprezentacji grafów. W tym e‑materiale poznamy trzy najczęściej stosowane – macierz sąsiedztwa, listę sąsiedztwa oraz macierz incydencji.

Ćwiczenie na rozgrzewkę