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

Алгоритмы   25 Июль 2015  Автор статьи: admin 

Обход в ширину (англ. Breadth-First Search, BFS) — один из основных не рекурсивных методов обхода вершин графа, позволяющий построить кратчайшие пути из начальной вершины (source vertex) обхода до всех остальных. Название метода объясняется тем, что в процессе обхода вершины графа просматриваются вширь, а не вглубь, в отличие от метода поиска в глубину. Общая идея алгоритма состоит в следующем: для стартовой вершины s просматриваются все не посещенные потомки, затем не посещенные потомки потомков и т. д. Алгоритм поиска в ширину перечисляет все достижимые вершины из начальной вершины s в порядке возрастания расстояния от нее и заканчивает свою работу, когда все достижимые вершины пройдены. Под расстоянием подразумевается длина кратчайшего пути, то есть количество ребер из начальной вершины обхода s до конкретной достижимой вершины из нее. Впервые обнаружив вершину v графа, отмечаем это событие, проставляя в массиве used пройденных вершин значение true, used[v] \gets true. В процессе поиска из графа выделяется часть, называемая «деревом поиска в ширину» c корнем s, которая является начальной вершиной обхода. Для каждой вершины дерева путь из корня s в нее будет одним из кратчайших. Расстояние до вершины v, равное длине кратчайшего пути, начинающего в начальной вершине обхода s, хранится в массиве d. В случае, если некоторая вершина v графа G не достижима из начальной вершины обхода s, то после работы алгоритма значение used[v] будет заполнено значением false, used[v] \gets false, а значение d[v] будет заполнено значением INF, d[v] \gets INF. Значение INF обозначает бесконечность и на практике равно какому-либо большому наперед заданному натуральному числу, которое обязательно превосходит любое кратчайшее расстояния между любой парой вершин в исходном графе G. Для восстановления пути из начальной вершины обхода s в достижимую из нее вершину v используется массив предшественников \pi, в котором для каждой вершины хранится ее предок в дереве обхода в ширину. Если вершина v является начальной, т. е. v = s, или вершина v не достижима из вершины s, значение массива \pi[v] полагается равным -1, \pi \gets -1. Для реализации алгоритма используется структура данных «очередь» (queue), которая работает по принципу FIFO (first-in, first-out). Это значит, что чем раньше очередная вершина была посещена, тем раньше будут просмотрены все ее еще не пройденные соседние вершины.
Исходный граф может быть как неориентированным, так и ориентированным, сути метода это не меняет.

 

Пошаговое представление

G(V, E) – исходный граф, в котором V – это множество вершин, а E – это множество ребер.
used – массив для хранения информации о пройденных и не пройденных вершинах графа G.
d – массив для хранения расстояния от начальной вершины s до каждой достижимой из нее.
\pi – массив для хранения предков вершин в дереве обхода в ширину.
queue – очередь, структура данных, действующая по принципу FIFO.

1
2
3
4
{\bf for} (для) всех вершин v \in V[G]
    used[v] \gets false //помечаем каждую вершину как не посещенную
    d[v] \gets INF //полагаем расстояние до каждой непомеченной вершины, равным бесконечности
    \pi[v] \gets -1 //предок каждой непомеченной вершины равен -1

 
BFS(s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{\bf if} \ used[v] = true
    {\bf return}
queue.push(s) //кладем начальную вершину s в очередь
used[s] \gets true //помечаем вершину s как посещенную
d[s] \gets 0 //расстояние от вершины s до самой себя равно 0
{\bf while} \ queue \neq \varnothing //пока очередь queue не пустая
   v \gets queue.head() //продолжаем обход из вершины v, находящейся в «голове» очереди queue
   queue.pop() //удаляем вершину в «голове» из очереди
   {\bf for} (для) всех вершин w \in E[v] //обрабатываем ребро (v, w)
     {\bf if} \ used[w] = false //если вершина w является не посещенной, то добавляем ее в очередь queue
       used[w] \gets true //помечаем вершину w как посещенную
       \pi[w] \gets v //помечаем предком вершины w вершину v
       d[w] \gets d[v] + 1 //обновляем расстояние от начальной вершины обхода до вершины w
      queue.push(w) //кладем вершину w в очередь

Для наглядности будем считать, что в процессе работы алгоритма вершины графа могут быть раскрашены в белый, серый и черный цвет. Вначале все вершины покрашены в белый цвет, то есть все еще непосещенные вершины — белые. Потом в ходе работы алгоритма белая вершина v может стать серой, а серая вершина v — черной. Покраска осуществляется только в этом порядке. Повстречав не посещенную вершину, алгоритм поиска в ширину красит ее, таким образом серые и черные вершины — это в точности те, что уже обнаружены, т. е. те, для которых значение массива used заполнено в true. Качественное отличие между серыми и черными вершинами заключается в том, что серыми вершинами являются те, который на данным момент работы алгоритма уже посещены и находятся в очереди queue, в то время, как черные вершины уже были извлечены из очереди queue. Более того, поддерживается следующее свойство: если (v, w) \in E и вершина w — черная, то вершина v — серая или черная вершина. Таким образом, только серые вершины могут иметь смежные непосещенные вершины.

 

Дерево поиска в ширину

В ходе работы процедуры BFS выделяется некоторый подграф, задаваемый полями массива \pi, который называется деревом поиска в ширину. Более формально, применим процедуру BFS в графу G(V, E) с начальной вершиной s. Рассмотрим подграф, вершинами которого являются достижимые из начальной вершиной s вершины v \in V, а ребрами являются ребра (\pi[v], v) для всех таких вершин v. Дерево будет построено следующим образом. Вначале дерево поиска в ширину состоит только из корня – начальной вершиной s. Как только алгоритм обнаруживает новую белую вершину w, смежную с ранее найденной вершиной v, вершина w вместе с ребром (v, w) добавляется к дереву поиска, становясь потомком (descendant) вершины v. При этом значение \pi[w] становится равным v, т. е. \pi[w] \gets v, а вершина v становится предком (ancestor) вершины w. Процесс построения дерева поиска в ширину показан на примере графа G. На рисунках (a-л) изображены стадии окрашивания вершин графа G в серые и черные цвета, а также список вершин в очереди queue на каждом этапе алгоритма. Начальной вершиной обхода является вершина с номером 1.

pic1
pic2
pic3
pic4

Построенный таким образом подграф G_{\pi} графа G представляет собой дерево, в котором для каждой вершины v имеется единственный простой путь из начальной вершины обхода s. Это путь будет кратчайшим путем из вершины s в вершину v. Дерево G_{\pi} называется деревом поиска в ширину (breadth-first tree) для данного графа и данной начальной вершины. Заметим, что построенное дерево зависит от того, в каком порядке просматриваются вершины в списках смежных вершин. Ребра исходного графа G, которые входят в дерево поиска в ширину G_{\pi} изображены на рисунке ниже жирной линией.

pic4

 

Реализации метода обхода в ширину

Научиться программировать

  • на Delphi

  • на Java

  • на C++