40. Алгоритмы обхода графа. Поиск в ширину (волновой алгоритм).

При решении многих задач, касающихся графов, необходимы эффективные методы систематического обхода вершин и ребер графов. К таким методам относятся:

– поиск в глубину;

– поиск в ширину.

Поиск в ширину (волновой алгоритм)

Этот алгоритм поиска в графе также называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны. Волна растекается равномерно во все стороны с одинаковой скоростью. На i-м шаге будут помечены все вершины, достижимые за i ходов, если ходом считать переход из одной вершины в другую.

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

Здесь используются те же структуры Graph и Visited, что и в алгоритме поиска в глубину.

Поиск в ширину для полного обхода графа с n вершинами и m дугами требует столько же времени, как и поиск в глубину, т. е. времени порядка O(max(n, m)). Поскольку обычно m ≥ n, то получается O(m).