Поиск в ширину (breadth-first search) графа

Лекция

Привет, сегодня поговорим про поиск в ширину, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое поиск в ширину, breadth-first search , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

поиск в ширину (англ. breadth-first search , BFS) — один из методов обхода графа.

Пусть задан граф $G=(V,E)$ и выделена исходная вершина $s$ . Алгоритм поиска в ширину систематически обходит все ребра $G$ для «открытия» всех вершин, достижимых из $s$ , вычисляя при этом расстояние (минимальное количество ребер) от $s$ до каждой достижимой из $s$ вершины. Алгоритм работает как для ориентированных, так и для неориентированных графов.

Поиск в ширину имеет такое название потому, что в процессе обхода мы идем вширь, т.е. перед тем как приступить к поиску вершин на расстоянии $k+1$ , выполняется обход вершин на расстоянии $k$ .

Поиск в ширину является одним из неинформированных алгоритмов поиска

Поиск в ширину (breadth-first search)

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

Пусть задан граф G = (V, Е) и выделена исходная (source) вершина S. Алгоритм поиска в ширину систематически обходит все ребра G для "открытия" всех вершин, достижимых из s, вычисляя при этом расстояние (минимальное количество ребер) от 5 до каждой достижимой из s вершины. Кроме того, в процессе обхода строится "дерево поиска в ширину" с корнем s, содержащее все достижимые вершины. Для каждой достижимой из s вершины v путь в дереве поиска в ширину соответствует кратчайшему (т.е. содержащему наименьшее количество ребер) пути от s до v в G.

Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина открывается (discovered) в процессе поиска, она окрашивается. Таким образом, серые и черные вершины - это вершины, которые уже были открыты. Если (u, v) є Е и вершина u черного цвета, то вершина v либо серая, либо черная, т.е. все вершины, смежные с черной, уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами.

Формальное описание

Входной граф G = (V, Е) представлен при помощи списков смежности. Цвет каждой вершины u є V хранится в переменной color [u], а предшественник - в переменной previous[u]. Если предшественника у u нет (например, если и == s или u не открыта), то previous[и] = NIL. Расстояние от s до вершины u, вычисляемое алгоритмом, хранится в поле d [u]. Алгоритм использует очередь Q для работы с множеством серых вершин.

В строках 1-4 все вершины, за исключением исходной вершины s, окрашиваются в белый цвет, для каждой вершины и полю d [u] присваивается значение infinity, а в качестве родителя для каждой вершины устанавливается nil. В строке 5 исходная вершина s окрашивается в серый цвет, поскольку она рассматривается как открытая в начале процедуры. В строке 6 ее полю d[s] присваивается значение 0, а в строке 7 ее родителем становится nil. В строках 8-9 создается пустая очередь Q, в которую помещается один элемент s.

Цикл while в строках 10-18 выполняется до тех пор, пока остаются серые вершины (т.е. открытые, но списки смежности которых еще не просмотрены).

В строке 11 определяется серая вершина и в голове очереди Q, которая затем удаляется из очереди. Цикл for в строках 12-17 просматривает все вершины v в списке смежности u. Если вершина v белая, значит, она еще не открыта, и алгоритм открывает ее, выполняя строки 14-17. Вершине назначается серый цвет, дистанция d [v] устанавливается равной d [u] + 1, а в качестве ее родителя указывается вершина u. После этого вершина помещается в хвост очереди Q. После того как все вершины из списка смежности и просмотрены, вершине и присваивается черный цвет.

Оценка сложности

После инициализации ни одна вершина не окрашивается в белый цвет, поэтому проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза. Операции внесения в очередь и удаления из нее требуют 0(1) времени, так что общее время операций с очередью составляет О (V). Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза. Oбщее время, необходимое для сканирования списков, равно 0(Е). Накладные расходы на инициализацию равны 0(V), так что общее время работы процедуры BFS составляет О (V + Е). Таким образом, время поиска в ширину линейно зависит от размера представления графа G с использованием списков смежности.

