ALG 7

10,5. Algorytm Floyda_257

10.6.Przeszukiwanie grafów

Dużo interesujących zadań algorytmicznych, w których użyto grafu do modelowania pewnej sytuacji, wymaga systematycznego przeszukiwania grafu, „ślepego” lub kierującego się pewnymi zasadami praktycznymi (tzw. heurysty-kami). W szczególności temat ten jest przydatny w'e wszelkich zagadnieniach związanymi z tzw'. teorią gier. ale do tej kwestii jeszcze powrócimy w rozdziale 12. Teraz skupimy się na dwóch najprostszych technikach przechadzania się po grafach: strategii „w głąb” (ang. depth first) i strategii „wszerz” (ang. breadth first). Analizując przykłady, będziemy się koncentrować na samym procesie przeszukiwania. bez zastanawiania się znad jego celowością. Pamiętajmy zatem, że w ostateczności przeszukiwanie grafit nut „czemuś" służyć: odnaleźć optymalną strategię gry, rozwiązać łamigłówkę lub konkretny problem techniczny przedstawiony przy pomocy grafów...

Uwaga: nasze przykłady będą używały wyłącznie reprezentacji tablicowej grafów Zabieg ten pozwala na uproszczenie prezentowanych przykładów, ale należy pamiętać, że nie jest to jedyna możliwa reprezentacja! W przypadku algorytmów przeszukiwania dla bardzo dużych grafów użycie tablic jest niemożliwe. Jedynym wyjściem w takiej sytuacji jest użycie reprezentacji popartej na słowniku węzłów. Wiąże się z tym modyfikacja wspomnianych algorytmów, zatem dla ułatwienia zostaną również podane w pseudo-kodzie, tak aby możliwe było ich przepisanie na użytek kon-kretnej struktury danych. _

10.6.1.Strategia „w głąb”

Nazwa tytułowej techniki eksploracji grafów jest związana z topologicznym kształtem ścieżek, po których się przechadzamy podczas badania grafu. Algorytm przeszukiwania „w głąb” bada daną drogę, aż do jej całkowitego wyczerpania (w przeciwieństwie do algorytmu „wszerz”, który najpierw bada wszystkie poziomy grafu o jednakowej głębokości)¹. Jego cechą przewodnią jest zatem maksymalnii eksploatacja raz obranej drogi, przed ewentualnym wybraniem następnej.

Rysunek 10 - 10. przedstawia niewielki graf, który posłuży nam za ilustrację problemu.

W naszej dotychczasowej dyskusji na temat grafów nie używaliśmy, co prawda, zacytowanej powyżej terminologii, ale jej znaczenie powinno się szybko wyjaśnić podczas analizy konkretnych przykładów.