W poprzednim wykładzie poznaliśmy trzy metody systematycznego odwiedzania wierzchołków drzew binarnych. Wszystkie trzy były procedurami rekurencyjnymi. Teraz rozważymy dwa inne sposoby poruszania się po drzewach. Metody przedstawione w tym wykładzie mają tę zaletę, że można je stosować do dowolnych grafów. Najpierw rozważymy je jednak w zastosowaniu do drzew binarnych. Pierwsza z nich to przeglądanie grafu wszerz, a druga w głąb.

Metoda "wszerz"

Idea algorytmu polega na przeglądaniu wierzchołków drzewa poziomami i stąd angielska nazwa  Bredth First Search, w skrócie BFS. Zaczynamy od odwiedzenia korzenia drzewa. Następnie przeglądamy wierzchołki odległe od korzenia o jedną krawędź (tzn. następniki korzenia) np. od lewej do prawej. W kolejnym kroku przeglądamy wierzchołki odległe od korzenia o 2 krawędzie itd. Następniki odwiedzanych wierzchołków zapamiętujemy, aby móc je odwiedzić w następnym kroku, w takim samym porządku, w jakim byli odwiedzani ich ojcowie. Do tego celu użyjemy kolejki. Dzięki takiej organizacji, jeśli wierzchołek v był odwiedzony przed wierzchołkiem u, to synowie wierzchołka v też będą odwiedzeni przed synami wierzchołka u.

Algorytm BFS

Załóżmy, że q jest pustą kolejką o elementach typu node, a root jest korzeniem etykietowanego drzewa binarnego, którego wierzchołki chcemy odwiedzić.  Zakładamy, że każdy wierzchołek drzewa jest obiektem typu node, jaki opisano w wykładzie VI p.4. Użyta w algorytmie instrukcja write ma za zadanie wypisanie wartości zmiennej, która jest jej argumentem. W konkretnych zastosowaniach instrukcja ta jest zastępowana odpowiednim programem obsługi tego wierzchołka. Tu jednak chcemy się skupić jedynie na kolejności odwiedzania wierzchołków drzewa.

Przykład 1.1

Niech wartością zmiennej root będzie korzeń drzewa przedstawionego na rysunku 7.1(a) (tzn. wartością zmiennej root jest wierzchołek z etykietą 1). Algorytm BFS zastosowany do tego drzewa daje w wyniku następującą kolejność etykiet: 1,2,3,4,5,6,7,8,9. Aby prześledzić działanie algorytmu przyjrzyjmy się bliżej kolejnym stanom kolejki q (por. rysunek 7.1(b)). Na początku kolejka zawiera tylko korzeń drzewa. W kolejnych iteracjach (opisanych w kolejnych wierszach na rysunku 7.1(b)), wyjmujemy z kolejki pierwszy wierzchołek, wypisujemy jego etykietę, a do kolejki wkładamy synów tego wierzchołka, tzn. wierzchołki 2 i 3 są dopisane do końca kolejki. Ponieważ pierwszym wierzchołkiem w kolejce jest teraz 2, więc etykieta 2 zostanie wypisana, a do kolejki zostaną dopisani synowie wierzchołka 2, tzn. wierzchołki 4 i 5 . Teraz na początku kolejki znajduje się wierzchołek 3. Wypisujemy jego etykietę i usuwamy go z kolejki. Do kolejki natomiast dopisujemy synów wierzchołka 3, czyli 6 i 7. W kolejnym kroku na początku kolejki znajduje się wierzchołek 4. Do kolejki w  tym kroku nie dopiszemy nowych wierzchołków, bo wierzchołek 4 nie ma ani lewego, ani prawego syna itd.

											Kolejne stany kolejki q:
												1
												2	®	3
												3	®	4	®	5
												4	®	5	®	6	®	7
												5	®	6	®	7
												6	®	7
												7
												8	®	9
												9
													Rysunek 7.1(b)

Analiza poprawności algorytmu

Chcemy uzasadnić, że w algorytmie BFS wszystkie wierzchołki drzewa zostaną odwiedzone i wszystkie etykiety wypisane. Oczywiście korzeń drzewa jest odwiedzony, a jego etykieta zostanie wypisana jako pierwsza. Weźmy wierzchołek x na poziomie k tego drzewa i załóżmy, że wszystkie wierzchołki znajdujące się w tym drzewie na poziomach od 1 do k-1 zostały już wypisane. Niech y będzie ojcem wierzchołka x.  Skoro etykieta wierzchołka y została wypisana, to znaczy, że y znajdował się, w pewnym momencie, na początku kolejki q. Ale wtedy, do kolejki zostały dopisane następniki wierzchołka y, czyli w szczególności wierzchołek  x. W każdej iteracji pętli, usuwany jest jeden element z kolejki, zatem po skończonej liczbie kroków na początku kolejki znajdzie się wierzchołek x i wtedy zostanie wypisana jego etykieta.  Podobne rozumowanie można powtórzyć dla dowolnego wierzchołka z poziomu k, wynika stąd na mocy zasady indukcji, że wszystkie wierzchołki zostaną odwiedzone.

