Cześć w 55 wpisie na blogu, gdzie poruszę temat grafów, czyli algorytm BFS (przeszukiwanie grafu wszerz). We wpisie dziesiątym poruszyłem temat przeszukiwania grafu w głąb, czyli algorytm DFS, który jest „bratem” dzisiejszego tytułowego algorytmu.

Temat grafów jest jednym z ciekawszych zagadnień w matematyce i informatyce, więc z przyjemnością do tych tematów wracam.

Dziś skupię się na następujących pytaniach:

  • Czym jest algorytm BFS?
  • Jak wygląda jego implementacja w języku Python?
  • Gdzie można go zastosować?
  • Jaka jest złożoność czasowa i pamięciowa algorytmu?

Pula pytań jest standardowa, więc zabieram się za omawianie.

Zaczynamy!

Wprowadzenie do BFS

Algorytm BFS (z angielskiego Breadth-first search) to algorytm, który przeszukuje grafy wszerz. Na temat grafów pisałem we wspomnianym artykule numer 10, więc tam Ciebie czytelniku odsyłam. 

Jedną z cech przechodzenia grafu jest to, by każdy wierzchołek i każdą krawędź przejść tylko jeden raz. Nie jest istotne, z którego wierzchołka startujemy oraz czy graf jest oznaczony, czy nie, ważne jest, by każdy wierzchołek oznaczać jako odwiedzony, a jego sąsiadów dodać na koniec kolejki. Algorytm BFS do prawidłowego działania używa kolejki FIFO.

Zobaczmy to na przykładzie poniżej.

Przechodzenie grafu wszerz
Rysunek 1. Przechodzenie grafu wszerz

Rysunek może nie jest zbyt estetyczny, ale najważniejsze, że pomoże zrozumieć Ci działanie, jakie niesie ze sobą algorytm BFS.

To, co możemy wywnioskować, patrząc na graf z kroku pierwszego, to to, że jest to graf nieskierowany. Krawędzie nie mają określonych kierunków w stronę wierzchołków. Przed przystąpieniem analizy powiem, że zielony kolor to umieszczone elementy na stosie, czerwone zdjęte ze stosu a białe oczekujące na umieszczenie na stosie. Zacznijmy analizę.

Krok 1

Zaczynamy od środkowej części grafu, wrzucamy na stos pierwszy wierzchołek o identyfikatorze 1.

Krok 2

Kolejnym krokiem jest sprawdzenie wszystkich sąsiadów wierzchołka numer 1, więc zaczniemy od góry – wierzchołek 2, 3 oraz 4. Następnie po sprawdzeniu wierzchołek numer 1 oznaczamy jako sprawdzony i zdejmujemy go ze stosu.

Krok 3

Na trzecim etapie wychodzimy z wierzchołka numer 2 i badamy jego wszystkich sąsiadów. Będą to wierzchołki 5, 3 oraz startowy wierzchołek 1. Wierzchołek numer 3 mamy na stosie, pierwszy został oznaczony jako sprawdzony, dlatego do stosu dodajemy jedynie wierzchołek numer 5.

Krok 4

W kroku czwartym przechodzimy do trzeciego wierzchołka, następnie sprawdzane są wszystkie sąsiadujące wierzchołki. Jest ich aż pięciu, z czego wierzchołek 1 oraz 2, już zostały zbadane i zdjęte ze stosu. Wierzchołki 6, 7 oraz 8 dodajemy do stosu. Po zbadaniu wszystkich krawędzi wierzchołek numer 3 usuwamy z listy i oznaczamy jako sprawdzony.

Krok 5

Na przedostatnim kroku na rysunku sprawdzamy wierzchołek numer 4. On również ma aż 5 krawędzi, jednak wierzchołki 1, 5 oraz 8 są już albo zbadane, albo oczekują na stosie na zbadanie. Dwóch nowych sąsiadów, których nie ma na liście to wierzchołek 9 oraz 10. więc dodajemy je do stosu.

Krok 6

W ostatnim kroku przeanalizujemy wierzchołka numer 5. Posiada on 4 sąsiadów, wierzchołek 2 oraz 4 są już przez nas zbadane i usunięte ze stosu. Wierzchołek numer 9 oczekuję na analizę. Czwartym wierzchołkiem jest wierzchołek 11, którego nie ma na stosie i nie był analizowany wcześniej, więc dodajemy go do stosu.

