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