Поиск в ширину (Волновой алгоритм)
Этот алгоритм поиска в графе также называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны. Волна растекается равномерно во все стороны с одинаковой скоростью. На i-ом шаге будут помечены все вершины, достижимые за i ходов, если ходом считать переход из одной вершины в другую.
Метод поиска в ширину получается из программы поиска в глубину (см. п. 3.6.2.1), если заменить стек возврата на очередь. Эта простая замена модифицирует порядок обхода вершин так, что обход идет равномерно во все стороны, а не вглубь как при поиске в глубину.
Здесь используются те же структуры Graph и Visited, что были описаны в алгоритме поиска в глубину.
procedure WidthSearch(v: integer);
var
Delayed: array[1..n] of integer; {Очередь}
Count, {Хвост очереди}
Head: integer; {Голова очереди}
Current, j: integer;
begin
Count := 1; Head := 0; Delayed[Count] := v;
Visited[v] := true;
repeat
Head := Head +1; Current := Delayed[Head];
for каждой вершины y, смежной с Current do
if not Visited[y] then begin
Count := Count + 1;
Delayed[Count] := Graph[y];
Visited[y] := true;
end;
until Count = Head;
end;
begin
while есть непомеченные вершины do begin
v := любая непомеченная вершина;
WidthSearch(v);
end;
end.
Рисунок 52. Поиск в ширину
Поиск в ширину для полного обхода графа с n вершинами и m дугами требует столько же времени, как и поиск в глубину, то есть времени порядка O(max(n, m)). Поскольку обычно m n, то получается O(m).
Yandex.RTB R-A-252273-3- Содержание
- Основные сведения
- Понятия алгоритма и структуры данных
- Анализ сложности и эффективности алгоритмов и структур данных
- Структуры данных
- Элементарные данные
- Данные числовых типов
- Данные целочисленного типа
- Данные вещественного типа
- Операции над данными числовых типов
- Данные символьного типа
- Данные логического типа
- Данные типа указатель
- Линейные структуры данных
- Множество
- Линейные списки
- Линейный однонаправленный список
- Линейный двунаправленный список
- Циклические списки
- Циклический однонаправленный список
- Циклический двунаправленный список
- Разреженные матрицы
- Матрицы с математическим описанием местоположения элементов
- Матрицы со случайным расположением элементов
- Очередь
- Нелинейные структуры данных
- Мультисписки
- Слоеные списки
- Спецификация
- Реализация
- Деревья
- Общие сведения
- Обходы деревьев
- Спецификация двоичных деревьев
- Реализация
- Основные операции
- Организация
- Представление файлов b-деревьями
- Основные операции
- Общая оценка b-деревьев
- Алгоритмы обработки данных
- Методы разработки алгоритмов
- Метод декомпозиции
- Динамическое программирование
- Поиск с возвратом
- Метод ветвей и границ
- Метод альфа-бета отсечения
- Локальные и глобальные оптимальные решения
- Алгоритмы поиска
- Поиск в линейных структурах
- Последовательный (линейный) поиск
- Бинарный поиск
- Хеширование данных
- Функция хеширования
- Открытое хеширование
- Закрытое хеширование
- Реструктуризация хеш-таблиц
- Поиск по вторичным ключам
- Инвертированные индексы
- Битовые карты
- Использование деревьев в задачах поиска
- Упорядоченные деревья поиска
- Случайные деревья поиска
- Оптимальные деревья поиска
- Сбалансированные по высоте деревья поиска
- Поиск в тексте
- Прямой поиск
- Алгоритм Кнута, Мориса и Пратта
- Алгоритм Боуера и Мура
- Алгоритмы кодирования (сжатия) данных
- Общие сведения
- Метод Хаффмана. Оптимальные префиксные коды
- Кодовые деревья
- Алгоритмы сортировки
- Основные сведения. Внутренняя и внешняя сортировка
- Алгоритмы внутренней сортировки
- Сортировка подсчетом
- Сортировка простым включением
- Сортировка методом Шелла
- Сортировка простым извлечением.
- Древесная сортировка
- Сортировка методом пузырька
- Быстрая сортировка (Хоара)
- Сортировка слиянием
- Сортировка распределением
- Сравнение алгоритмов внутренней сортировки
- Алгоритмы внешней сортировки
- Алгоритмы на графах
- Алгоритм определения циклов
- Алгоритмы обхода графа
- Поиск в глубину
- Поиск в ширину (Волновой алгоритм)
- Нахождение кратчайшего пути
- Алгоритм Дейкстры
- Алгоритм Флойда
- Переборные алгоритмы
- Нахождение минимального остовного дерева
- Алгоритм Прима
- Алгоритм Крускала
- 190000, Санкт-Петербург, ул. Б. Морская, 67