Начало
Учебные материалы
Методы уменьшения размера задачи
Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы
Поиск в глубину и поиск в ширину
помечая ее как посещенную. На каждой итерации алгоритм обрабатывает непо-
сещенные вершины, смежные с текущей. Если таких вершин несколько, они
обрабатываются в произвольном порядке. Этот процесс
продолжается до достижения тупика —
вершины, у которой нет непосещенных
смежных вершин.
По достижении тупика алгоритм возвращается на одно ребро
назад (в вершину, из которой он попал в тупик) и пытается продолжить посещения
смежных непосещенных вершин из этого места. В конце концов алгоритм
прекращает работу, когда возвращается в начальную вершину, которая к этому моменту
становится тупиком.
--
В этот момент все вершины данного компонента связности
графа оказываются посещенными. Если в графе после этого имеются непосещенные вершины,
процесс должен повториться, при этом в качестве стартовой
используется любая из непосещенных вершин.
Для выполнения поиска в глубину удобно использовать стек. Мы помещаем
вершину в стек, когда впервые посещаем ее (т.е. когда начинается обход
вершины), и убираем ее из стека, когда она становится тупиком (т.е. обход вершины
завершается).
--
Алгоритм DFS (`G`)
// Входные данные: Граф `G=(V,E)`
// Выходные данные: Граф `G`, вершины которого пронумерованы
// последовательными числами в порядке их
// первого посещения в процессе поиска
Помечаем все вершины в `V` числом 0 (непосещенная вершина)
`count larr 0`
**for** всех вершин `v in V` **do**
`quad` **if** вершина `v` помечена 0
`quad quad "dfs1"(v)`
--
Где dfs1(`v`)
// Рекурсивно посещает все непосещенные вершины, связанные
// с вершиной v, и присваивает им номера в порядке посещения
// при помощи глобальной переменной `count`
`count larr count + 1`
Помечаем вершину `v` числом `count`
**for** каждой вершины `w` из `V`, смежной с `v` **do**
`quad` **if** вершина `w` помечена 0
`quad quad quad "dfs1"(w)`
--
Нетрудно увидеть, что
этот алгоритм достаточно эффективен, поскольку время его работы
пропорционально размеру используемой для представления графа структуры данных.
Так, для представления с использованием матрицы смежности временная
эффективность обхода равна `Theta(|V|^2)`, а для представления с использованием списков смежных вершин -- `Theta(|V| + |E|)`, где `|V|` и `|E|` —
соответственно, количество вершин и ребер графа.
--
Важным применением поиска в глубину являются проверка связности графа
и его ацикличности.
Поскольку поиск в глубину завершается после посещения
всех вершин, соединенных некоторым путем со стартовой, проверку связности
графа можно выполнить следующим образом. Начнем поиск в глубину с
произвольной вершины и после завершения проверим, все ли вершины графа
посещены. Если все, то граф связный, в противном случае —
нет.
--
Для проверки наличия циклов в графе можно сначала в ``dfs1`` присваивать вершине число -1, а
давать номер только тогда, когда вершина становится тупиковой (после цикла).
Тогда обнаружение смежной вершины `w`, помеченной -1, означает, что в графе есть цикл.
Если граф является ориентированным, то для него может поставлена задача
*топологической сортировки*, которая состоит в следующем:
указать такой линейный порядок на его вершинах, чтобы любая дуга вела от вершины с меньшим номером
к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.
Обращение порядка номеров в DFS для поиска циклов дает нам решение задачи топологической сортировки.
--
*Поиск в ширину* работает "кругами", сперва посещая все вершины, смежные со стартовой, затем —
вершины, которые лежат на расстоянии двух ребер от стартовой, и т.д., пока
не будут посещены все вершины связного компонента, которому принадлежит
стартовая точка.
Для выполнения поиска в ширину удобно использовать очередь. Очередь инициализируется стартовой
вершиной поиска, помеченной как посещенная. На каждой итерации алгоритм
находит все непосещенные вершины, смежные с вершиной в начале очереди,
помечает их как посещенные и вносит в очередь; после этого вершина в начале
очереди изымается из нее.
--
Алгоритм BFS (`G`)
// Входные данные: Граф `G=(V,E)`
// Выходные данные: Граф `G`, вершины которого пронумерованы
// последовательными числами в порядке их
// первого посещения в процессе поиска
Помечаем все вершины в `V` числом 0 (непосещенная вершина)
`count larr 0`
**for** всех вершин `v in V` **do**
`quad` **if** вершина `v` помечена 0
`quad quad "bfs1"(v)`
--
Где bfs1(`v`)
// Обход всех вершин, связанных с `v` и назначение им номеров
// в порядке посещения при помощи глобальной переменной `count`
`"mark"(v)`
**while** очередь не пуста **do**
`quad` Извлекаем из очереди первый элемент и помещаем его в `v`
`quad` **for** каждой вершины `w` из `V`, смежной с `v` **do**
`quad quad` **if** вершина `w` помечена 0
`quad quad quad "mark"(w)`
Где mark(`v`)
`count larr count + 1`
Помечаем вершину `v` числом `count`
Добавляем `v` в очередь
--
Поиск в ширину имеет ту же эффективность, что и поиск в глубину.
Поиск в ширину может использоваться для проверки связности графа
и при поиске пути между двумя вершинами, состоящего из минимального количества ребер.
