Nadszedł czas na kolejną strukturę danych. Tym razem będzie to graf. Warto poznać tę strukturę ponieważ jest ona naprawdę przydatna i często wykorzystywana. Popularnym przykładem mającym pomóc wyobrazić sobie graf jest siatka miast i łączących je dróg. Miasta to wierzchołki grafu a drogi to krawędzie je łączące.
Przykład bliższy komputerom to komputerowa sieć w domu czy na uczelni. Ją też możemy przedstawić jako graf. Wierzchołkami są wtedy podpięte do sieci urządzenia, a krawędzie to połączenia między nimi. Dzięki tej strukturze można przedstawić w łatwy sposób architekturę takiej sieci.
Grafy to bardzo szeroki temat, ja przedstawię tylko podstawy potrzebne do zrozumienia implementacji tej struktury oraz algorytmów potrzebnych do jej obsługi. Jak zawsze zachęcam do dalszego zgłębiania tematu na własną rękę 🙂
Jak już wspomniałem wyżej, graf składa się z wierzchołków oraz krawędzi. Krawędzie to połączeni pomiędzy wierzchołkami. Oto graficzna reprezentacja przykładowego grafu:
Koła to wierzchołki a łączące je kreski to krawędzie. Połączone jedną krawędzią wierzchołki to wierzchołki przylegające lub sąsiednie.
Najważniejsze informacje w grafie to wbrew pozorom nie wierzchołki a właśnie krawędzie. Dzięki nim wiadomo jak wygląda struktura grafu. Implementacja grafu musi skupiać się na dobrej ich reprezentacji.
Jeżeli chodzi o implementacje jest na to parę sposobów, każdy ma swoje wady i zalety i powinien być dobrany zależnie od sytuacji. Jednym ze sposobów to stworzenie ‚macierzy przylegalności’. Jest to tabelka, której rzędy i kolumny reprezentują wierzchołki. Jeżeli między danymi wierzchołkami znajduje się krawędź, w odpowiednim polu tabelki pojawia się 1, w przeciwnym razie znajduje się tam 0. Najlepiej zobaczyć to na przykładzie. ‚Macierz przylegalności’ dla powyższego grafu wyglądałaby tak:
Jak łatwo sobie wyobrazić, taką tabelkę da się zaprezentować dwuwymiarową tablicą. Na przykład wywołanie:
|
1 |
matrix[A][B] |
Zwróciłoby true, co oznaczałoby, że między tymi wierzchołkami istnieje połączenie.
Innym sposobem na implementacje grafu jest stworzenie ‚listy przylegalności’. Jest to lista, która dla każdego wierzchołka zawiera listę wierzchołków, które do niego przylegają. Przykład:
Właśnie z tej implementacji skorzystam. Dlaczego? Ponieważ mam wrażenie, że jest bardziej uniwersalna. Jeżeli na przykład graf posiada wiele wierzchołków ale minimalną ilość krawędzi, macierz w większości składałaby się z zer. To marnowanie pamięci 🙂 .
Lista zużywa tylko tyle pamięci ile potrzeba. Jednak tak jak pisałem wcześniej, wszystko zależy od sytuacji i od tego z jakim grafem ma się do czynienia. Oczywiście istnieją też inne sposoby na implementacje grafu. Po raz kolejny zachęcam do dalszego zgłębiania tematu na własną rękę.
Ok, czas na konkret. Dziś pierwszy etap implementacji grafu w JavaScripcie. Póki co, stworzę tylko podwaliny pod pełną strukturę. Będą tu odpowiednie mechanizmy na przechowywanie informacji, możliwość dodania danych do grafu, oraz wyświetlenia go.
Oto kod:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
function Graph(v) { this.vertices = v; this.edges = 0; this.adjList = []; for (var i = 0; i < this.vertices; ++i) { this.adjList[i] = []; } this.newEdge = function(v,w) { this.adjList[v].push(w); this.adjList[w].push(v); this.edges++; }; this.printGraph = function() { for (var i = 0; i < this.vertices; ++i) { var txt = "" txt += (i + ": "); for (var j = 0; j < this.vertices; ++j) { if (this.adjList[i][j] != undefined) txt+= (this.adjList[i][j] + ' '); } console.log(txt); } }; }; |
Konstruktor klasy Graph przyjmuje jeden argument, liczbę wierzchołków jakie zawierać będzie tworzony graf. W tej implementacji nie będzie możliwości zmiany ilości wierzchołków. Manipulować będzie można jedynie krawędziami.
W obecnej wersji konstruktor zawiera trzy pola: vertices, które przechowuje liczbę wierzchołków, edges, które przechowuje listę krawędzi oraz adjList, czyli ‚listę przyległości’.
Po polach znajduje się prosta pętla for. Służy ona do zainicjalizowania grafu i odpali się dla każdej nowo stworzonej instancji klasy. Ta pętla dodaje do tablicy adjList tyle elementów ile wierzchołków ma tworzony graf. Każdy wierzchołek będzie identyfikowany po indeksie tej tablicy. Pod każdym indeksem znajduje się kolejna tablica, będzie ona zawierała indeksy wierzchołków, do którego dany wierzchołek przylega.
wizualizacja takiego prostego, przykładowego grafu:
Wierzchołek podpisany zero to pierwszy element listy adjList. Pod tym indeksem znajduje się kolejna tablica i będzie ona zawierać dwa elementy: [1, 2]. To oznacza, że wierzchołek zero połączony jest dwoma krawędziami z wierzchołkami jeden oraz dwa. To w jaki sposób połączone są elementy trzeba zdefiniować. Służy do tego pierwsza metoda newEdge.
newEdge przyjmuje dwa argumenty. Są to wierzchołki, które mają zostać połączone. Aby stworzyć krawędź program do tablicy znajdującej się w adjList pod indeksem przekazanym w pierwszym argumencie, dodaje element o wartości drugiego argumentu. Następnie robi to samo czyli na odwrót, czyli do tablicy pod indeksem drugiego argumentu dodaje element o wartości pierwszego. W ten sposób powstaje krawędź grafu. Na koniec wartość pola edges jest inkrementowana.
ta metoda pozwala na tworzenie, różnych grafów składających się z tych samych wierzchołków. Tak jak zaznaczałem wcześniej, w tej strukturze liczą się połączenia między elementami. Te same wierzchołki, ale różne połączenia to inny graf.
Druga metoda, printGraph, służy jedynie do wypisania połączeń w konsoli. Dla każdego wierzchołka podawane są wierzchołki sąsiadujące.
Aby stworzyć graf, którego wizualizację pokazałem wcześniej, wystarczy wpisać do skryptu następujący kod:
|
1 2 3 4 5 6 |
var myGraph = new Graph(5); myGraph.newEdge(0,1); myGraph.newEdge(0,2); myGraph.newEdge(2,4); myGraph.newEdge(2,3); myGraph.newEdge(3,4); |
Wywołanie metody printGraph zwróci następujący wynik w konsoli:
|
1 2 3 4 5 |
0: 1 2 1: 0 2: 0 4 3 3: 2 4 4: 2 3 |
Działa jak trzeba 🙂 .
W obecnej formie struktura wydaje się być mało użyteczny ale w kolejnych postach przedstawię kolejne metody. Dadzą one możliwość między innymi przeszukiwania grafu, sortowania go oraz szukania najkrótszych połączeń pomiędzy wierzchołkami. Taka funkcjonalność jest już dużo bardziej przydatna.
Aby nie przegapić kolejnych postów, zachęcam do polubienia mojej strony na facebooku. Zawsze zamieszczam tam informacje o nowościach.