Do kolejki zawsze wpisujemy ojca przed synem, oraz najpierw wpisujemy lewy, a potem prawy następnik dowolnego wierzchołka. Wynika stąd, że zgodnie z własnościami kolejki, najpierw zostaną wypisane wierzchołki bliższe korzeniowi (z poziomów o mniejszych numerach), a potem bardziej odległe od korzenia. Co więcej  na początku kolejki pojawi się lewy następnik dowolnego wierzchołka, a dopiero po jego usunięciu, prawy. Zatem ich etykiety też pojawią się w takiej kolejności.

Koszt algorytmu BFS

Każdy wierzchołek drzewa o korzeniu root jest tylko raz wpisywany do kolejki i tylko raz z niej usuwany, gdy stanie się pierwszym elementem kolejki. Wynika stąd, że liczba iteracji pętli "while" jest równa liczbie wierzchołków drzewa. Zatem koszt algorytmu BFS, mierzony liczbą wykonanych operacji na kolejce wynosi Q(n), gdzie n jest liczbą wierzchołków drzewa.

Pytanie 1: Niech root będzie korzeniem drzewa binarnego o wysokości h. Do wypisania etykiet tego drzewa użyto algorytmu BFS. Ile co najwyżej elementów może znajdować się równocześnie w kolejce q? 

Metoda "najpierw w głąb"

Idea tego algorytmu polega na przeglądaniu wierzchołków drzewa wzdłuż gałęzi od korzenia do liści drzewa, jak wskazuje nazwa Depth First Search, w skrócie DFS. Przesuwamy się najpierw wzdłuż, np. lewej gałęzi, przechodząc stale do lewego następnika. Gdy kontynuowanie przejścia w lewo nie jest możliwe, zaczynamy przeglądać prawe poddrzewo ostatnio odwiedzonego wierzchołka. Zapamiętujemy mijane wierzchołki, aby móc później odwiedzić ich prawe poddrzewa. Użyjemy do tego celu struktury stosu.

Algorytm DFS

Załóżmy, że s jest stosem początkowo pustym, a root jest korzeniem drzewa binarnego.

Przedstawiony algorytm niewiele się różni od algorytmu BFS. Podstawowa różnica to typ użytej struktury pomocniczej. Zauważmy też, że na stos dostaje się zawsze najpierw  prawy następnik, a potem lewy.  Nie ma to wielkiego znaczenia, ale umożliwia przeglądanie wierzchołków od strony lewej w kierunku prawej. Pamiętajmy, że porządek wkładania elementów na stos jest odwrotny do porządku ich zdejmowania ze stosu.

Przykład 1.2

Rozważmy drzewo z przykładu 7.1(a). Na rysunku 7.2 przedstawiliśmy kolejne stany stosu s w trakcie wykonywania algorytmu DFS. Na początku do stosu jest włożony korzeń drzewa. W pierwszym kroku pętli wypisujemy jego etykietę i usuwamy go. Do stosu natomiast wpisujemy jego synów: najpierw prawego syna, a potem lewego. Dzięki temu, to właśnie lewy następnik, wierzchołek 2 jest na szczycie stosu w następnym kroku. Po wypisaniu jego etykiety usuwamy go ze stosu, a na jego miejsce wpisujemy następniki: wierzchołek 5 i wierzchołek 4. Teraz na szczycie stosu znajduje się wierzchołek 4, itd

Analiza poprawności algorytmu