Pozostałe kroki od 7 do 12 pominąłem, ale każdy z tych kroków polega już tylko na tym, że nie dodajemy nowych sąsiadów do stosu, a jedynie oznaczamy jako sprawdzony i zdjęty ze stosu. W kroku ostatnim, czyli 12 zdejmujemy  ostatni element ze stosu i algorytm kończy swoje działanie. 

Powinny zostać zwrócone następujące wartości:  1 2 3 4 5 6 7 8 9 10 11 

Proste prawda?

Implementacja

Spróbujemy z użyciem języka Python 3 napisać prostą implementację algorytmu, gdzie najważniejszą częścią kodu będzie funkcja BFS, która przyjmuje na wejście numer wierzchołka, który będzie wierzchołkiem startowym.

Na początku zostaje stworzona lista visited a w niej wszystkie wierzchołki, które inicjalnie będą oznaczone jako nieoznaczone. Następnie na stos zostaje wrzucony pierwszy analizowany wierzchołek i oznaczany jako odwiedzony. 

Główna część funkcji to pętla While, która działa do momentu, aż queue nie będzie pusty.

Najpierw do zmiennej s ściągany jest z kolejki pierwszy element, zostaje on wypisany na ekran i w pętli for, z grafu, który został zbudowany przed wywołaniem funkcji BFS, następuje iteracja po wszystkich sąsiadach ściągniętego wierzchołka. Jeżeli sąsiad nie został jeszcze odwiedzony, to jest wciągany na stos i oznaczany jako odwiedzony.

Poza metodą BFS w klasie Graph jest jeszcze konstruktor oraz mała metoda addEdge, która pomaga w inicjalnym zbudowaniu grafu. Metody addEdge używam do tego, by dla każdego wierzchołka podać wszystkich jego sąsiadów. Poniżej pełna implementacja wraz z wynikami dla pierwszego i czwartego wierzchołka.

Jako zadanie dodatkowe, spróbuj rozrysować na wyżej przedstawionym rysunku dokładną kolejność, zaczynając od wierzchołka numer 4 i porównaj z wynikami z programu!

Pełna implementacja

from collections import defaultdict


class Graph:
    def __init__(self):
        self.graph = defaultdict(list)


    def addEdge(self, u, v):
        self.graph[u].append(v)


    def BFS(self, s):
        visited = [False] * (len(self.graph))

        queue = [s]

        visited[s] = True

        while queue:
            s = queue.pop(0)
            print(s + 1, end=" -> ")

            for i in self.graph[s]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True


g = Graph()

# Pierwszy wierzchołek
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(0, 3)

# Drugi wierzchołek
g.addEdge(1, 0)
g.addEdge(1, 2)
g.addEdge(1, 4)

# Trzeci wierzchołek
g.addEdge(2, 0)
g.addEdge(2, 1)
g.addEdge(2, 5)
g.addEdge(2, 6)
g.addEdge(2, 7)

# Czwarty wierzchołek
g.addEdge(3, 0)
g.addEdge(3, 4)
g.addEdge(3, 7)
g.addEdge(3, 8)
g.addEdge(3, 9)

# Piąty wierzchołek
g.addEdge(4, 1)
g.addEdge(4, 3)
g.addEdge(4, 8)
g.addEdge(4, 10)

# Szósty wierzchołek
g.addEdge(5, 2)
g.addEdge(5, 6)
g.addEdge(5, 10)

# Siódmy wierzchołek
g.addEdge(6, 2)
g.addEdge(6, 5)
g.addEdge(6, 9)

# Ósmy wierzchołek
g.addEdge(7, 2)
g.addEdge(7, 3)

# Dziewiąty wierzchołek
g.addEdge(8, 3)
g.addEdge(8, 4)

# Dziesiąty wierzchołek
g.addEdge(9, 3)
g.addEdge(9, 6)

# Jedenasty wierzchołek
g.addEdge(10, 4)
g.addEdge(10, 5)

