Реализация поиска в ширину
Структура данных списка смежности идеально подходит для реализации поиска в ширину. Алгоритм поочередно проверяет ребра, выходящие из заданного узла. Когда мы проверяем ребра, выходящие из u, и добираемся до ребра (u, v), необхо- димо знать, был ли узел v обнаружен ранее в ходе поиска.
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, который организован в формате очереди. В этом случае алгоритм обрабатывает узлы в том порядке, в котором они были изначально обнаружены; каждый обнаруженный новый узел добавляется в конец очереди, а алгоритм всег- да обрабатывает ребра, выходящие из узла, который в настоящее время является первым в очереди.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу