Поиск в ширину
Поиск в ширину (англ. breadth-first search, BFS) — один из методов обхода графа. Пусть задан граф [math]\displaystyle{ G = (V, E) }[/math] и выделена исходная вершина [math]\displaystyle{ s }[/math]. Алгоритм поиска в ширину систематически обходит все ребра [math]\displaystyle{ G }[/math] для «открытия» всех вершин, достижимых из [math]\displaystyle{ s }[/math], вычисляя при этом расстояние (минимальное количество рёбер) от [math]\displaystyle{ s }[/math] до каждой достижимой из [math]\displaystyle{ s }[/math] вершины. Алгоритм работает как для ориентированных, так и для неориентированных графов.[1]
Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии [math]\displaystyle{ k + 1 }[/math], выполняется обход вершин на расстоянии [math]\displaystyle{ k }[/math].
Поиск в ширину является одним из неинформированных алгоритмов поиска[2].
Работа алгоритма
Поиск в ширину работает путём последовательного просмотра отдельных уровней графа, начиная с узла-источника [math]\displaystyle{ u }[/math].
Рассмотрим все рёбра [math]\displaystyle{ (u,v) }[/math], выходящие из узла [math]\displaystyle{ u }[/math]. Если очередной узел [math]\displaystyle{ v }[/math] является целевым узлом, то поиск завершается; в противном случае узел [math]\displaystyle{ v }[/math] добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла [math]\displaystyle{ u }[/math], из очереди извлекается следующий узел [math]\displaystyle{ u }[/math], и процесс повторяется.
Неформальное описание
- Поместить узел, с которого начинается поиск, в изначально пустую очередь.
- Извлечь из начала очереди узел [math]\displaystyle{ u }[/math] и пометить его как развёрнутый.
- Если узел [math]\displaystyle{ u }[/math] является целевым узлом, то завершить поиск с результатом «успех».
- В противном случае, в конец очереди добавляются все преемники узла [math]\displaystyle{ u }[/math], которые ещё не развёрнуты и не находятся в очереди.
- Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
- Вернуться к п. 2.
Примечание: деление вершин на развёрнутые и не развёрнутые необходимо для произвольного графа (так как в нём могут быть циклы). Для дерева эта операция не нужна, так как каждая вершина будет выбрана один-единственный раз.
Формальное описание
Ниже приведён псевдокод алгоритма для случая, когда необходимо лишь найти целевой узел. В зависимости от конкретного применения алгоритма, может потребоваться дополнительный код, обеспечивающий сохранение нужной информации (расстояние от начального узла, узел-родитель и т. п.)
Рекурсивная формулировка:
BFS(start_node, goal_node) { return BFS'({start_node}, ∅, goal_node); } BFS'(fringe, visited, goal_node) { if(fringe == ∅) { // Целевой узел не найден return false; } if (goal_node ∈ fringe) { return true; } return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node); }
Итеративная формулировка:
BFS(start_node, goal_node) { for(all nodes i) visited[i] = false; // изначально список посещённых узлов пуст queue.push(start_node); // начиная с узла-источника while(! queue.empty() ) { // пока очередь не пуста node = queue.pop(); // извлечь первый элемент в очереди if(node == goal_node) { return true; // проверить, не является ли текущий узел целевым } visited[node] = true; // пометить текущую ноду посещенной foreach(child in expand(node)) { // все преемники текущего узла, ... if(visited[child] == false) { // ... которые ещё не были посещены ... queue.push(child); // ... добавить в конец очереди... visited[child] = true; // ... и пометить как посещённые } } } return false; // Целевой узел недостижим }
Реализация на Pascal:
function BFS(v : Node) : Boolean;
begin
enqueue(v);
while queue is not empty do
begin
curr := dequeue();
if is_goal(curr) then
begin
BFS := true;
exit;
end;
mark(curr);
for next in successors(curr) do
if not marked(next) then
begin
enqueue(next);
end;
end;
BFS := false;
end;
Свойства
Обозначим число вершин и рёбер в графе как [math]\displaystyle{ \vert V \vert }[/math] и [math]\displaystyle{ \vert E \vert }[/math] соответственно.
Пространственная сложность
Так как в памяти хранятся все развёрнутые узлы, пространственная сложность алгоритма составляет [math]\displaystyle{ O(\vert V \vert + \vert E \vert) }[/math][2].
Алгоритм поиска с итеративным углублением похож на поиск в ширину тем, что при каждой итерации перед переходом на следующий уровень исследуется полный уровень новых узлов, но требует значительно меньше памяти.
Временная сложность
Так как в худшем случае алгоритм посещает все узлы графа, при хранении графа в виде списков смежности, временная сложность алгоритма составляет [math]\displaystyle{ O(\vert V \vert + \vert E \vert) }[/math][2][3].
Полнота
Если у каждого узла имеется конечное число преемников, алгоритм является полным: если решение существует, алгоритм поиска в ширину его находит, независимо от того, является ли граф конечным. Однако если решения не существует, на бесконечном графе поиск не завершается.
Оптимальность
Если длины рёбер графа равны между собой, поиск в ширину является оптимальным, то есть всегда находит кратчайший путь. В случае взвешенного графа поиск в ширину находит путь, содержащий минимальное количество рёбер, но не обязательно кратчайший.
Поиск по критерию стоимости является обобщением поиска в ширину и оптимален на взвешенном графе с неотрицательными весами рёбер. Алгоритм посещает узлы графа в порядке возрастания стоимости пути из начального узла и обычно использует очередь с приоритетами.
История и применения
Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте[4]. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах[5][6][7].
Поиск в ширину может применяться для решения задач, связанных с теорией графов:
- Волновой алгоритм поиска пути в лабиринте[4]
- Волновая трассировка печатных плат[5]
- Поиск компонент связности в графе
- Поиск кратчайшего пути между двумя узлами невзвешенного графа
- Поиск в пространстве состояний: нахождение решения задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа[2]
- Нахождение кратчайшего цикла в ориентированном невзвешенном графе[2]
- Нахождение всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math][2]
- Поиск увеличивающего пути в алгоритме Форда-Фалкерсона (алгоритм Эдмондса-Карпа)
См. также
Примечания
- ↑ Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. — 3-е изд. — Издательский дом "Вильямс", 2013. — С. 630. — 1328 с. — ISBN 978-5-8459-1794-2 (рус.). — ISBN 978-0-2620-3384-8 (англ.).
- ↑ 2,0 2,1 2,2 2,3 2,4 2,5 MAXimal :: algo :: Поиск в ширину в графе и его приложения Архивная копия от 16 сентября 2013 на Wayback Machine
- ↑ 3,0 3,1 НГТУ Структуры и алгоритмы обработки данных Обход графа в ширину Архивная копия от 30 декабря 2012 на Wayback Machine
- ↑ 4,0 4,1 Шаблон:Source
- ↑ 5,0 5,1 C. Y. Lee (1961), An algorithm for path connection and its applications. IRE Transactions on Electronic Computers, EC-10(3), pp. 346–365
- ↑ Cormen et al, Introduction to Algorithms, 3rd edition, p. 623
- ↑ Mathematics Stack Exchange Origin of the Breadth-First Search algorithm
Литература
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. — 3rd edition. — The MIT Press, 2009. — ISBN 978-0-262-03384-8.. Перевод 2-го издания: Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
- Шаблон:Source