algorithm
Глубина первого поиска
Поиск…
Введение в поиск по глубине
Поиск по глубине - это алгоритм для перемещения или поиска структур данных дерева или графика. Один начинается с корня и исследует, насколько это возможно, вдоль каждой ветви перед отступлением. Версия поиска по глубине была исследована в 19-м веке французским математиком Чарльзом Пьером Тремо в качестве стратегии решения лабиринтов.
Поиск по глубине - это систематический способ найти все вершины, достижимые из исходной вершины. Как и поиск по ширине, DFS пересекает связанный компонент заданного графа и определяет остовное дерево. Основная идея поиска по глубине - это методическое изучение каждого края. При необходимости мы начинаем с разных вершин. Как только мы обнаруживаем вершину, DFS начинает изучать ее (в отличие от BFS, которая помещает вершину в очередь, чтобы потом исследовать ее).
Давайте посмотрим на пример. Мы проведем этот график:
Мы пройдем по графику, следуя этим правилам:
- Мы начнем с источника.
- Ни один узел не будет посещаться дважды.
- Узлы, которые мы еще не посетили, будут окрашены в белый цвет.
- Узел, который мы посетили, но не посетил все его дочерние узлы, будет окрашен в серый цвет.
- Полностью пройденные узлы будут окрашены в черный цвет.
Давайте посмотрим на это шаг за шагом:
Мы можем увидеть одно важное ключевое слово. Это поддержка . Ты можешь видеть. 5-1 называется backedge. Это связано с тем, что мы еще не сделали это с узлом-1 , поэтому переход от другого узла к узлу-1 означает, что на графике есть цикл. В DFS, если мы можем перейти от одного серого узла к другому, мы можем быть уверены, что график имеет цикл. Это один из способов обнаружения цикла на графике. В зависимости от исходного узла и порядка узлов, которые мы посещаем, мы можем найти любое ребро в цикле в качестве поддержки . Например: если мы сначала отправимся в 5 из 1 , мы бы обнаружили 2-1 в качестве поддержки.
Край, который мы берем, чтобы перейти от серого узла к белому узлу, называется краем дерева . Если мы сохраним только ребро дерева и удалим другие, мы получим дерево DFS .
В неориентированном графике, если мы можем посетить уже посещенный узел, это должно быть поддержкой . Но для ориентированных графов мы должны проверить цвета. Если и только если мы можем перейти от одного серого узла к другому серому узлу, который называется поддержкой .
В DFS мы также можем сохранять временные метки для каждого узла, которые могут использоваться многими способами (например: Топологическая сортировка).
- Когда узел v изменяется с белого на серый, время записывается в d [v] .
- Когда узел v изменяется с серого на черный, время записывается в f [v] .
Здесь d [] означает время обнаружения, а f [] означает время окончания . Наш пес-код будет выглядеть так:
Procedure DFS(G):
for each node u in V[G]
color[u] := white
parent[u] := NULL
end for
time := 0
for each node u in V[G]
if color[u] == white
DFS-Visit(u)
end if
end for
Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
if color[v] == white
parent[v] := u
DFS-Visit(v)
end if
end for
color[u] := black
time := time + 1
f[u] := time
Сложность:
Каждый узел и ребра посещаются один раз. Таким образом, сложность DFS равна O (V + E) , где V обозначает количество узлов, а E обозначает количество ребер.
Приложения глубины Первый поиск:
- Поиск кратчайшего пути пары в неориентированном графе.
- Обнаружение цикла на графике.
- Найти путь.
- Топологическая сортировка.
- Тестирование, если граф двудольный.
- Поиск сильно подключенного компонента.
- Решение головоломок с одним решением.