Lista sąsiedztwa i macierzowa reprezentacja wykresu
Mimo że wyglądają inaczej, wszyscy rodzaje wykresów można przedstawić w podobny sposób. Generalnie istnieją dwa typy reprezentacji wykresów:
- Macierz sąsiedztwa
- Lista sąsiedztwa
Lista sąsiedztwa
Lista sąsiedztwa składa się z list połączonych. Każdy wierzchołek jest uważany za indeks tablicy, a każdy element reprezentuje połączoną listę. Te połączone listy zawierają wierzchołki, które mają krawędzie z wierzchołkiem indeksującym.
Oto przykład listy sąsiedztwa:
Załóżmy, że graf zawiera V liczbę wierzchołków i E liczbę krawędzi.
Ogólnie rzecz biorąc, złożoność kosmiczna będzie wynosić O(V + E)
.
Najgorsza złożoność przestrzenna wyniesie O(V2)
jeśli dany Wykres jest Grafem pełnym
Macierz sąsiedztwa
Macierz sąsiedztwa składa się z tablicy 2D. Wykres posiadający V liczbę wierzchołków będzie miał rozmiar macierzy VxV
.
Mówić, matrix[i][j] = 5
. Oznacza to, że pomiędzy węzłami i i j istnieje krawędź, której waga wynosi 5.
Przyjrzyjmy się poniższemu grafowi i jego macierzy sąsiedztwa:
Stworzyliśmy Tablica 2D korzystając z tych kroków:
Krok 1) Wierzchołek A ma bezpośrednią krawędź z B, a waga wynosi 5. Zatem komórki w wierszu A i kolumnie B zostaną wypełnione liczbą 5. Pozostałe komórki w wierszu A zostaną wypełnione zerem.
Krok 2) Wierzchołki B mają bezpośrednią krawędź z C, a waga wynosi 4. Zatem komórki w wierszu B i kolumnie C zostaną wypełnione liczbą 4. Pozostałe komórki w wierszu B zostaną wypełnione zerem, ponieważ B nie ma krawędzi wychodzącej do żadnej inne węzły.
Krok 3) Wierzchołki C nie mają bezpośrednich krawędzi z innymi wierzchołkami. Zatem wiersz C zostanie wypełniony zerami.
Krok 4) Wierzchołek D ma krawędź skierowaną z A i C.
- W tym przypadku komórki w wierszu D i kolumnie A będą miały wartość 7. Komórki w wierszach D i kolumnie C będą miały wartość 2.
- Pozostałe komórki w wierszu D zostaną wypełnione zerami.
Krok 5) Wierzchołki E mają skierowaną krawędź z B i D. Komórka w wierszu E i kolumnie B będzie miała wartość 6. Komórki w wierszu E i kolumnie D będą miały wartość 3. Pozostałe komórki w wierszu D będą wypełnione zerami.
Oto kilka punktów, na które warto zwrócić uwagę:
- Wykres nie ma pętli własnych, gdy główna przekątna macierzy sąsiedztwa wynosi 0.
- Graf jest grafem skierowanym, jeśli indeksy (a, b) i (b, a) nie mają tej samej wartości. W przeciwnym razie graf jest grafem skierowanym.
- Wykres będzie wykresem ważonym, jeśli wartość komórek będzie większa niż 1.
Występuje pewien problem z macierzą sąsiedztwa, ponieważ wymaga ona kwadratowych spacji. Tutaj przechowujemy krawędzie, które nie są połączone. Krawędzie te przydzielają miejsce w pamięci.
Przykładowo, jeśli mamy graf mający 100 węzłów, to potrzeba 10 tysięcy komórek, aby zapisać go w RAM. Przy mniejszej liczbie krawędzi w Grafie przydzielanie tak dużej pamięci może być marnotrawstwem. Tak więc złożoność przestrzeni przy użyciu macierzy sąsiedztwa będzie O(N2)
, gdzie N oznacza liczbę węzłów na Grafie.