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 Wierzchołek {
2.   private List<int> połączenia = new List<int>();
4.   public bool sprawdźPołączenie(int cel) {
5.     return połączenia.IndexOf(cel) != -1;
6.   }
8.   public bool dodajKrawędź(int cel) {
9.     if (sprawdźPołączenie(cel)) {
10.       return false;
11.     } else {
12.       połączenia.Add(cel);
13.       return true;
14.     }
15.   }
16. }

W klasie Wierzchołek informacja o połączonych wierzchołkach są przechowywane w zmiennej prywatnej połączenia. W celu sprawdzenia czy istnieje połączenia tego wierzchałka z jakimś należy wywołać sprawdzenie funkcją sprawdźPołączenie(), a jako argument podać wierzchołek docelowy. Wynikiem działania funkcji będzie wartość logiczna. Z kolei funkcja dodajKrawędź() 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łączenie 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 List<Wierzchołek> wierzchołki = new List<Wierzchołek>();
4.   public Graf(int ile) {
5.     while (ile-- > 0)
6.       wierzchołki.Add(new Wierzchołek());
7.   }
9.   public void dodajPołączenia(int id, params int[] połączenia) {
10.     foreach(int krawędź in połączenia)
11.       wierzchołki[id].dodajKrawędź(krawędź);
12.   }
14.   public bool sprawdźKrawędź(int start, int koniec) {
15.     if (start > koniec)
16.       return sprawdźKrawędź(koniec, start);
17.     return wierzchołki[start].sprawdźPołączenie(koniec);
18.   }
19. }

W klasie Graf informacja o połączonych wierzchołkach są przechowywane w zmiennej prywatnej wierzchołki. W celu dodania połączeń można skorzystać z funkcji dodajPołączenia(). 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ą sprawdźKrawędź(), 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. class Program {
2.   static void Main(string[] args) {
3.     Graf g = new Graf(4);
5.     g.dodajPołączenia(0, 1, 2, 3);
6.     g.dodajPołączenia(1, 2);
8.     Console.WriteLine("Nie istnieją krawędzie:");
9.     for (int i = 0; i < 4; i++)
10.       for (int j = i + 1; j < 4; j++)
11.         if (!g.sprawdźKrawędź(i, j))
12.           Console.WriteLine("{0} z {1}", i, j);
14.     Console.ReadKey();
15.   }
16. }

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