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

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

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

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

Формальное описание     [вверх]

BFS(G, s)
1    for (для) каждой вершины u є V[G] — s
2           do color[u] «— WHITE
3                 d[u] «- infinity
4                 previous[u] «- NIL
5    Color[s] «— GRAY
6    d[s] «- 0
7    previous[s] «- NIL
8	Q - пустая очередь
9	Enqueue(Q, s)
10	while Q не пустая
11	        do u «— Dequeue(Q)
12	           for (для) каждой v є Adj[u]
13	                do if color[v] = white
14	                   then color[v] «— GRAY
15	                        d[v] «- d[u] + 1
16	                        prev[v] «— u
17	                        Enqueue(Q,v)
18	           color[u] «— BLACK

Входной граф 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 с использованием списков смежности.

Пример     [вверх ]

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

Визуализатор для алгоритма поиска в ширину.