Sposoby reprezentacji grafów
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.
Omówienie tego zagadnienia w kontekście wybranych języków programowania znajdziesz w e‑materiałach:
Sposoby reprezentacji grafów w języku C++Sposoby reprezentacji grafów w języku C++,
Sposoby reprezentacji grafów w języku JavaSposoby reprezentacji grafów w języku Java,
Sposoby reprezentacji grafów w języku PythonSposoby reprezentacji grafów w języku Python.
Scharakteryzujesz, czym są macierz sąsiedztwa, lista sąsiedztwa i macierz incydencji, oraz wyjaśnisz, jak za ich pomocą przedstawić dany graf.
Wskażesz zalety każdej z poznanych reprezentacji.
Przeanalizujesz reprezentacje grafów nieskierowanych i skierowanych, multigrafów oraz grafów ważonych.