Поиск в глубину и в ширину

Важными задачами теории графов являются задачи глобального анализа графов. К таким задачам относятся, например, задачи поиска циклов, вычисление длин путей между парами вершин, перечисление путей с теми или иными свойствами и т.п. Например, для нахождения эксцентриситета вершины необходимо найти все расстояния от данной вершины до остальных и выбрать максимальное. Глобальный анализ графа следует отличать от локального, примером которого может служить задача определения множеств предшественников и преемников фиксированной вершины ориентированного графа. Необходимо уметь обходить все вершины графа так, чтобы каждая вершина была помечена ровно один раз. Обычно такое путешествие по графу сопровождается нумерацией проходимых вершин и рёбер. — Т.е. при обходе графа происходит некоторое систематическое перечисление его вершин (и/или рёбер). Существуют две основные стратегии обхода вершин, называемые поисками в ширину и в глубину. Алгоритмы поисков в глубину и в ширину лежат в основе многих алгоритмов на графах.

Понятие обхода вершин/рёбер предполагает однозначность маршрута – т.е. в обходе не должно быть циклов. Другими словами, обход графа совершается по некоторому остовному дереву. Предположим, нам известно это дерево. Назначим тогда начальную вершину корнем дерева. После этого все остальные вершины расположатся по ярусам (этажам) дерева. — Так, сразу будет решена задача определения эксцентриситета вершины и расстояний от данной вершины до произвольной. Путешествовать по дереву также можно разными способами.

Первый способ: выйдя на вершину в некотором ярусе и обработав её, спускаемся по некоторому ребру на следующий ярус; после обработки вершины спускаемся снова и т.д. Если доходим до листа – возвращаемся наверх на один ярус и ищем ребро, по которому ещё не спускались. Если такого ребра нет, поднимаемся ещё на ярус и т.д. Это идея алгоритма поиска в глубину.

Второй способ: выйдя на вершину в некотором ярусе и обработав её, переходим к следующей вершине того же яруса. Таким образом обрабатываем все вершины данного яруса и только после этого переходим к обработке вершин следующего уровня. Это идея алгоритма поиска в ширину.

Возможны и комбинация алгоритмов: на некоторых этажах «ныряем» вглубь, на других «чистим» весь этаж.

В действительности оба алгоритма не используют готовое дерево обхода, а строят его в процессе работы. Построенное остовное дерево обхода является одним из результатов работы алгоритма – фактически это протокол работы алгоритма. В протоколе каждой вершине присваивается номер в порядке её посещения. Очерёдность обхода вершин зависит от расположения вершин в динамической памяти S (структуре данных).

Оба алгоритма работают со списками смежности графа.

Всё различие в работе алгоритмов заключается в том, как организована динамическая память S. Если S – это стек (LIFO – Last In First Out), то обход будет поиском в глубину. Если S – это очередь (FIFO – First In First Out) – то получается поиск в ширину.

На вход алгоритма подаётся граф G(V, E), заданный списком смежности вершин.

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

Рассмотрим работу алгоритмов на следующих примерах. Предполагается, что вершины в списках упорядочены по номерам.

Результат работы алгоритмов:

а) дерево поиска Tree;

б) массив номеров вершин в порядке прохождения;

в) массив родителей p(v);

г) множество хорд (обратных рёбер) (= кодерево) Back= E\Tree, BackÈTree=Æ;

д) векторное пространство фундаментальных циклов Cycle;

е) массив расстояний до вершин и т.д....

При поиске на орграфе вместо множества хорд могут появиться рёбра разных типов:

а) древесные – отец ¦ сын;

б) прямые – предок ¦ потомок;

в) обратные – потомок ¦ предок;

г) поперечные – все остальные, не связанные «родством».

При поиске в ширину происходит сортировка вершин по ярусам – это есть ни что иное как минимальное расстояние между данной вершиной и корневой. Если поиск происходит во взвешенном графе, то возникает естественная сортировка не только по ярусам, но и по расстояниям. Такой поиск называется алгоритмом волнового фронта. При работе алгоритма дополнительно формируется массив «обратных вершин», составляющих в совокупности кратчайшие пути от корневой вершины до всех прочих.

Сложность алгоритмов поиска в глубину и в ширину составляет O(max(|E|, |V|).