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

Структура данных списка смежности идеально подходит для реализации поиска в ширину. Алгоритм поочередно проверяет ребра, выходящие из заданного узла. Когда мы проверяем ребра, выходящие из u, и добираемся до ребра (u, v), необхо- димо знать, был ли узел v обнаружен ранее в ходе поиска.
Для упрощения этой задачи создается массив Discovered длины n, а при первом обнаружении v в про- цессе поиска присваивается значение Discovered[v] = true. Алгоритм, описанный в предыдущем разделе, строит из узлов уровни L1, L2, ..., где L. — множество узлов, находящихся на расстоянии i от источника 5. Для хранения узлов уровня L. созда- ется список L[i] для всех i = 0, 1, 2, ....

BFS(s):

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

Инициализировать L[0] одним элементом 5

Присвоить значение счетчика уровней i= 0

Присвоить текущее дерево BFS T = 0

Пока элемент L[i] не пуст

инициализировать пустой список L[i + 1]

Для каждого узла и е L[i]

Рассмотреть каждое ребро (u, v), инцидентное и Если Discovered[v]=false

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

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

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

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

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

Доказательство. Для начала легко продемонстрировать для времени вы- полнения алгоритма ограничение O(n2) (более слабая граница, чем заявленная O(m + n)). Чтобы убедиться в этом, достаточно заметить, что достаточно создать максимум n списков L[i], а эта операция выполняется за время O(n). Теперь не- обходимо рассмотреть узлы и этих списков. Каждый узел входит не более чем в один список, поэтому цикл будет выполнен не более 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. Время, потраченное во внутреннем цикле, в котором проверяются ребра, инцидентные и, составляет O(n ), так что

сvммяпн∩е R∩емя по всем узлам составляет , ⅛). Вспомните из (3.9), что

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

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

Если хранить обнаруженные узлы в этом порядке, то все узлы уровня L. будут находиться в очереди до всех узлов уровня Li+1 для i = 0, 1, 2... Следовательно, все узлы уровня Li образуют непрерывную последовательность, за которой следуют все узлы уровня L+1, и т. д. Из этого вытекает, что такая реализация на базе одной очереди приводит к тому же результату, что и описанная ранее реализация BFS.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Реализация поиска в ширину:

  1. 11.2.1. Область реализации права на поиск, получение и потребление информации в Интернет
  2. Поиск смысла жизни – это поиск бессмертия!
  3. Глава 6. Реализация права
  4. РЕАЛИЗАЦИЯ МЫСЛЕННОГО ПРЕДСТАВЛЕНИЯ
  5. 4.2. Реализация
  6. 4. Реализация прав по ипотеке
  7. 3.3. Дальнейшая реализация проекта
  8. 10. Реализация заложенного имущества
  9. Механизм реализации личности
  10. Статья 591. Реализация предмета залога
  11. Практическая реализация.
  12. Практическая реализация.
  13. Практическая реализация.