Пример

Порядок обхода дерева в ширину:

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

Пусть задан граф G=(V, E) и корень s, с которого начинается обход. После посещения узла s, следующими за ним будут посещены смежные с s узлы (множество смежных с s узлов обозначим как q; очевидно, что q⊆V, то есть q – некоторое подмножество V). Далее, эта процедура повториться для вершин смежных с вершинами из множества q, за исключением вершины s, т. к. она уже была посещена. Так, продолжая обходить уровень за уровнем, алгоритм обойдет все доступные из s вершины множества V. Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения наличествующего условия.

Рассматривая следующий пример, будем считать, что в процессе работы алгоритма каждая из вершин графа может быть окрашена в один из трех цветов: черный, белый или серый. Изначально все вершины белые. В процессе обхода каждая из вершин, по мере обнаружения, окрашивается сначала в серый, а затем в черный цвет. Определенный момент обхода описывает следующие условие: если вершина черная, то все ее потомки окрашены в серый или черный цвет.

Имеем смешанный граф (см. рис.) с |V| = 4 и |E| = 5. Выполним обход его вершин, используя алгоритм поиска в ширину. В качестве стартовой вершины возьмем узел 3. Сначала он помечается серым как обнаруженный, а затем черным, поскольку обнаружены смежные с ним узлы (1 и 4), которые, в свою очередь, в указанном порядке помечаются серым. Следующим в черный окрашивается узел 1, и находятся его соседи – узел 2, который становится серым. И, наконец, узлы 4 и 2, в данном порядке, просматриваются, обход в ширину завершается.

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

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

матрица смежности графа GM;
очередь queue;
массив посещенных вершин visited.

Две первые структуры имеют целочисленный тип данных, последняя – логический. Посещенные вершины, заносятся в массив visited, что предотвратит зацикливание, а очередь queue будет хранить задействованные узлы. Напомним, что структура данных «очередь» работает по принципу «первый пришел – первый вышел». Рассмотрим разбитый на этапы процесс обхода графа:

массив visited обнуляется, т. е. ни одна вершина графа еще не была посещена;
в качестве стартовой, выбирается некоторая вершина s и помещается в очередь (в массив queue);
вершина s исследуется (помечается как посещенная), и все смежные с ней вершины помещаются в конец очереди, а сама она удаляется;
если на данном этапе очередь оказывается пустой, то алгоритм прекращает свою работу; иначе посещается вершина, стоящая в начале очереди, помечается как посещенная, и все ее потомки заносятся в конец очереди;
пункт 4 выполняется пока это возможно.

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

Для реализации алгоритма на ЯП потребуется: умение программно задавать граф, а также иметь представление о такой структуре данных, как очередь.

Код программы на C++:

#include "stdafx.h"
#include
using namespace std;
const int n = 4;
int i, j;
// graph adjacency matrix
int GM [n] [n] =
{
{0, 1, 1, 0},
{0, 0, 1, 1},
{1, 0, 0, 1},
{0, 1, 0, 0}
};
// search wide
void BFS (bool * visited, int unit)
{
int * queue = new int [n];
int count, head;
for (i = 0; i count = 0; head = 0;
queue [count ++] = unit;
visited [unit] = true;
while (head {
unit = queue [head ++];
cout << unit + 1 << "";
for (i = 0; i if (GM [unit] [i] &&! visited [i])
{
queue [count ++] = i;
visited [i] = true;
}
}
delete [] queue;
}
// main function
void main ()
{
setlocale (LC_ALL, "Rus");
int start;
cout << "Starting Top >>"; cin >> start;
bool * visited = new bool [n];
cout << "Graph adjacency matrix:" << endl;
for (i = 0; i {
visited [i] = false;
for (j = 0; j cout << "" << GM [i] [j];
cout << endl;
}
cout << "Bypass order:";
BFS (visited, start-1);
delete [] visited;
system ("pause >> void");
}

Код программы на Pascal:

program BreadthFirstSearch;
uses crt;
const n=4;
type
MassivInt=array[1..n, 1..n] of integer;
MassivBool=array[1..n] of boolean;
var
i, j, start: integer;
visited: MassivBool;
{матрица смежности графа}
const GM: MassivInt = (
(0, 1, 1, 0),
(0, 0, 1, 1),
(1, 0, 0, 1),
(0, 1, 0, 0));
{поиск в ширину}
procedure BFS(visited: MassivBool; _unit: integer);
var
queue: array[1..n] of integer;
count, head: integer;
begin
for i:=1 to n do queue[i]:=0;
count:=0; head:=0;
count:=count+1;
queue[count]:=_unit;
visited[_unit]:=true;
while headbegin
head:=head+1;
_unit:=queue[head];
write(_unit, ' ');
for i:=1 to n do
begin
if (GM[_unit, i]<>0) and (not visited[i]) then
begin
count:=count+1;
queue[count]:=i;
visited[i]:=true;
end;
end;
end;
end;
{основной блок программы}
begin
clrscr;
write('Стартовая вершина >> '); read(start);
writeln('Матрица смежности графа: ');
for i:=1 to n do
begin
visited[i]:=false;
for j:=1 to n do
write(' ', GM[i, j]);
writeln;
end;
write('Порядок обхода: ');
BFS(visited, start);
end.

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

Входные данные	Выходные данные
1	1 2 3 4
2	2 3 4 1
3	3 1 4 2
4	4 2 3 1

Граф представлен матрицей смежности, и относительно эффективности это не самый лучший вариант, так как время, затраченное на ее обход, оценивается в O(|V|²), а сократить его можно до O(|V|+|E|), используя список смежности.

История и применения

Поиск в ширину был формально предложен Э. Ф. Муром в контексте поиска пути в лабиринте. Ли независимо открыл тот же алгоритм в контексте разводки проводников на печатных платах

Поиск в ширину может применяться для решения задач, связанных с теорией графов:

Волновой алгоритм поиска пути в лабиринте
Волновая трассировка печатных плат
Поиск компонент связности в графе
Поиск кратчайшего пути между двумя узлами невзвешенного графа
Поиск в пространстве состояний: нахождение решения задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — ребрами графа
Нахождение кратчайшего цикла в ориентированном невзвешенном графе
Нахождение всех вершин и ребер, лежащих на каком-либо кратчайшем пути между двумя вершинами $a$ и $b$
Поиск увеличивающего пути в алгоритме Форда-Фалкерсона (алгоритм Эдмондса-Карпа)

Вау!! 😲 Ты еще не читал? Это зря!

графы
поиск в глубину , depth-first search , обход графа ,

Алгоритмы поиска на графах
Неинформированные методы	Двунаправленный поиск Лучевой поиск Лексикографический поиск в ширину Поиск в ширину Поиск по критерию стоимости Поиск в глубину Поиск с возвратом Поиск восхождением к вершине Поиск с ограничением глубины Поиск в глубину с итеративным углублением
Информированные методы	Альфа-бета-отсечение Метод ветвей и границ Поиск по первому наилучшему совпадению A* B* D* Поиск точки перехода IDA* Рекурсивный поиск по первому наилучшему совпадению SMA*
Кратчайшие пути	Волновой алгоритм Алгоритм Беллмана — Форда Алгоритм Дейкстры Алгоритм Джонсона Алгоритм Левита Алгоритм Флойда — Уоршелла Поиск по краям
Минимальное остовное дерево	Алгоритм Борувки Алгоритм Прима Алгоритм Краскала
Другое	Алгоритм Британского музея Алгоритм Эдмондса Обход дерева Алгоритм ближайшего соседа в задаче коммивояжера

На этом все! Теперь вы знаете все про поиск в ширину, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое поиск в ширину, breadth-first search и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов