флеров

Поиск в графе

Будем далее рассматривать ориентированные и неориентированные графы без петель и кратных ребер, которые будем называть простыми.

Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа, такой, что каждая вершина просматривается в точности один раз. Поэтому важной задачей является нахождение хороших методов поиска в графе. Вообще говоря, метод поиска ”хороший”, если

1) он позволяет легко применить этот метод в алгоритме решения задачи (“погрузить” алгоритм решения нашей задачи в этот метод);

2) каждое ребро графа анализируется не более одного раза (или, что существенно не меняет ситуации, число раз, ограниченное константой).

Опишем теперь такой метод поиска в неориентированном простом графе, который стал одним из основных методов проектирования графовых алгоритмов. Этот метод называется методом поиска в глубину, по причинам, которые вскоре станут ясными.

Содержание