Cześć wszystkim
W tej notatce postanowiłem wymienić główne struktury danych używane do przechowywania wykresów w informatyce, a także opowiem o kilku innych takich strukturach, które w jakiś sposób „skrystalizowały się” dla mnie.
Zacznijmy więc. Ale nie od samego początku - myślę, że wszyscy już wiemy, czym jest graf i czym są (skierowany, nieskierowany, ważony, nieważony, z wieloma krawędziami i pętlami lub bez).
Więc chodźmy. Jakie mamy opcje struktur danych do „przechowywania grafów”?
1. Macierzowe struktury danych
1.1 Macierz sąsiedztwa. Macierz sąsiedztwa to macierz, w której nagłówkom wierszy i kolumn odpowiadają numery wierzchołków grafu, a o wartości każdego z jego elementów a(i,j) decyduje obecność lub brak krawędzi pomiędzy wierzchołkami i oraz j (jasne jest, że dla grafu nieskierowanego taka macierz będzie symetryczna, albo możemy zgodzić się, że wszystkie wartości przechowujemy tylko powyżej głównej przekątnej). Dla grafów nieważonych a(i,j) można wyznaczyć liczbą krawędzi od i do j (jeśli takiej krawędzi nie ma, to a(i,j)= 0), a dla grafów ważonych także wagą (waga całkowita) wymienionych krawędzi.
1.2 Macierz zachorowań. W tym przypadku nasz graf jest również zapisany w tabeli, w której z reguły numery wierszy odpowiadają numerom jego wierzchołków, a numery kolumn odpowiadają wcześniej ponumerowanym krawędziom. Jeżeli wierzchołek i krawędź są do siebie incydentne, to w odpowiedniej komórce wpisuje się wartość niezerową (w przypadku grafów nieskierowanych wpisuje się 1, jeśli wierzchołek i krawędź są incydentne, dla grafów zorientowanych - „1”, jeśli krawędź „wychodzi” z wierzchołka i „-1”, jeśli „zawiera się” w nim (łatwo to zapamiętać, ponieważ znak „minus” również wydaje się „zawarty” w liczbie „-1”). W przypadku wykresów ważonych ponownie zamiast 1 i -1 można określić całkowitą wagę krawędzi.
2. Wyliczeniowe struktury danych
2.1 Lista sąsiedztwa. Cóż, tutaj wszystko wydaje się proste. Ogólnie rzecz biorąc, każdy wierzchołek grafu można powiązać z dowolną strukturą wyliczeniową (lista, wektor, tablica, ...), która będzie przechowywać numery wszystkich wierzchołków sąsiadujących z danym. W przypadku grafów skierowanych do takiej listy dodamy tylko te wierzchołki, do których istnieje „skierowana” krawędź z wierzchołka cechy. W przypadku grafów ważonych implementacja będzie bardziej złożona.
2.2 Lista żeber. Dość popularna struktura danych. Lista krawędzi, jak mówi nam Kapitan Oczywistość, to tak naprawdę lista krawędzi grafu, z których każda jest określona przez wierzchołek początkowy, wierzchołek końcowy (w przypadku grafów nieskierowanych kolejność nie ma tu znaczenia, choć dla ujednolicenia można użyj różnych zasad, np. podając wierzchołki w kolejności rosnącej) i wagę (tylko dla grafów ważonych).
Możesz przyjrzeć się listom matryc wymienionym powyżej bardziej szczegółowo (i z ilustracjami), na przykład: .
2.3 Tablica sąsiedztwa. Nie jest to najczęstsza konstrukcja. W swej istocie jest to forma „pakowania” list sąsiedztwa w jedną strukturę wyliczeniową (tablica, wektor). Pierwsze n (według liczby wierzchołków grafu) elementów takiej tablicy zawiera indeksy początkowe tej samej tablicy, od której zapisywane są w jednym rzędzie wszystkie wierzchołki sąsiadujące z danym.
Tutaj znalazłem najbardziej zrozumiałe (dla siebie) wyjaśnienie:
3. Wektor sąsiedztwa i tablica sąsiedztwa asocjacyjnego
Okazało się, że autor tych wierszy, nie będąc zawodowym programistą, ale okresowo zajmującym się wykresami, najczęściej zajmował się listami krawędzi. Rzeczywiście jest to wygodne, jeśli wykres ma wiele pętli i krawędzi. I tak przy opracowywaniu klasycznych list krawędzi proponuję zwrócić uwagę na ich „rozwój/rozgałęzienie/modyfikację/mutację”, czyli: wektor sąsiedztwa i tablicę sąsiedztwa asocjacyjnego.
3.1 Wektor sąsiedztwa
Przypadek (a1): wykres nieważony
Nazwiemy wektorem sąsiedztwa dla grafu nieważonego uporządkowanym zbiorem parzystej liczby liczb całkowitych (a[2i], a[2i+1],..., gdzie i jest o numerze c 0), w którym każda para liczb is a[2i], a[2i+1 ] określa krawędź grafu pomiędzy wierzchołkami odpowiednio a[2i] i a[2i+1].
Ten format zapisu nie zawiera informacji o tym, czy graf jest skierowany (możliwe są obie opcje). Przy stosowaniu formatu dwuznaku uważa się, że krawędź jest skierowana od a[2i] do a[2i+1]. Tutaj i poniżej: dla grafów nieskierowanych, jeśli zajdzie taka potrzeba, można zastosować wymagania dotyczące kolejności rejestrowania wierzchołków (np. aby na pierwszym miejscu znajdował się wierzchołek z mniejszą wartością przypisanej mu liczby).
W C++ zaleca się określenie wektora sąsiedztwa za pomocą std::vector, stąd nazwa tej struktury danych.
Przypadek (a2): graf nieważony, wagi krawędzi są liczbami całkowitymi
Analogicznie do przypadku (a1) wektor sąsiedztwa dla grafu ważonego z całkowitymi wagami krawędzi nazywamy uporządkowanym zbiorem (tablicą dynamiczną) liczb (a[3i], a[3i+1], a[3i+2], ..., gdzie i jest o numerze c 0), gdzie każda „trójka” liczb a[3i], a[3i+1], a[3i+2] określa krawędź grafu pomiędzy wierzchołkami o numerach a[3i] i a[3i+1], a wartość a [3i+2] jest wagą tej krawędzi. Taki graf może być również skierowany lub nie.
Przypadek (b): graf nieważony, wagi krawędzi niecałkowite
Ponieważ nie jest możliwe przechowywanie elementów heterogenicznych w jednej tablicy (wektorze), możliwa jest następująca implementacja. Wykres zapisany jest w parze wektorów, gdzie pierwszy wektor jest wektorem sąsiedztwa grafu bez określenia wag, a drugi wektor zawiera odpowiadające im wagi (możliwa implementacja dla C++: std::pair ). Zatem dla krawędzi określonej przez parę wierzchołków pod indeksami 2i, 2i+1 pierwszego wektora waga będzie równa elementowi pod indeksem i drugiego wektora.
Dlaczego jest to konieczne?
Cóż, autor tych wierszy uznał je za całkiem przydatne przy rozwiązywaniu wielu problemów. Cóż, z formalnego punktu widzenia będą następujące zalety:
- Wektor sąsiedztwa, jak każda inna struktura „wyliczeniowa”, jest dość zwarty, zajmuje mniej pamięci niż macierz sąsiedztwa (w przypadku grafów rzadkich) i jest stosunkowo łatwy w implementacji.
- Wierzchołki wykresu w zasadzie można również oznaczyć liczbami ujemnymi. A co jeśli taka „perwersja” będzie potrzebna?
- Wykresy mogą zawierać wiele krawędzi i wiele pętli o różnych wagach (dodatniej, ujemnej, a nawet zerowej). Nie ma tutaj żadnych ograniczeń.
- Krawędom możesz także przypisać różne właściwości - ale więcej na ten temat znajdziesz w rozdziale 4.
Trzeba jednak przyznać, że ta „lista” nie oznacza szybkiego dostępu do krawędzi. I tutaj na ratunek przychodzi tablica sąsiedztwa asocjacyjnego, o której mowa poniżej.
3.2 Tablica sąsiedztwa asocjacyjnego
Jeśli więc dostęp do konkretnej krawędzi, jej wagi i innych właściwości jest dla nas krytyczny, a wymagania pamięciowe nie pozwalają nam na skorzystanie z macierzy sąsiedztwa, to zastanówmy się, jak możemy zmienić wektor sąsiedztwa, aby rozwiązać ten problem. Zatem kluczem jest krawędź grafu, którą można określić jako uporządkowaną parę liczb całkowitych. Jak to wygląda? Czy nie jest to klucz w tablicy asocjacyjnej? A jeśli tak, dlaczego tego nie wdrożymy? Miejmy tablicę asocjacyjną, w której każdy klucz – uporządkowana para liczb całkowitych – będzie powiązany z wartością – liczbą całkowitą lub liczbą rzeczywistą, która określa wagę krawędzi. W C++ wskazane jest zaimplementowanie tej struktury w oparciu o kontener std::map (std::map , int> lub std::map , double>) lub std::multimap, jeśli oczekiwanych jest wiele krawędzi. Cóż, 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 i nie ma nawet ścisłych wymagań co do nieujemności liczb wierzchołków (nie wiem komu to potrzebne, ale jednak).
4. Struktury danych są pełne, ale czegoś brakuje
I to prawda: przy rozwiązywaniu szeregu problemów może zaistnieć potrzeba przypisania krawędziom wykresu pewnych cech i odpowiednio ich przechowywania. Jeżeli uda się jednoznacznie sprowadzić te cechy do liczb całkowitych, wówczas możliwe będzie przechowywanie takich „wykresów z dodatkowymi cechami” przy wykorzystaniu rozszerzonych wersji wektora sąsiedztwa i tablicy asocjacyjnej sąsiedztwa.
Mamy więc graf nieważony, dla każdej krawędzi którego trzeba zapisać np. 2 dodatkowe cechy określone liczbami całkowitymi. W tym przypadku można zdefiniować jego wektor sąsiedztwa jako uporządkowany zbiór nie „par”, ale „kwartetów” liczb całkowitych (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , gdzie a[2i+2] i a[2i+3] określą charakterystykę odpowiedniej krawędzi. W przypadku grafów z całkowitymi wagami krawędzi kolejność jest ogólnie podobna (jedyna różnica będzie taka, że atrybuty będą zgodne z wagą krawędzi i będą określone przez elementy a[2i+3] i a[2i+4] , a sama krawędź zostanie określona nie 4, ale 5 liczb uporządkowanych). W przypadku grafu z niecałkowitymi wagami krawędzi cechy można zapisać w jego nieważonej składowej.
Stosując asocjacyjną tablicę sąsiedztwa dla grafów z całkowitymi wagami krawędzi, można określić jako wartość nie pojedynczą liczbę, ale tablicę (wektor) liczb, które oprócz wagi krawędzi określają wszystkie inne niezbędne cechy. Jednocześnie niedogodnością w przypadku wag niecałkowitych będzie konieczność podania znaku z liczbą zmiennoprzecinkową (tak, jest to niedogodność, ale jeśli takich znaków nie jest zbyt wiele i nie nie ustawiaj ich zbyt „podstępnie” podwójnie, wtedy może to być nic). Oznacza to, że w C++ rozszerzone tablice sąsiedztwa asocjacyjnego można zdefiniować w następujący sposób: std::map , std::vector> lub std::map , std::vector, w którym pierwszą wartością w „wektorze-klucz-wartość” będzie waga krawędzi, a następnie umieszczone zostaną numeryczne oznaczenia jej charakterystyk.
Literatura:
O grafach i algorytmach ogólnie:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorytmy: konstrukcja i analiza, wydanie 2: Trans. z angielskiego – M.: Wydawnictwo Williams, 2011.
2. Harari Frank. Teoria grafów. M.: Mir, 1973.
Raport autora na temat tych samych wektorów i tablicy asocjacyjnej przylegań:
3. Czernouchow SA Wektor sąsiedztwa i tablica sąsiedztwa asocjacyjnego jako sposoby reprezentacji i przechowywania grafów / SA Chernouhov. Wektor sąsiedztwa i mapa sąsiedztwa jako struktury danych reprezentujące graf // Zbiór artykułów Międzynarodowej Konferencji Naukowo-Praktycznej „Problemy wdrażania wyników innowacyjnych rozwiązań i sposoby ich rozwiązywania” (Saratow, 14.09.2019 września 2019 r.). – Sterlitamak: AMI, 65, s. 69-XNUMX. XNUMX-XNUMX
Przydatne źródła internetowe na ten temat:
4.
5.
Źródło: www.habr.com