Witajcie wszyscy.
W tym artykule postanowiłem wymienić główne struktury danych używane do przechowywania grafów w informatyce, a także opisać jeszcze kilka takich struktur, które jakoś same się «wykrystalizowały» w mojej głowie.
Zaczynajmy. Ale nie od samego początku – myślę, że wszyscy już wiemy, czym jest graf i jakie są jego rodzaje (skierowane, nieskierowane, ważące, nieważące, z wieloma krawędziami oraz pętlami lub bez nich).
No dobrze, przejdźmy do rzeczy. Jakie mamy zatem opcje struktur danych do «przechowywania grafów»?
1. Struktury danych oparte na macierzach
1.1 Macierz sąsiedztwa. Macierz sąsiedztwa to macierz, w której nagłówki wierszy i kolumn odpowiadają numerom wierzchołków grafu, a wartość każdego jej elementu a(i,j) określana jest przez obecność lub brak krawędzi między wierzchołkami i oraz j (jasne, że dla grafu nieskierowanego taka macierz będzie symetryczna, lub możemy umówić się, że wszystkie wartości przechowujemy jedynie powyżej głównej przekątnej). Dla grafów nieważonych a(i,j) można ustalić liczbą krawędzi z i do j (jeśli taka krawędź nie istnieje, to a(i,j)= 0), a dla ważonych również – jako wagę (łączną wagę) wspomnianych krawędzi.
1.2 Macierz incydencji. W tym przypadku nasz graf również jest przechowywany w tabeli, w której zazwyczaj numery wierszy odpowiadają numerom jego wierzchołków, a numery kolumn – wcześniejszym krawędziom. Jeśli wierzchołek i krawędź są incydentne, to w odpowiedniej komórce zapisywana jest wartość różna od zera (dla grafów nieskierowanych zapisujemy 1 w przypadku incydencji wierzchołka i krawędzi, dla grafów skierowanych – „1”, jeśli krawędź „wychodzi” z wierzchołka i „-1”, jeśli do niego „wchodzi” (zapamiętuje się to dość łatwo, bo znak „minus” również jakoś „wchodzi” w liczbę „-1”)). Dla grafów ważonych zamiast 1 i -1 można ponownie podawać łączną wagę krawędzi.
2. Struktury danych wyliczeniowe
2.1 Lista sąsiedztwa. Tutaj wszystko jest dość proste. Każdemu wierzchołkowi grafu możemy przyporządkować dowolną strukturę wyliczeniową (listę, wektor, tablicę, …), w której będą przechowywane numery wszystkich wierzchołków sąsiednich danej. W przypadku grafów skierowanych w takiej liście zapiszemy tylko te wierzchołki, do których prowadzi "skierowana" krawędź z wierzchołka-przykładu. Dla grafów ważonych realizacja będzie bardziej skomplikowana.
2.2 Lista krawędzi. Bardzo popularna struktura danych. Lista krawędzi, jak podpowiada nam Kapitan Oczywistość, to po prostu lista krawędzi grafu, z których każda określana jest wierzchołkiem początkowym, wierzchołkiem końcowym (w przypadku grafów nieskierowanych kolejność nie ma tu znaczenia, chociaż dla ujednolicenia można zastosować różne zasady, np. wskazywać wierzchołki w kolejności rosnącej) oraz wagą (tylko dla grafów ważonych).
O wymienionych wyżej listach-macierzach można poczytać więcej (i z ilustracjami) na przykład .
2.3 Tablica sąsiedztwa. Nie jest to najczęściej spotykana struktura. Zasadniczo stanowi ona formę "pakowania" list sąsiedztwa w jedną strukturę wyliczeniową (tablicę, wektor). Pierwsze n (zgodnie z liczbą wierzchołków grafu) elementów takiej tablicy zawiera indeksy początkowe tej samej tablicy, od których kolejno zapisane są wszystkie wierzchołki sąsiednie.
Tutaj znalazłem najjaśniejsze (dla mnie) wyjaśnienie:
3. Wektor sąsiedztwa i Asocjacyjna tablica sąsiedztwa
Zdarza się, że autor tych słów, nie będąc profesjonalnym programistą, ale okresowo mając do czynienia z grafami, najczęściej miał do czynienia z listami krawędzi. Rzeczywiście, jest to wygodne, gdy w grafie występują wielokrotne pętle i krawędzie. Dlatego w rozwinięciu klasycznych list krawędzi proponuję zwrócić uwagę na ich "rozwój / odgałęzienie / modyfikację / mutację", a konkretnie: na wektor sąsiedztwa i asocjacyjną tablicę sąsiedztwa.
3.1 Wektor sąsiedztwa
Przypadek (a1): graf nieważony
Będziemy nazywać wektorem sąsiedztwa dla nieważonego grafu uporządkowany zbiór parzystej liczby liczb całkowitych (a[2i], a[2i+1],…, gdzie i numeruje się od 0), w którym każda para liczb a[2i], a[2i+1] określa krawędź grafu między wierzchołkami a[2i] i a[2i+1] odpowiednio.
Ten format zapisu nie zawiera informacji, czy graf jest skierowany (oba warianty są możliwe). Przy użyciu formatu dla grafu zakłada się, że krawędź jest skierowana z a[2i] do a[2i+1]. Tutaj i dalej: dla grafów nieskierowanych, w razie potrzeby, mogą być stosowane wymagania dotyczące kolejności zapisu wierzchołków (na przykład, aby pierwsza była wierzchołek z mniejszą wartością przypisanego numeru).
W C++ wygodnie jest definiować wektor sąsiedztwa za pomocą std::vector, stąd wybrano nazwę tej struktury danych.
Przypadek (a2): nieskierowany graf, wagi krawędzi są całkowite.
Podobnie jak w przypadku (a1), nazwiemy wektorem sąsiedztwa dla grafu ważonego z całkowitymi wagami krawędzi uporządkowany zestaw (tablica dynamiczna) liczb (a[3i], a[3i+1], a[3i+2],…, gdzie i numeruje się od 0), gdzie każdy „trio” liczb a[3i], a[3i+1], a[3i+2] definiuje krawędź grafu między wierzchołkami o numerach a[3i] i a[3i+1] odpowiednio, a wartość a[3i+2] to waga tej krawędzi. Taki graf może być zarówno skierowany, jak i nieskierowany.
Przypadek (b): nieskierowany graf, wagi krawędzi nie są całkowite.
Z uwagi na to, że w jednej tablicy (wektorze) nie można przechowywać elementów różnego typu, możliwa jest na przykład następująca realizacja. Graf jest przechowywany w parze wektorów, w której pierwszy wektor jest wektorem sąsiedztwa grafu bez wskazania wag, a drugi wektor zawiera odpowiadające wagi (możliwa realizacja dla C++: std::pair). W ten sposób dla krawędzi zdefiniowanej przez parę wierzchołków pod indeksami 2i, 2i+1 w pierwszym wektorze, waga będzie równa elementowi pod indeksem i w drugim wektorze.
A po co to potrzebne?
Cóż, autorowi tych słów wydawało się to dość przydatne w rozwiązaniu szeregu zadań. A z formalnego punktu widzenia, będą tutaj takie zalety:
- Wektor sąsiedztwa, jak każda inna struktura „wyliczeniowa”, jest wystarczająco kompaktowy, zajmuje mniej pamięci niż macierz sąsiedztwa (dla grafów rzadkich), a jego realizacja jest stosunkowo prosta.
- Wierzchoły grafu mogą być zasadniczo oznaczone również liczbami ujemnymi. Może się to przydać w jakimś „dziwnym” przypadku.
- Grafy mogą zawierać krawędzie wielokrotne oraz wielokrotne pętle, przy czym z różnymi wagami (dodatnie, ujemne, a nawet zerowe). Nie ma tutaj żadnych ograniczeń.
- Można również przypisywać różne właściwości krawędziom – ale o tym mowa w punkcie 4.
Jednakże, należy przyznać, że ta "listowa struktura" nie zapewnia szybkiego dostępu do krawędzi. I tutaj z pomocą przychodzi asocjacyjna tablica krawędzi, o czym poniżej.
3.2 Asocjacyjna tablica krawędzi
Zatem, jeśli dostęp do konkretnej krawędzi, jej wagi i innych właściwości jest dla nas krytyczny, a wymagania dotyczące pamięci nie pozwalają na użycie macierzy krawędzi, pomyślmy, jak można zmodyfikować wektor krawędzi, aby rozwiązać ten problem. Kluczem jest krawędź grafu, którą można zdefiniować jako uporządkowaną parę liczb całkowitych. Na co to wygląda? Czyż nie przypomina klucza w asocjacyjnej tablicy? A jeśli tak, to czemu by tego nie zrealizować? Niech powstanie taka asocjacyjna tablica, w której każdemu kluczowi – uporządkowanej parze liczb całkowitych – zostanie przyporządkowana wartość – liczba całkowita lub rzeczywista, definiująca wagę krawędzi. W C++ implementacja tej struktury wydaje się zasadna na bazie kontenera std::map (std::map <std::pair , int> lub std::map <std::pair , double>), lub std::multimap, jeśli przewiduje się wiele krawędzi. I oto, mamy strukturę do przechowywania grafów, która zajmuje mniej pamięci niż struktury „macierzowe”, może definiować grafy z wieloma pętlami i krawędziami oraz nawet nie ma sztywnych wymagań co do nieujemności numerów wierzchołków (nie wiem, kto by tego potrzebował, ale jednak).
4. Struktura danych, choć "przepełniona", czegoś brakuje
I rzeczywiście: podczas rozwiązywania pewnych problemów może zaistnieć potrzeba przypisania krawędziom grafu pewnych cech i, w konsekwencji, ich przechowywania. Jeśli możliwe jest jednoznaczne przypisanie tych cech do liczb całkowitych, to można przechowywać takie "grafy z dodatkowymi cechami" wykorzystując rozszerzone wersje wektora krawędzi i asocjacyjnej tablicy krawędzi.
Załóżmy, że mamy nieskierowany graf, dla którego należy przechowywać na przykład 2 dodatkowe atrybuty określane przez liczby całkowite. W takim przypadku można zdefiniować jego wektor sąsiedztwa jako uporządkowany zestaw nie „par”, a „czwartetów” liczb całkowitych (a[2i], a[2i+1], a[2i+2], a[2i+3]…), gdzie a[2i+2] i a[2i+3] będą określać atrybuty odpowiadającej krawędzi. Dla grafu z wagami całkowitymi krawędzi sposób postrzegania jest zasadniczo analogiczny (różnicą będzie jedynie to, że atrybuty będą podawane po wadze krawędzi i zdefiniowane przez elementy a[2i+3] i a[2i+4], a sama krawędź będzie definiowana nie przez 4, a 5 uporządkowanych liczb). A dla grafu z niecałkowymi wagami krawędzi atrybuty można będzie zapisać w jego nieskierowanym komponencie.
Przy użyciu asocjacyjnej tablicy sąsiedztwa dla grafów z całkowitymi wagami krawędzi można zamiast pojedynczej liczby używać tablicy (wektora) liczb, które określają, oprócz wagi krawędzi, wszystkie inne niezbędne atrybuty. Wadą w przypadku wag niecałkowitych będzie konieczność zdefiniowania atrybutu jako liczby zmiennoprzecinkowej (tak, to niewygodne, ale jeśli takich atrybutów nie jest zbyt wiele i nie definiować ich zbyt „sprytnymi” typami double, to może da się to przeżyć). Oznacza to, że w C++ rozszerzone asocjacyjne tablice sąsiedztwa można definiować w następujący sposób: std::map<std::pair<int, int>, std::vector> lub std::map<std::pair<int, int>, std::vector, przy czym pierwszą wartością w „wektorze-wartości-pod-kluczem” będzie waga krawędzi, a następnie znajdują się oznaczenia jego atrybutów liczbowych.
Literatura:
O grafach i algorytmach w ogóle:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algorytmy: budowa i analiza, wydanie 2: Tłum. z ang. – M.: Wydawnictwo „Williams”, 2011.
2. Harari, Frank. Teoria grafów. M.: Mir, 1973.
Referat autora na temat wspomniany wektor i asocjacyjną tablicę sąsiedztwa:
3. Chernouhov S.A. Wektor sąsiedztwa i mapa sąsiedztwa jako sposoby reprezentacji i przechowywania grafów / S.A. Chernouhov. Wektor sąsiedztwa i mapa sąsiedztwa jako struktury danych do reprezentacji grafu // Zbiór artykułów Międzynarodowej Konferencji Naukowo-Praktycznej „Problemy wdrażania wyników innowacyjnych opracowań i sposoby ich rozwiązania” (Saratów, 14.09.2019). – Stierlitamak: AMI, 2019, s. 65-69
Przydatne źródła internetowe na ten temat:
4.
5.
Źródło: habr.com
