Przechowywanie Grafów

Wstęp

Struktura przechowująca grafy w komputerze różni się złożonością pamięciową. Należy również pamiętać, że stosowany sposób przechowywania może różnić się w zależności od przechowywanego typu grafu. Przedstawiony poniżej kod pozwala na przechowywanie grafu nieskierowanego bez wag krawędziowych.

Przechowywanie Grafu

Jednym z sposobów na przechowanie grafu w komputerze jest macierz sąsiedztwa. Jednak ta technika jest mało wydajna pamięciowo jeśli jest bardzo mało krawędzi, a ponadto każda krawędź jest przechowywana podwójnie. To powoduje kolejne komplikacje, że należy pamiętać o podwójnej aktualizacji danych (jeśli krawędź nie jest skierowana). Na podstawie tych powodów warto zastanowić się nad jak najprostszym i najszybszym sposobem.

Dobrym pomysłem jest, aby każdy wierzchołek posiadał listę wierzchołków z którymi jest połączony. Ponadto przyjmując, że graf nie jest skierowany to można ograniczyć liczbę przechowywanych informacji o połączeniach. Jeśli krawędź (x, y) istnieje to (y, x) też. Przypuśćmy, że x < y wtedy istnienie krawędzi (y, x) sprawdzimy szukając krawędzi (x, y). W ten sposób liczba przechowywanych danych spada o połowę.

Przykład

Dany jest następujący graf:

Można go zapisać w następującej postaci:

W celu sprawdzenia czy istnieje krawędź (1, 2) należy sprawdzić w liście połączeń wierzchołka 1 czy istnieje wartość 2. W przypadku szukania krawędzi (3, 2) należy zamienić wartościami miejscami tj. (2, 3) i dopiero sprawdzić czy wierzchołek 2 ma połącznie z wierzchołkiem 3.

Implementacja

Wierzcholek

Wierzchołek to elementarna część grafu. Będzie on przechowywał listę wierzchołków z którymi jest połączony na liście. Dodatkowo będzie pozwalał na wykonanie dwóch podstawowych operacji: dodania nowej krawędzi oraz sprawdzenia czy dane połączenie już istnieje.

1. class Wierzcholek {
2. private:
3.   std::vector<int> polaczenia;
5. public:
6.   bool sprawdzPolaczenie(int cel) {
7.     return std::find(polaczenia.begin(), polaczenia.end(), cel) != polaczenia.end();
8.   }
10.   bool dodajKrawedz(int cel) {
11.     if (sprawdzPolaczenie(cel)) {
12.       return false;
13.     }
14.     else {
15.       polaczenia.push_back(cel);
16.       return true;
17.     }
18.   }
19. };

W klasie Wierzcholek informacja o połączonych wierzchołkach są przechowywane w zmiennej prywatnej polaczenia. W celu sprawdzenia czy istnieje połączenia tego wierzchałka z jakimś należy wywołać sprawdzenie funkcją sprawdzPolaczenie(), a jako argument podać wierzchołek docelowy. Wynikiem działania funkcji będzie wartość logiczna. Z kolei funkcja dodajKrawedz() pozwala dodać połączenie do innego wierzchołka. Funkcja zwraca informację logiczną czy została dodana. Połączenie może nie zostać dodane ze względu na oszczędzanie pamięci jeśli dane połąćzenie już istnieje.

Graf

Z kolei graf będzie przechowywał listę wszystkich wierzchołków. Ilość wierzchołków jest do ustalenia podczas inicjalizacji nowego wystąpienia klasy. (Zabezpiecza to klasę przed wystąpieniem błędu dodania nowego połączenia, ponieważ dany wierzchołek mógł nie zostać jeszcze dodany.)

1. class Graf {
2. private:
3.   std::vector<Wierzcholek*> wierzcholki;
5. public:
6.   Graf(int ile) {
7.     while (ile-- > 0)
8.       wierzcholki.push_back(new Wierzcholek());
9.   }
11.   void dodajPolaczenia(int id, std::initializer_list<int> polaczenia) {
12.     for (int krawedz : polaczenia)
13.       wierzcholki[id]->dodajKrawedz(krawedz);
14.   }
16.   bool sprawdzKrawedz(int start, int koniec) {
17.     if (start > koniec)
18.       return sprawdzKrawedz(koniec, start);
19.     return wierzcholki[start]->sprawdzPolaczenie(koniec);
20.   }
21. };

W klasie Graf informacja o połączonych wierzchołkach są przechowywane w zmiennej prywatnej wierzcholki. W celu dodania połączeń można skorzystać z funkcji dodajPolaczenia(). Jako pierwszy przyjmowane jest id wierzchołka, a jako drugi listę wierzchołków do których ma zostać utworzone połączenie. Po dodaniu krawędzi można sprawdzić je funkcją sprawdzKrawedz(), która sprawdzi czy połączenie (start, koniec) ostnieje. Wynikiem jest wartość logiczna.

Testowanie funkcji

Napisaną klasę Graf można przetestować przy pomocy poniższego kodu, który wprowadza graf podany wcześniej w przykładzie. Po utworzeniu grafu zostają wypisane wszystkie krawędzi pomiędzy różnymi wierzchołkami, które nie istnieją.

1. int main () {
2.   Graf* g = new Graf(4);
4.   g->dodajPolaczenia(0, { 1, 2, 3 });
5.   g->dodajPolaczenia(1, { 2 });
6.  
7.   cout << "Nie istnieja krawedzie:" << endl;
8.   for (int i = 0; i < 4; i++)
9.     for (int j = i + 1; j < 4; j++)
10.       if (!g->sprawdzKrawedz(i, j))
11.         cout << i << " z " << j << endl;
13.   system("pause");
14.   return 0;
15. }

Uruchomienie programu dla przykładowo wprowadzonego grafu zwraca następujący wynik:

1. Nie istnieją krawędzie:
2. 1 z 3
3. 2 z 3

Wynik ten zgadza się z wprowadzonym grafem.

• Kod źródłowy Implementacja