ALG 9

116. Przeszukiwanie grafów    259

zwiedzaj(i)

(

zaznacz ’i' jako "zbadany";

dla każdego wierzchołka 'k' przyległego do 'i' jeśli 'k' nie był już zbadany zwiedzaj < k)

’

Uruchomienie programu poinformuje nas, że kolejność przeszukiwanych wierzchołków jest następująca: 0. /, 2, 6. 3, 4 i .5.

Lista wierzchołków przyległych do danego wierzchołka jest dla ułatwienia wypisana obok grafu. Zastanówmy się, czy jest to rzeczywiście przeszukiwanie „w głąb”. Zgodnie z pętlą/or zawartą w procedurze szukaj, pierwszym przeszukiwanym wierzchołkiem będzie 0 i on też zostanie jako pierwszy zaznaczony jako „zbadany” (1). Przylegają do niego trzy wierzchołki /, i, i 4 i dla nich zostanie kolejno wywołana procedura zwiedzaj (tym razem rckurcncyjnic). Wierzchołek 2 zostaje zaznaczony jako „zbadany”, a następnie badana jest lista wierzchołków przyległych do niego {(), 2 i 4). Ponieważ wierzchołek 0 został już wcześniej przebadany, to następnym będzie 2, dla którego ponownie zostanie wywołana procedura zwiedzaj. (Oczywiście, zanim to nastąpi, zostanie on zaznaczony jako „zbadany”). Wierzchołkami przyległymi do 2 są / i <5, ale ponieważ / został już zbadany, procedura zwiedzaj zostanie wywołana tylko dla 6 itd.

Postępując dalej tą drogą, można odtworzyć sposób pracy algorytmu przeszukiwania „w głąb” dla całego grafu.

10.6.2.Strategia „wszerz”

Do analizy przeszukiwania „wszerz” użyjemy takiego samego grafu jak w przykładzie poprzednim. Rysunek został jednak uzupełniony o elementy ułatwiające zrozumienie nowej idei przeszukiwania.

Listu wierzchołków przyległych:

Rys. 10- II.

Przeszukiwanie grafu.. wszerz

Załóżmy, że rozpoczynamy od wierzchołka 0. Na liście wierzchołków przyległych znajdują się kolejno: /, 3 i 4 i te właśnie wierzchołki zostaną jako pierwsze