Подразделы

Другие разделы

Дата и время

04/04/2025 11:37:31

Авторизация

Методы уменьшения размера задачи

Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы

Поиск в глубину и поиск в ширину

Поиск в глубину начинает посещение вершин графа с произвольной вершины, помечая ее как посещенную. На каждой итерации алгоритм обрабатывает непо- сещенные вершины, смежные с текущей. Если таких вершин несколько, они обрабатываются в произвольном порядке. Этот процесс продолжается до достижения тупика — вершины, у которой нет непосещенных смежных вершин.

По достижении тупика алгоритм возвращается на одно ребро назад (в вершину, из которой он попал в тупик) и пытается продолжить посещения смежных непосещенных вершин из этого места. В конце концов алгоритм прекращает работу, когда возвращается в начальную вершину, которая к этому моменту становится тупиком.

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

Для выполнения поиска в глубину удобно использовать стек. Мы помещаем вершину в стек, когда впервые посещаем ее (т.е. когда начинается обход вершины), и убираем ее из стека, когда она становится тупиком (т.е. обход вершины завершается).

Алгоритм 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$ в очередь

Поиск в ширину имеет ту же эффективность, что и поиск в глубину.