Реализация поиска в ширину

Структура данных списка смежности идеально подходит для реализации поиска в ширину. Алгоритм поочередно проверяет ребра, выходящие из заданного узла. Когда мы проверяем ребра, выходящие из u, и добираемся до ребра (u, v), необходимо знать, был ли узел v обнаружен ранее в ходе поиска.

Для упрощения этой задачи создается массив Discovered длины n, а при первом обнаружении v в процессе поиска присваивается значение Discovered[v] = true. Алгоритм, описанный   в предыдущем разделе, строит из узлов уровни L1, L2, …, где Li — множество узлов, находящихся на расстоянии i от источника s. Для хранения узлов уровня Li создается список L[i] для всех i = 0, 1, 2, ….

BFS(s):

Присвоить Discovered[s] = true и Discovered[v] = false для остальных v

Инициализировать L[0] одним элементом s Присвоить значение счетчика уровней i = 0 Присвоить текущее дерево BFS T = Ø

Пока элемент L[i]  не  пуст инициализировать пустой список L[i + 1] Для каждого узла u Ѯ L[i]

Рассмотреть  каждое  ребро  (u,  v),  инцидентное  u

Если Discovered[v]=false

Присвоить Discovered[v]=true Добавить  ребро  (u,  v)  в  дерево  T Добавить v в список L[i + 1]

Конец Если Конец цикла

Увеличить счетчик уровней i на 1

В этой реализации несущественно, хранится каждый список L[i] в формате очереди или стека, поскольку алгоритму разрешено рассматривать узлы уровня Li в произвольном порядке.

(3.11) Приведенная выше реализация алгоритма BFS выполняется за время O(m + n) (то есть в линейной зависимости от размера ввода), если граф описывается представлением списка смежности.

Доказательство. Для начала легко продемонстрировать для времени выполнения алгоритма ограничение O(n2) (более слабая граница, чем заявленная O(m + n)). Чтобы убедиться в этом, достаточно заметить, что достаточно создать максимум n списков L[i], а эта операция выполняется за время O(n).

Теперь необходимо рассмотреть узлы u этих списков. Каждый узел входит не более чем    в один список, поэтому цикл будет выполнен не более n раз по всем итерациям цикла Пока. Рассматривая узел u, необходимо просмотреть все ребра (u, v), инцидентные u. Таких ребер не больше n, и на каждое ребро тратится время O(1).

Итак, общее время, затраченное на одну итерацию внутреннего цикла, не более O(n). Соответственно мы заключаем, что внутренний цикл состоит не более чем из n итераций, а каждая итерация выполняется за время не более O(n), так что общее время не превышает O(n2).

Чтобы прийти к усиленной границе O(m + n), следует увидеть, что внутренний цикл, обрабатывающий узел u, может выполняться за время меньше O(n) при небольшом количестве соседей у u.

Как и прежде, nu обозначает степень узла u, то есть количество ребер, инцидентных u. Время, потраченное во внутреннем цикле, в котором проверяются ребра, инцидентные u, составляет O(nu), так что суммарное время по всем узлам составляет. Вспомните из (3.9),  что, а общее время, потраченное на проверку ребер для всего алгоритма, составляет O(m).

Дополнительное время O(n) понадобится для подготовки списков и управления массивом Discovered. Таким образом, общие затраты времени составляют O(m + n), как и утверждалось выше.

В нашем описании алгоритма упоминались n разных списков L[i] для каждого уровня Li. Вместо нескольких разных списков можно реализовать алгоритм с одним списком L, который организован в формате очереди. В этом случае алгоритм обрабатывает узлы в том порядке, в котором они были изначально обнаружены; каждый обнаруженный новый узел добавляется в конец очереди, а алгоритм всегда обрабатывает ребра, выходящие из узла, который в настоящее время является первым в очереди.