print("Wynik dla pierwszego wierzchołka:")
g.BFS(0) # pierwszy wierzchołek
print("\nWynik dla czwartego wierzchołka:")
g.BFS(3) # czwarty wierzchołek


"""
Wynik dla pierwszego wierzchołka:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 
Wynik dla czwartego wierzchołka:
4 -> 1 -> 5 -> 8 -> 9 -> 10 -> 2 -> 3 -> 11 -> 7 -> 6 -> 
Process finished with exit code 0
"""

Podsumowanie kodu

Kod nie wydaje się skomplikowany, musisz go samodzielnie przeanalizować. Warto w tym miejscu zastanowić się jeszcze nad tym, jaka jest złożoność obliczeniowa i czasowa tego algorytmu, która wynosi O(|V| + |E|), gdzie |V| jest ilością wierzchołków, a |E| liczbą krawędzi (połączeń wierzchołków).

W najgorszym przypadku każdy wierzchołek mamy powiązany z każdym innym wierzchołkiem, a w najlepszym zaś jeden wierzchołek ma tylko jednego sąsiada.

Potrafisz wyobrazić sobie taki graf? 

Podsumowanie

Kolejny krótki artykuł i przyznam szczerze, że ta forma prezentowania tematów bardziej mi odpowiada niż długie artykuły, lecz nie oznacza to jeszcze, że dłuższe wpisy przestały się pojawiać.

Dodam jeszcze coś na temat zastosowania, ponieważ algorytm BFS jest bardzo popularny i  często wykorzystywany w wielu różnych, bardziej złożonych algorytmach, między innymi badania spójności czy algorytmy wyszukujące najkrótszą ścieżkę z punktu A do punktu B.

Jednym z ciekawszych algorytmów jest algorytm Dijkstry, o którym niedługo będę pisał dla jednego z zewnętrznych podmiotów i informacje wkrótce podam na Social Media!

I to by było na tyle, jeżeli chodzi o algorytm BFS.

Z racji mocno technicznego zagadnienia, polecam Ci książki na temat algorytmów!

PS. Będę wdzięczny za komentarze pod tym postem!

PS2. Czeka też na Ciebie prezent. Wystarczy, że zapiszesz się na Newsletter poniżej!

PS3. Dołącz do naszej grupy na Facebook!


Subskrybuj

Zapisz się na Newsletter, odbierz NAGRODĘ w postaci e-booka z 10 omówionymi algorytmami pojawiającymi się w pytaniach podczas REKRUTACJI..

Dodatkowo otrzymuj co niedzielę informacje na temat nowych wpisów, wiadomości ze świata IT i matematyki oraz ciekawych wydarzeniach. Nie przegap i dołącz już dziś do 942 osób!.

Źródła

http://ii.uwb.edu.pl/rudnicki/wp-content/uploads/2016/02/P14-DanielGolubiewski.pdf
http://staff.uz.zgora.pl/afiedoro/pliki/2016/lista3alg.pdf
http://antenor.pol.lublin.pl/users/gorgol/bfs-druk.pdf
http://smurf.mimuw.edu.pl/sites/default/files/DFS-BFS.pdf
http://www-users.mat.uni.torun.pl/~amroz/dydak/AiSD/grafy/wykladII.pdf
http://users.pja.edu.pl/~msyd/giz/bfs-dfs4.pdf
Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

1 Komentarz

  1. O grafach wiem bardzo niewiele więc nie wiem czy dobrze zrozumiałem treść tego artykułu. W Kroku 4 jesteśmy w punkcie 3 więc nie wiem jak możemy przejść do punktu 4 nie przechodząc wpierw przez punkt 1 lub punkt 8 co by łamało zasadę nie przechodzenia drugi raz przez daną krawędź.

    Chyba że w grafach możemy się „teleportować” do dowolnego punktu lub krawędzi z dowolnego punktu. Nie wiem, czy to możliwe.

    Fajnie by było, Mateusz, gdybyś dodał do komentarzy możliwość powiadomienia mnie jak by ktoś odpowiedział na mój komentarz. Teraz tego nie ma i jak na przykład ty odpisujesz na mój komentarz to o tym nie wiem, więc prawdopodobnie nie przeczytam twojej odpowiedzi.

    Pozdrawiam :-).

Napisz komentarz

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.