На этом шаге мы приведем общие сведения по обходу графов.
Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа, такой что каждая вершина просматривается (посещается) в точности один раз. Поэтому важной задачей является нахождение хороших методов поиска в графе.
Под обходом графов (поиском на графах) мы будем понимать процесс систематического просмотра всех вершин графа с целью отыскания вершин, удовлетворяющих некоторому условию.
В.Липский [1, с.88] называет метод поиска "хорошим", если
- он позволяет алгоритму решения интересующей нас задачи легко "погрузиться" в этот метод и
- каждое ребро графа анализируется не более одного раза (или, что существенно не меняет ситуации, число раз, ограниченное константой).
Два наиболее распространенных алгоритма обхода графов называются:
- обход графа в глубину (поиск в глубину (англ. Depth First Search)) и
- обход графа в ширину (поиск в ширину (англ. Breadth First Search)).
(1) Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. - 213 с.
На следующем шаге мы рассмотрим обход графа в глубину.
