W poprzednim poście przedstawiłem z grubsza teorię grafów. Stworzyłem też zalążek implementacji tej struktury danych w JavaScripcie.
Dziś kontynuuję ten temat. Tym razem pokażę jak przeszukiwać grafy. Należy pamiętać, że w grafie przeszukiwanie nie tyle polega na odnalezieniu konkretnego wierzchołka, co na przeanalizowaniu jego układu krawędzi.
Algorytmy przeszukiwania grafów są dwa: przeszukiwanie w głąb (zwany df od ‚depth first’) i przeszukiwanie wszerz (zwany bf od ‚breadth first’). Różnią się one kolejnością analizowania krawędzi.
Depth first przechodzi z danego wierzchołka na sąsiedni wierzchołek z niego na kolejny sąsiedni i tak aż trafi na taki na którym już był lub na wierzchołek bez wyjścia, następnie wraca do oryginalnego wierzchołka i sprawdza kolejnego sąsiada.
Bredth first natomiast najpierw bada wszystkie sąsiadują (połączone) z danym wierzchołkiem elementy a następnie przechodzi na sąsiednie wierzchołki i sprawdza wszystkie ich sąsiednie wierzchołki i tak aż do końca.
To może przykładowy graf:
Przeszukiwanie w głąb, przejdzie przez graf najpierw badając jedną ścieżkę, a potem drugą. Kolejność badania wierzchołków to: A, H, G, F, B, E, D, C.
Przeszukiwanie wszerz przejdzie przez wierzchołki w następującej kolejności: A, H, B, G, E, C, F, D.
Zanim pokażę funkcje zawierające algorytmy przeszukiwania grafu, muszę dodać do mojej implementacji jeszcze jedną rzecz. Potrzebny jest mi system, dzięki któremu metody, będą mogły śledzić, które z wierzchołków były już przeanalizowane przez system, a które nie.
Mogę to zrobić w bardzo prosty sposób. Wystarczy do obiektu Graph dodać nowe pole – visited. Zawierać będzie one pustą tablicę. Gdy metoda przeszukiwania przejdzie przez jakiś wierzchołek, pod odpowiednim indeksem visited wstawiona zostanie wartość true.
Dobra, koniec gadania. Pierwsza nowa metoda obiektu Graph, to dfs. Metoda ta wykona na grafie przeszukiwanie w głąb. Oto jej kod:
|
1 2 3 4 5 6 7 8 9 10 11 |
this.dfs = function(v) { if (this.adjList[v] !== undefined) { console.log("Analizowany wierzchołek: " + v); } this.visited[v] = true; for (var i = 0; i < this.adjList[v].length; i++) { var next = this.adjList[v][i]; if (!this.visited[next]) { this.dfs(next); } } |
Metoda ta przyjmuje jeden parametr – identyfikator wierzchołka, od którego algorytm zacznie przeszukiwanie. Najpierw sprawdzam czy w tablicy zawierającej listy krawędzi, pod indeksem reprezentującym badany wierzchołek coś jest. Jeżeli nie ma, oznacza to, że dany wierzchołek nie jest z niczym połączony. W przeciwnym razie, przeprowadzam na nim odpowiednią operację, w tym wypadku po prostu wypisuję jego wartość. Kolejny krok to dodanie w tablicy visited pod indeksem reprezentując aktualny wierzchołek wartości true.
Następnie pętla for sprawdzam wszystkie sąsiednie dla danego wierzchołka wierzchołki. Jeżeli sprawdzany wierzchołek nie był wcześniej odwiedzany, odpalam rekurencyjnie tę samą metodę, która jako argument otrzymuje sprawdzany wierzchołek.
To rekurencyjne wywołanie powoduje, że algorytm przechodzi „w głąb” grafu, czyli analizuje jedną ścieżkę do końca, a następnie dopiero zaczyna przechodzić kolejną.
Inaczej, o czym wspominałem wcześniej, działa algorytm szukania wszerz. A oto kod odpowiedniej metody:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
this.bfs = function(v) { var queue = []; this.visited[v] = true; queue.push(v); while (queue.length > 0) { var curr = queue.shift(); if (curr !== undefined) { console.log("Analizowany wierzchołek: " + curr); } for (var i = 0; i < this.adjList[v].length; i++) { var next = this.adjList[curr][i]; if (!this.visited[next]) { this.visited[next] = true; queue.push(next); } } } } |
Jak widać, nie ma tutaj rekurencji. Zamiast tego, stosowany jest prosty system kolejki. Tak jak we wcześniejszym przypadku metoda przyjmuje jako argument identyfikator wierzchołka od którego zacząć ma się przeszukiwanie. Na początku funkcji, w zmiennej queue inicjalizowana jest pusta tablica. To kolejka, która przechowywać będzie identyfikatory wierzchołków, mających zostać przeanalizowane przez algorytm. Wierzchołek początkowy ustawiam jako odwiedzony a następnie wrzucam jego identyfikator do kolejki.
Następna część kodu to główny element algorytmu. Jest to pętla while, która działa dopóki w kolejce znajdują się jakieś wierzchołki. Najpierw do zmiennej reprezentującej aktualnie badany wierzchołek przypisuje pierwszy element z kolejki (przy okazji usuwam go z kolejki, dzięki działaniu metody tablicowej shift). Jeżeli element ten nie jest równy undefined, metoda przeprowadza na nim działanie (tym razem, również wypisanie w konsoli). Następnie wszystkie sąsiednie wierzchołki, które nie były jeszcze odwiedzane, wrzucane są do kolejki. W ten sposób pętla while, będzie działać tak długo, dopóki w grafie znajdują się niezbadane wierzchołki. Kolejność analizowania wierzchołków jest zależna od ich ustawienia w kolejce. A do kolejki trafiają najpierw najbliższe elementy aktualnie analizowanego. Proste 😉
Tak właśnie wyglądają algorytmy przeszukujące strukturę grafów. W następnym poście (ostatnim już o grafach), pokażę jak można wykorzystać te mechanizmy do bardziej przydatnych rzeczy takich jak odnajdywanie najkrótszych ścieżek między wierzchołkami czy sortowanie wierzchołków według ich połączeń.
Na koniec, jak zwykle, zachęcam do polubienia strony na facebooku. Zawsze na bieżąco zamieszczam tam informacje o nowościach na blogu, więc jakby ktoś bał się, że coś przegapi, to musi koniecznie ‚polajkować’ 😉