Обход в ширину

Обход в ширину (Поиск в ширину, BFS, Breadth-first search) — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами. Например, алгоритм Прима поиска минимального остовного дерева или алгоритм Дейкстры поиска кратчайшего пути из одной вершины используют идеи, сходные идеям, используемым при поиске в ширину.

Алгоритм

Общая идея

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

Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина открывается в процессе поиска, она окрашивается. Таким образом, серые и черные вершины — это вершины, которые уже были открыты, но алгоритм поиска в ширину по-разному работает с ними, чтобы обеспечить объявленный порядок обхода. Если [math](u, v) \in E[/math] и вершина [math]u[/math] черного цвета, то вершина [math]v[/math] либо серая, либо черная, т.е. все вершины, смежные с ней уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами.

Поиск в ширину строит дерево поиска в ширину, которое изначально состоит из одного корня, которым является исходная вершина [math]s[/math]. Если в процессе сканирования списка смежности уже открытой вершины [math]u[/math] открывается белая вершина [math]v[/math], то вершина [math]v[/math] и ребро [math](u, v)[/math] добавляются в дерево. При этом [math]u[/math] является предшественником (predecessor), или родителем (parent), [math]v[/math] в дереве поиска в ширину. Поскольку вершина может быть открыта не более одного раза, она имеет не более одного родителя.

Реализация

Приведенная ниже процедура поиска в ширину BFS предполагает, что входной граф [math]G = (V, E)[/math] представлен при помощи списков смежности. Кроме того, поддерживаются дополнительные структуры данных в каждой вершине графа. Цвет каждой вершины [math]u \in V[/math] хранится в переменной [math]color[u][/math], а предшественник — в переменной [math]p[u][/math]. Если предшественника у [math]u[/math] нет, то [math]p[u] =[/math] NIL. Расстояние от [math]s[/math] до вершины [math]u[/math], вычисляемое алгоритмом, хранится в поле [math]d[u][/math]. Алгоритм использует очередь [math]Q[/math] для работы с множеством серых вершин.

BFS([math]G[/math], [math]s[/math])
  1  for (для) каждой вершины [math]u \in V[G][/math]
  2    do  [math]color[u] \leftarrow[/math] WHITE
  3      [math]d[u] \leftarrow \mathcal {1}[/math]
  4      [math]p[u] \leftarrow[/math] NIL
  5  [math]color[s] \leftarrow[/math] GRAY
  6  [math]d[s] \leftarrow 0[/math] 
  7  [math]p[s] \leftarrow[/math] NIL
  8  [math]Q \leftarrow \varnothing[/math] 
  9  ENQUEUE([math]Q[/math], [math]s[/math])
  10 while [math]Q \ne \varnothing[/math]
  11  do [math]u \leftarrow[/math] DEQUEUE([math]Q[/math])
  12     for (для) каждой [math]v \in Adj[u][/math]
  13       do if [math]color[v] =[/math] WHITE
  14         then [math]color[v] \leftarrow[/math] GRAY
  15              [math]d[v] \leftarrow d[u] + 1[/math]
  16              [math]p[v] \leftarrow u[/math] 
  17              ENQUEUE([math]Q[/math], [math]v[/math])
  18     [math]color[u] \leftarrow[/math]BLACK

Анализ

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

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1