algorithm
Глубина первого поиска

Введение в поиск по глубине

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

Поиск по глубине - это систематический способ найти все вершины, достижимые из исходной вершины. Как и поиск по ширине, DFS пересекает связанный компонент заданного графа и определяет остовное дерево. Основная идея поиска по глубине - это методическое изучение каждого края. При необходимости мы начинаем с разных вершин. Как только мы обнаруживаем вершину, DFS начинает изучать ее (в отличие от BFS, которая помещает вершину в очередь, чтобы потом исследовать ее).

Давайте посмотрим на пример. Мы проведем этот график:

Мы пройдем по графику, следуя этим правилам:

• Мы начнем с источника.
• Ни один узел не будет посещаться дважды.
• Узлы, которые мы еще не посетили, будут окрашены в белый цвет.
• Узел, который мы посетили, но не посетил все его дочерние узлы, будет окрашен в серый цвет.
• Полностью пройденные узлы будут окрашены в черный цвет.

Давайте посмотрим на это шаг за шагом:

Мы можем увидеть одно важное ключевое слово. Это поддержка . Ты можешь видеть. 5-1 называется backedge. Это связано с тем, что мы еще не сделали это с узлом-1 , поэтому переход от другого узла к узлу-1 означает, что на графике есть цикл. В DFS, если мы можем перейти от одного серого узла к другому, мы можем быть уверены, что график имеет цикл. Это один из способов обнаружения цикла на графике. В зависимости от исходного узла и порядка узлов, которые мы посещаем, мы можем найти любое ребро в цикле в качестве поддержки . Например: если мы сначала отправимся в 5 из 1 , мы бы обнаружили 2-1 в качестве поддержки.

Край, который мы берем, чтобы перейти от серого узла к белому узлу, называется краем дерева . Если мы сохраним только ребро дерева и удалим другие, мы получим дерево DFS .

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

В DFS мы также можем сохранять временные метки для каждого узла, которые могут использоваться многими способами (например: Топологическая сортировка).

1. Когда узел v изменяется с белого на серый, время записывается в d [v] .
2. Когда узел 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 обозначает количество ребер.

Приложения глубины Первый поиск:

• Поиск кратчайшего пути пары в неориентированном графе.
• Обнаружение цикла на графике.
• Найти путь.
• Топологическая сортировка.
• Тестирование, если граф двудольный.
• Поиск сильно подключенного компонента.
• Решение головоломок с одним решением.