Przeszukiwanie Wszerz (BFS)

Cel

Algorytm przeszukiwania grafu wszerz (BFS) może służyć do sprawdzenia czy dany graf jest spójny, albo do znalezienia najkrótszej drogi pomiędzy dwoma wybranymi wierzchołkami grafu. Bardzo często jest on również wykorzystywany do sprawdzenia czy dany graf jest dwudzielny.

Algorytm

Algorytm Poszukiwania Wszerz wymaga określenia punktu początkowego oraz przypisania każdemu wierzchołkowi dwóch właściwości: odległość o wartości początkowej nieskończoność, oraz poprzednik, który początkowo jest pusty. Wyjątkiem jest punkt startowy, którego odległość początkowa wynosi 0. Początkowo kolejka składa się tylko z punktu początkowego.

Dopóki kolejka nie jest pusta pobieramy pierwszy jej element (usuwając go z kolejki). Następnie sprawdzamy, który z jego sąsiadów nie został odwiedzony tzn. nie ma ustawionego poprzednika. Sąsiadów wybieramy alfabetycznie (lub rosnąco) jeśli nie zostało wskazane inaczej w zadaniu. Dla każdego nieodwiedzonego dotychczas sąsiada ustawiamy odległość na odległość wybranego elementu z kolejki i dodajemy wagę krawędzi (dla grafu bez wag przyjmujemy 1) i ustawiamy poprzednika na aktualnie wybrany element. Algorytm kończy się, gdy kolejka będzie pusta.

Przykład

Przypuśćmy, że mam następujący graf:

Punktem początkowym jest zaznaczony punkt A. W tabeli została przedstawiona aktualna kolejka oraz właściwości poszczególnych obiektów:

Z tabeli można wyczytać, że w odległości 1 od punktu początkowego A znajdują się węzły B, C oraz D, a w odległości 2 węzły E, F. Warto zwrócić uwagę, że do punktu F można dojść w drogą tej samej długości idąc kolejno A > C > F, albo A > D > F. Punkty G i H nie zostały odwiedzone, więc nie istnieje żadna droga do nich z węzła A. To świadczy również o tym, że graf nie jest spójny.

Implementacja

Napisz funkcję BFS, która na podstawie podanej macierzy sąsiedztwa oraz początkowego wypisze tablice z informacjami jak daleko jest z punktu początkowego do danego i który węzeł jest poprzednikiem. Przetestuj działanie funkcji.

Rozwiązanie

Wynik

Dane dotyczące węzła tj. jego odległość oraz poprzednik będą przechowywane w specjalnym typie.

1. class dane(object):
2.   def __init__(self, dl, p):
3.     self.odległość = dl
4.     self.poprzednik = p

Dane dotyczące węzła tj. jego odległość oraz poprzednik będą przechowywane w specjalnym typie.

Funkcja BFS

Oto przykładowe rozwiązanie funkcji realizującej algorytm BFS.

1. def BFS(macierz, start):
2.   tab = []
3.   for i in range(0, len(macierz)):
4.     tab.append(dane(sys.maxsize, -1))
5.   tab[start].odległość = 0;
6.   q = queue.Queue()
7.   q.put(start)
8.   while (not q.empty()):
9.     u = q.get()
10.     for i in range(0, len(macierz)):
11.       if (macierz[u][i] > 0 and tab[i].odległość == sys.maxsize):
12.         tab[i].odległość = tab[u].odległość + 1
13.         tab[i].poprzednik = u
14.         q.put(i)
15.   return tab

(2. - 4.) Przygotuj tabelę na zapis informacji o przejściach i (5.) oznacz punkt początkowy. Następnie (6.) utwórz kolejke i (7.) włóż do niej węzeł początkowy. (8.) Dopóki kolejka nie jest pusta (9.) pobierz pierwszy element z kolejki i (10.) rozpocznij sprawdzanie jego sąsiadów. Jeśli (11.) krawędź do sąsiada istnieje i nie był odwiedzony to (12. - 13.) odwiedź go i (14.) dołącz na koniec kolejki.

Testowanie funkcji

Do przetestowania napisanej funkcji można skorzystać z poniższego fragmentu kodu, który wczytuje od użytkownika potrzebne dane, a następnie wypisuje odpowiednio sformatowany wynik.

1. n = int(input("Podaj ile węzłów ma graf\n n = "))
2. s = int(input("Podaj węzeł startowy\n s = "))
3. print("Podaj elementy macierzy:")
4. macierz = []
5. for i in range(0, n):
6.   tab = [int(x) for x in input().split()]
7.   macierz.append(tab)
8.  
9. tab = BFS(macierz, s)
10. for i in range(0, n):
11.   wypiszDane(i, tab[i])

Do ładnego sformatowania danych dotyczących węzła została dopisana funkcja wypiszdane(). Rozpoznaje ona niektóre wartości domyślne i na tej podstawie wyświetla odpowiedni opis zamiast liczb.

1. def wypiszDane(i, d):
2.   txt = str(i) + "\t"
3.   if (d.odległość == sys.maxsize):
4.     txt += "nieosiągalny"
5.   else:
6.     txt += str(d.odległość) + "\t"
7.     if (d.poprzednik == -1):
8.       txt += "brak"
9.     else:
10.       txt += str(d.poprzednik)
11.   print(txt);

W celu przetestowania grafu przedstawionego w przykładzie należałoby podać n = 8, s = 0 oraz wpisać nastepującą macierz:

1. 0  1  1  1  0  0  0  0
2. 1  0  0  0  1  0  0  0
3. 1  0  0  0  0  1  0  0
4. 1  0  0  0  0  1  0  0
5. 0  1  0  0  0  1  0  0
6. 0  0  1  1  1  0  0  0
7. 0  0  0  0  0  0  0  1
8. 0  0  0  0  0  0  1  0

• Kod źródłowy Implementacja