Zauważmy najpierw, że algorytm zatrzymuje się po skończonej liczbie iteracji. Rzeczywiście, wierzchołek raz usunięty ze stosu nigdy na ten stos ponownie nie wraca. Drzewo ma skończoną liczbę wierzchołków, więc po skończonej liczbie iteracji wszystkie wierzchołki zostaną usunięte ze stosu. Trzeba jeszcze uzasadnić, że każdy wierzchołek zostanie odwiedzony (tzn. znajdzie się na szczycie stosu), a  ciąg otrzymany w wyniku zawiera wszystkie etykiety tego drzewa. Jeśli jakiś wierzchołek został wpisany na stos, to po skończonej liczbie kroków znajdzie się on na szczycie stosu, a jego etykieta zostanie wypisana.  Gdyby wierzchołek x należał do drzewa o korzeniu  root, ale nie był odwiedzony w algorytmie DFS, to ojciec tego wierzchołka, nazwijmy go y, nie mógłby być wpisany na stos (w przeciwnym bowiem razie, po skończonej liczbie kroków byłby on na szczycie stosu, a wtedy do stosu, zgodnie z instrukcjami algorytmu, wpisano by jego następniki, czyli również x). Podobnie ojciec wierzchołka y też nie mógł być wpisany na stos w procesie DFS. Wynika sąd, że żaden poprzednik wierzchołka x na ścieżce od korzenia do x,  nie mógłby być wpisany na stos. Prowadzi to do sprzeczności, bo root jest wkładany na stos jako pierwszy element.

Jest oczywiste, że wierzchołki, które są właśnie dopisane do stosu zostaną odwiedzone wcześniej niż te, które na tym stosie już się znajdują. Jeśli w pewnej chwili wierzchołek x znajdzie się na szczycie stosu, to zostanie usunięty, a na jego miejsce zostaną wpisani jego synowie: najpierw prawy syn, a potem lewy. Wynika stąd, że następnym odwiedzonym wierzchołkiem będzie lewy syn wierzchołka x, a do stosu zostaną dopisane jego następniki. Ostatecznie, zanim prawy syn wierzchołka x znajdzie się na szczycie stosu, zostaną odwiedzone wszystkie wierzchołki z lewego poddrzewa wierzchołka x. 

 Koszt algorytmu

Każdy wierzchołek drzewa jest dokładnie raz wkładany na stos i usuwany z niego, gdy znajdzie się na szczycie stosu. Wynika stąd, że liczba operacji na stosie jest proporcjonalna do liczby wierzchołków drzewa  n i wynosi  Q(n).

Pytanie 2: Ile co najwyżej elementów może się znajdować równocześnie na stosie w trakcie przeglądania drzewa binarnego o wysokości h za pomocą algorytmu DFS?

Idea przeglądania wierzchołków drzewa "wszerz " i "w głąb" może zostać uogólniona na dowolne grafy. Warto zapamiętać obie te metody, gdyż będą przez nas wykorzystywane w innych ważnych algorytmach na grafach.  Niech r będzie ustalonym wierzchołkiem grafu G, zwanym źródłem. Przeglądanie "wszerz" oznacza, że najpierw odwiedzamy wszystkie te wierzchołki x, dla których istnieje ścieżka od źródła o długości i, a potem te bardziej oddalone od źródła, dla których najkrótsza ścieżka od źródła ma długość i+1. Przeglądanie "w głąb" oznacza, że idziemy wzdłuż jednej ścieżki tak daleko, jak to jest możliwe (oddalając się stale od źródła). Jeśli napotkamy wierzchołek, którego wszystkie następniki były już odwiedzone, lub wierzchołek, który nie ma następników, wykonujemy krok powrotny, szukając pierwszego wierzchołka, z którego prowadzi inna droga w głąb grafu. Jeśli graf jest niezorientowany, to przeglądanie "wszerz" lub "w głąb" pozwalają odwiedzić tylko tę spójną część grafu, w której znajduje się źródło. Odwiedzanie trzeba powtórzyć dla każdej spójnej części grafu, jeśli nie wszystkie wierzchołki zostały jeszcze odwiedzone.

Niech G = <V, E, et> będzie niezorientowanym, prostym, etykietowanym grafem spójnym, a w jego wyróżnionym wierzchołkiem.  Zakładamy, że wierzchołki grafu są ponumerowane liczbami naturalnymi od 1 do n oraz TAB jest tablicą list incydencji tego grafu. Niech źródłem będzie wierzchołek o numerze w. Dla dowolnego v, TAB[v] wskazuje pierwsze ogniwo listy incydencji wierzchołka v. Każde ogniwo ma atrybut next, który wskazuje następny element listy (por. wykład VI p.3). Dodatkowo, booleowska tablica InQueue wskazuje, czy wierzchołek był już wpisany do kolejki, czy też nie. Ta informacja pozwala uniknąć ponownego wpisania tego samego wierzchołka do kolejki, a co za tym idzie pozwala uniknąć zapętlenia. Tak jak poprzednio, zakładamy, że kolejka q służy do przechowywania wierzchołków grafu i jest początkowo pusta. Algorytmy BFS  można zapisać następująco: