Главная » Java, Структуры данных и алгоритмы » Поиск в ширину для графа

0

В этом разделе рассматривается алгоритм поиска в ширину (breadth-first search — BFS). Как и в случае с поиском в глубину (DFS), поиск в ширину обходит связные компоненты графа и в процессе этого обхода определяет соответствующее остовное дерево. При этом поиск в ширину более предсказуем, чем поиск в глубину. Вместо путешествий по лабиринту графа BFS выполняет круговые обходы и распределяет узлы по уровням. BFS также можно рассматривать как поход с нитью и баллончиком краски, только в этом случае используется более консервативный способ разматывания нити.

Поиск в ширину начинается из узла s, расположенного на нулевом уровне и служащего местом привязки нити. При первом обходе разматываем нить на длину одного пути и проверяем только узлы, расположенные на расстоянии длины нити. В этом случае заходим в каждый смежный с s узел и маркируем его как пройденный. Теперь эти узлы образуют первый уровень. При втором заходе мы отматываем нить на длину двух путей и вновь проверяем все узлы, расположенные на расстоянии ее длины и не более. Эти новые узлы, смежные,с узлами первого уровня, но не вошедшие в него, формируют второй уровень. И так далее. BFS-обход заканчивается только после обследований всех узлов графа.

Псевдокод BFS-алгоритма показан во фрагменте кода 12.8. Здесь вспомогательные участки памяти используются для маркировки путей и узлов и для хранения контейнеров, ассоциируемых с уровнями. То есть контейнеры Lo, L\, Lj и так далее хранят узлы, расположенные в первом, втором, третьем и так далее уровнях. Например, контейнеры могут быть реализованы в виде очередей. Они также обеспечивают нерекурсивность алгоритма.

Алгоритм BFS(s):

Инициировать контейнер L0 для хранения узла s

/ <- О

while Lj не пустая do

создать контейнер L/+1 изначально пустой for каждого узла v в L, do

for каждого пути е, проходящего через v, do if путь е не пройден then

пусть w будет вторым конечным пунктом е if узел w не пройден then

отмаркировать е как прямой путь ввести w в L/ +1 else

отмаркировать е как пересекающийся путь

/<-/’+ 1 Фрагмент кода 12.8. BFS-алгоритм

Рис. 12.7. Пример обхода поиском в ширину, при котором сквозные пути узла расположены в алфавитном порядке. Открывающие пути выделены непрерывными линиями, поперечные пути показаны пунктиром: (а) граф до начала обхода; (Ъ) определение первого уровня; (с) определение второго уровня; (d) определение третьего уровня; (е) определение четвертого урорня; (f) определение пятого уровня

Удобным свойством такого подхода является возможность маркировки каждого узла длиной кратчайшего до него маршрута (по количеству путей) от узла отправления. В частности, если узел v алгоритм расположил на уровне / при начале движения от узла s, то длина кратчайшего маршрута от s до v маркируется как /.

Как и при поиске в глубину, можно представить работу алгоритма поиска в ширину, считая пути, ведущие в новые (непройденные) узлы, как открывающие пути, а ведущие в уже пройденные узлы — как поперечные пути (см. рис. 12.7, f). Как и ранее, открывающие пути формируют ос- товное дерево, которое будет называться BFS-деревом. Однако не вошедшие в дерево пути в этом случае не будут называться «обратными», поскольку ни один из них не связывает узел с его предшественником. Каждый не вошедший в дерево путь связывает узел v с другим узлом, который не является ни предшественником, ни потомком v.

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

Утверждение 12.7. Пусть G будет графом, в котором выполняется BFS-обход с началом в узле s. Тогда

•   обход обращается ко всем узлам связного компонента узла s\

•      открывающие пути образуют остовное дерево Г, которое называется BFS-деревом связного компонента узла s;

•      для каждого узла v уровня / маршрут BFS-дерева Гот s до v состоит из / путей, и любой другой маршрут графа G от s до v будет включать как минимум i путей;

•      если (m,v) является путем, не вошедшим в BFS-дерево, то номера уровней и и v отличаются друг от друга максимум на 1.

Доказательство этого утверждения авторы предоставляют сделать читателю в упражнении 3-12.13. Анализ времени выполнения BFS аналогичен анализу DFS, что предполагает верность нижеприведенного.

Утверждение 12.8. Пусть G — граф из п узлов и m путей, представленный структурой списка смежности. BFS-обход графа G выполняется за 0(п + т). времени. Кроме того, на основе BFS существует алгоритм со временем выполнения 0(п + т), применяемый для решения следующих задач:

Сравнение алгоритмов DFS и BFS

Согласно утверждению 12.8, BFS-обход может выполнять те же операции, что и DFS-обход. Но между ними имеется и ряд отличий, в частности, существуют задачи, с которыми каждый из методов справляется лучше другого. BFS-обход намного быстрее определяет кратчайший маршрут в графе (где расстояния измеряются количеством путей). К тому же он создает остовное дерево таким образом, что не вошедшие в него пути являются поперечными. DFS-обход решает сложные задачи взаимодействия, например, может ли каждая пара узлов в графе быть связанной двумя несмежными путями. Эти свойства, однако, применимы только в ненаправленных графах. Тем не менее, как видно из следующего раздела, и для направленных графов эти алгоритмы могут предложить некоторые решения.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии